Using std::multiset instead of std::priority_queue
std::multisetをstd::priority_queueの代わりに使う実装例を目にしました。std::priority_queueは重いと言われているし、std::multisetのほうが性能がよいのであれば使う価値があるな...と考えて計測してみたところstd::priority_queueよりも3倍重く少しがっかり。まあ知見は得られたのでよしとします。
以下は検証に使った実装です。こちらはstd::priority_queueを使ったもので、数値の小さいものをキューに残そうとします。値が重複していても大丈夫です。
int N = 1000000, M = 100, K = 1000; std::priority_queue<int> pq; for (int i = 0; i < N; i ++) { // N回 int size = rand() % M; for (int j = 0; j < size; j ++) // [0, M)個のランダムな値を追加して pq.push(rand()); while (pq.size() > K) // キューがK個になるまで大きな数値を取り除く pq.pop(); // (つまり、小さな数値を最大K個残す) }
std::multiset版はこちらです。数値の小さいものを残すために値の正負を反転しています(std::multiset::removeがリバースイテレータを取れればいいのですが、そういうものではないようです)。
std::multiset<int> set; for (int i = 0; i < N; i ++) { int size = rand() % M; for (int j = 0; j < size; j ++) set.insert(- rand()); while (set.size() > K) set.erase(std::begin(set)); }
それでもstd::multisetを使う利点があるとすれば、要素を取り出すことなく反復できるところでしょうか(std::priority_queueは取り出す必要があります)。
// 要素を(結果、降順で)表示する for (const auto& i : set) std::cerr << - i << std::endl;