最終更新日時(UTC):
が更新

履歴 編集

class template
<queue>

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)

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

queueは2つのテンプレート引数を持つ。

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

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

出力

1
3
4

4
3
1

関連項目