• Class / Function / Type

      std::
    • Header file

      <>
    • Other / All

    最終更新日時(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が使用される。

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

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

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

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

    メンバ関数

    名前 説明 対応バージョン
    (constructor) コンストラクタ
    ~priority_queue() = default デストラクタ
    operator=(const priority_queue&) = default
    operator=(priority_queue&&) = default
    代入演算子
    empty 要素が空かどうかを判定する
    size 要素数を取得する
    top 次の要素にアクセスする
    push 要素を追加する
    push_range Rangeの要素を追加する C++23
    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
    

    関連項目