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が使用される。

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

概念・前提知識

• コンテナとは

適格要件

TがContainer::value_typeと同じ型であること。

メンバ関数

protectedメンバ変数

メンバ型

非メンバ関数

推論補助

例

基本的な使い方

#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>
#include <vector>

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();
    }
  }
}

出力

1
3
4

4
3
1

関連項目

• std::push_heap
• std::pop_heap
• std::make_heap
• std::sort_heap

参照

• LWG Issue 2566. Requirements on the first template parameter of container adaptors
  • C++17で、テンプレートパラメータTがContainer::value_typeと同じ型であることが規定された
• LWG Issue 2684. priority_queue lacking comparator typedef
  • C++17で、他の順序付きコンテナと同様に、比較関数型のメンバ型value_compareが追加された