priority_queueを使って要素を小さい順に取り出す

C++ STLのsetやmapの場合は要素を小さい順にソートするけど，priority_queueは要素を大きい順に並べる．

priority_queueの定義はこんな感じ．

template <class T, class Container = vector<T>,
          class Compare = less<typename Container::value_type> >
  class priority_queue;

ここで紛らわしいのは，Compareにはデフォルトでlessが割り当てられるけど，priority_queueはこれを使って要素を大きい順に並べること．指定するCompareと実際のソートの仕方が逆で直感的じゃない．要注意．

要素を小さい順に取り出したい場合は以下のようにgreaterを指定しなければならない．

priority_queue<int, vector<int>, greater<int> > que;

あとはpushなりtopなりpopなりすれば要素を小さい順から取り出せるようになる．

以下はpriority_queueから要素を小さい順に取り出す場合の例．

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main(int argc, char const* argv[]) {
  priority_queue<int, vector<int>, greater<int> > que;

  que.push(3);
  que.push(1);
  que.push(4);
  que.push(1);
  que.push(5);
  que.push(9);
  que.push(2);
  que.push(6);

  while (!que.empty()) {
    cout << que.top() << endl;
    que.pop();
  }
  
  return 0;
}

出力はこちら．

1
1
2
3
4
5
6
9

昨日greaterを指定し忘れたpriority_queueでダイクストラ法を実装して計算時間がめちゃくちゃなことになったのは内緒．