std::priority_queue

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

概要

priority_queueはコンテナアダプタであり、優先順位付きキューを実現する目的で設計されている。要素をpush()で追加し、取り出す際にtop()を呼び出すことで、Compare述語によって優先順に要素が取り出される。デフォルトでは降順に処理される。

priority_queueは、所定のメンバ関数を持つコンテナのオブジェクトを内部実装として用いており、標準のコンテナ、もしくは独自に実装したコンテナを指定することができる。

このコンテナに必要な要件は、ランダムアクセスイテレータを持ち、かつ以下のメンバ関数を持つことである。

front()
push_back()
pop_back()
emplace_back() (C++11)

この要件を満たすものとしてはvectorとdequeがあり、デフォルトではvectorが使用される。

priority_queueは3つのテンプレート引数を持つ。

各テンプレートパラメータの意味は以下の通りである。

T: 要素の型
Container: 内部実装のコンテナクラス
Compare: 優先順に並べ替えるための比較用述語型。デフォルトでは降順比較のlessが使用される。

以下のリファレンス中では、テンプレート引数として同じ名前を用いる。

メンバ関数

名前	説明	対応バージョン
`(constructor)`	コンストラクタ
`~priority_queue() = default`	デストラクタ
`operator=(const priority_queue&) = default` `operator=(priority_queue&&) = default`	代入演算子
`empty`	要素が空かどうかを判定する
`size`	要素数を取得する
`top`	次の要素にアクセスする
`push`	要素を追加する
`emplace`	直接構築で要素を追加する	C++11
`pop`	次の要素を削除する
`swap`	他のpriority_queueオブジェクトと値を入れ替える	C++11

protectedメンバ変数

変数名	型	対応バージョン
`c`	`Container`
`comp`	`Compare`

メンバ型

名前	説明	対応バージョン
`value_type`	`Container::value_type`
`reference`	`Container::reference`	C++11
`const_reference`	`Container::const_reference`	C++11
`size_type`	`Container::size_type`
`container_type`	`Container`

非メンバ関数

名前	説明	対応バージョン
`swap`	2つの`priority_queue`オブジェクトを入れ替える	C++11

推論補助

名前	説明	対応バージョン
`(deduction_guide)`	クラステンプレートの推論補助	C++17

例

基本的な使い方

#include <iostream>
#include <queue>

int main()
{
  // intを要素に持つ優先順位付きキュー。
  // 降順に処理する
  std::priority_queue<int> que;

  // データを追加する
  que.push(3);
  que.push(1);
  que.push(4);

  // 処理順に出力する
  while (!que.empty()) {
    std::cout << que.top() << std::endl;
    que.pop();
  }
}

出力

4
3
1

処理順をカスタマイズする (C++11)

#include <iostream>
#include <queue>

int main()
{
  // 昇順に処理する
  {
    std::priority_queue<
      int,                // 要素の型はint
      std::vector<int>,   // 内部コンテナはstd::vector (デフォルトのまま)
      std::greater<int>   // 昇順 (デフォルトはstd::less<T>)
    > que;

    que.push(3);
    que.push(1);
    que.push(4);

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

  // 処理順を表す比較関数オブジェクトにラムダ式を使用する
  {
    auto compare = [](int a, int b) {
      return a < b;
    };

    std::priority_queue<
      int,
      std::vector<int>,
      decltype(compare) // 比較関数オブジェクトを指定
    > que {compare};

    que.push(3);
    que.push(1);
    que.push(4);

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

出力