メモの日々

■ [c++] std::priority_queueのメモ

C++のstd::priority_queueを使うときにいつも調べる羽目になるのでメモしておく。

デフォルトの動作

std::priority_queueにはpush()で要素を追加でき、top()で「優先度が最高の要素」を取得できる。 デフォルトの優先度の決め方は

• std::lessで比較した時に大きい要素が優先度が高い

である。なので、例えば整数を格納すると値が最大の要素を取得できる。

#include <iostream>
#include <queue>

int main()
{
  std::priority_queue<int> q;
  for (int i : {1, 2, 3, 1, 2, 3}) {
    q.push(i);
  }

  while (!q.empty()) {
    std::cout << q.top() << " ";
    q.pop();
  }
  std::cout << std::endl;
}

3 3 2 2 1 1

優先度のカスタマイズ

優先度の定義をカスタマイズするためには、

• 要素を比較するためのファンクタのインスタンス
• 要素を比較するためのファンクタの型
• 要素を格納するためのコンテナの型

を指定しなければならない。1番目はコンストラクタの引数で、2番目と3番目はテンプレートパラメータで指定する。3番目を指定しなければいけないのは面倒だが、通常はstd::vectorを指定しておけばよい。

上の例の優先度の定義を逆にするには、qの宣言を

  std::priority_queue<int, std::vector<int>, std::greater<int>> q;

と変更することになる（ファンクタのインスタンスはファンクタのデフォルトコンストラクタで生成されるものでいいので指定していない）。これでtop()により値が最小の要素を取得できるようになる。std::greaterを指定すると最小の要素を取得できるようになるという所が混乱しやすいので注意。

優先度をラムダ式で指定する

優先度をラムダ式で指定するにはdecltypeを使えばよい。上のstd::greaterの代わりにラムダ式を使う場合は

  auto comp = [](int lhs, int rhs) { return lhs > rhs; };
  std::priority_queue<int, std::vector<int>, decltype(comp)> q(comp);

のように書く。