名前空間
変種
操作

std::priority_queue

提供: cppreference.com
< cpp‎ | container
ヘッダ <queue> で定義
template<

    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>

> class priority_queue;

優先度付きキューは (デフォルトでは) 最も大きな要素を定数時間で提供するコンテナアダプタです。 挿入および抽出は対数時間がかかります。

順序を変更するためにユーザ提供の Compare を提供できます。 例えば std::greater<T> を使うと top() に最も小さな要素が現れるようになります。

priority_queue を用いるのは、何らかのランダムアクセスコンテナを使ってヒープを管理するのと同様ですが、誤ってヒープを壊さずに済むという利点があります。

目次

[編集] テンプレート引数

T - 格納される要素の型。 TContainer::value_type が同じ型でない場合、動作は未定義です。 (C++17およびそれ以降)
Container - 要素を格納するために使用するベースとなるコンテナの型。 コンテナは SequenceContainer の要件を満たさなければならず、そのイテレータは RandomAccessIterator の要件を満たさなければなりません。 さらに、通常のセマンティクスを持つ以下の関数を提供していなければなりません。
  • front()
  • push_back()
  • pop_back()

標準のコンテナ std::vector および std::deque はこれらの要件を満たします。

Compare - strict weak ordering を提供する Compare 型。

Compare 引数は weak ordering で第1引数が第2引数よりもに来る場合 true を返すように定義されていることに注意してください。 しかし priority queue は最も大きな要素を最初に出力するため、に来る要素は実際には最後に出力されます。 つまり、 Compare によって定められる weak ordering に従って「最後」の要素がキューの先頭に格納されます。

[編集] メンバ型

メンバ型 定義
container_type Container [edit]
value_compare (C++17) Compare
value_type Container::value_type [edit]
size_type Container::size_type [edit]
reference Container::reference [edit]
const_reference Container::const_reference [edit]

[編集] メンバ関数

priority_queue を構築します
(パブリックメンバ関数) [edit]
priority_queue を破棄します
(パブリックメンバ関数) [edit]
コンテナアダプタに値を代入します
(パブリックメンバ関数) [edit]
要素アクセス
トップの要素にアクセスします
(パブリックメンバ関数) [edit]
容量
ベースとなるコンテナが空かどうか調べます
(パブリックメンバ関数) [edit]
要素数を返します
(パブリックメンバ関数) [edit]
変更
要素を挿入してベースとなるコンテナをソートします
(パブリックメンバ関数) [edit]
(C++11)
要素をその場で構築してベースとなるコンテナをソートします
(パブリックメンバ関数) [edit]
トップの要素を削除します
(パブリックメンバ関数) [edit]
内容を入れ替えます
(パブリックメンバ関数) [edit]

メンバオブジェクト

Container c
ベースとなるコンテナ
(プロテクテッドメンバオブジェクト) [edit]
Compare comp
比較関数オブジェクト
(プロテクテッドメンバオブジェクト)

[編集] 非メンバ関数

std::swap アルゴリズムの特殊化
(関数テンプレート) [edit]

[編集] ヘルパークラス

std::uses_allocator 型特性の特殊化
(関数テンプレート) [edit]

[編集] 推定ガイド(C++17およびそれ以降)

[編集]

#include <functional>
#include <queue>
#include <vector>
#include <iostream>
 
template<typename T> void print_queue(T& q) {
    while(!q.empty()) {
        std::cout << q.top() << " ";
        q.pop();
    }
    std::cout << '\n';
}
 
int main() {
    std::priority_queue<int> q;
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q.push(n);
 
    print_queue(q);
 
    std::priority_queue<int, std::vector<int>, std::greater<int> > q2;
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q2.push(n);
 
    print_queue(q2);
 
    // Using lambda to compare elements.
    auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1);};
    std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q3.push(n);
 
    print_queue(q3);
 
}

出力:

9 8 7 6 5 4 3 2 1 0 
0 1 2 3 4 5 6 7 8 9 
8 9 6 7 4 5 2 3 0 1