三浦ノート

自分の経験したことを検索可能にしていくブログ.誰かの役に立ってくれれば嬉しいです.

C++ で std::queue を定数時間で空にする方法

C++ でstd::queue の内容を全て削除したくなったのですが,std::queue には clear 関数がありませんでした.

なので,私は直観的には queue が空になるまで pop を繰り返せばいいと思ったのですが,これはqueueのサイズに比例した時間がかかります.

もっと洗練された方法がないか探してみたところ,空のqueueと swap するという方法が見つかりました.計算量はqueueのベースとなるコンテナに依りますが一般には定数時間だそうです.

参考

std::queue をクリアする方法。 - Qiita

std::queue<T,Container>::swap - cppreference.com

実際に以下のように時間を計ってみます.

大きなサイズの queue に対して,内容を空にする2つの方法の実行時間を計測してみました.

#include <iostream>
#include <queue>
#include <time.h>
using namespace std;

int main() {
    queue<int> q;
    clock_t start, end;

    for (int i = 0; i < 100000000; ++i) q.push(i);
    start = clock();
    while (q.size()) q.pop();
    end = clock();
    cout << end - start << " ms" <<  endl;

    for (int i = 0; i < 100000000; ++i) q.push(i);
    start = clock();
    queue<int>().swap(q);
    end = clock();
    cout << end - start << " ms" <<  endl;
}

出力は以下のようになりました.

3712 ms
193 ms

一行目がwhileで繰り返しpopをした場合,二行目がswapを使った場合です.

やはりswapですると速かったです.