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;