名前空間
変種
操作

std::priority_queue

From cppreference.com
< cpp‎ | container
 
C++
コンパイラサポート
フリースタンディングとホスト
言語
標準ライブラリ
標準ライブラリヘッダー
名前付き要件
機能テストマクロ (C++20)
言語サポートライブラリ
コンセプトライブラリ (C++20)
診断ライブラリ
メモリ管理ライブラリ
メタプログラミングライブラリ (C++11)
汎用ユーティリティライブラリ
コンテナライブラリ
イテレータライブラリ
Rangesライブラリ (C++20)
アルゴリズムライブラリ
文字列ライブラリ
テキスト処理ライブラリ
数値ライブラリ
日付と時刻ライブラリ
入出力ライブラリ
ファイルシステムライブラリ (C++17)
並行サポートライブラリ (C++11)
実行制御ライブラリ (C++26)
Technical specifications (技術仕様)
シンボルインデックス
外部ライブラリ
 
コンテナライブラリ
 
std::priority_queue
 
ヘッダー<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を扱うことは、いくつかのランダムアクセスのコンテナでヒープを管理することに似ていますが、誤ってヒープを無効にしてしまう心配がないという利点があります。

std::priority_queueのすべてのメンバ関数はconstexprです。定数式の評価においてstd::priority_queueオブジェクトを作成し、使用することが可能です。

しかし、std::priority_queueオブジェクトは、通常constexprにはできません。なぜなら、動的に確保されたストレージは、同じ定数式の評価で解放されなければならないからです。

 (C++26以降)

目次

[編集] テンプレートパラメータ

T - 格納される要素の型です。TがContainer::value_typeと同じ型でない場合、プログラムは不正形式です。
コンテナ - 要素を格納するために使用する基底コンテナの型です。このコンテナはSequenceContainerの要件を満たし、そのイテレータはLegacyRandomAccessIteratorの要件を満たす必要があります。さらに、通常のセマンティクスで以下の関数を提供する必要があります。

標準コンテナのstd::vector（std::vector<bool>を含む）およびstd::dequeは、これらの要件を満たします。

Compare - 厳密な弱順序を提供するCompare型。

Compareパラメータは、その最初の引数が弱い順序で2番目の引数より前に来る場合にtrueを返すように定義されていることに注意してください。しかし、優先度キューは最大の要素を最初に出力するため、「前に来る」要素は実際には最後に出力されます。つまり、キューの先頭にはCompareによって課された弱い順序に従って「最後の」要素が含まれます。

[編集] メンバ型

メンバ型 定義
container_type Container[編集]
value_compare Compare
value_type Container::value_type[編集]
size_type Container::size_type[編集]
reference Container::reference[編集]
const_reference Container::const_reference[編集]

[編集] メンバオブジェクト

メンバ名 定義
Container c
 基底コンテナ
(protected member object) [編集]
Compare comp
 比較関数オブジェクト
(protected member object)

[編集] メンバ関数

 priority_queueを構築する
(公開メンバ関数) [編集]
 priority_queueを破棄する
(公開メンバ関数) [編集]
 コンテナアダプタに値を割り当てる
(公開メンバ関数) [編集]
要素アクセス
 トップ要素にアクセスする
(public member function) [編集]
容量
 コンテナアダプタが空かどうかをチェックする
(public メンバ関数) [編集]
 要素数を返す
(public メンバ関数) [編集]
変更
 要素を挿入し、基底コンテナをソートする
(public member function) [編集]
(C++23)
 要素の範囲を挿入し、基底コンテナをソートする
(public member function) [編集]
(C++11)
 要素をインプレースで構築し、基底コンテナをソートする
(公開メンバ関数) [編集]
 トップ要素を削除する
(public member function) [編集]
(C++11)
 内容を交換する
(public メンバ関数) [編集]

[編集] 非メンバ関数

(C++11)
 std::swap アルゴリズムを特殊化する
(関数テンプレート) [編集]

[編集] ヘルパークラス

(C++11)
 std::uses_allocator 型特性を特殊化する
(クラス テンプレート特殊化) [edit]
(C++23)
 std::priority_queueの書式設定サポート
(class template specialization) [編集]

推論補助

 (C++17以降)

[編集] 備考

機能テストマクロ 値 規格 機能
__cpp_lib_containers_ranges 202202L (C++23) Ranges対応コンテナの構築と挿入
__cpp_lib_constexpr_containers 202502L (C++26) constexpr std::priority_queue

[編集] 例

このコードを実行
#include <functional>
#include <iostream>
#include <queue>
#include <string_view>
#include <vector>
 
template<typename T>
void pop_println(std::string_view rem, T& pq)
{
    std::cout << rem << ": ";
    for (; !pq.empty(); pq.pop())
        std::cout << pq.top() << ' ';
    std::cout << '\n';
}
 
template<typename T>
void println(std::string_view rem, const T& v)
{
    std::cout << rem << ": ";
    for (const auto& e : v)
        std::cout << e << ' ';
    std::cout << '\n';
}
 
int main()
{
    const auto data = {1, 8, 5, 6, 3, 4, 0, 9, 7, 2};
    println("data", data);
 
    std::priority_queue<int> max_priority_queue;
 
    // Fill the priority queue.
    for (int n : data)
        max_priority_queue.push(n);
 
    pop_println("max_priority_queue", max_priority_queue);
 
    // std::greater<int> makes the max priority queue act as a min priority queue.
    std::priority_queue<int, std::vector<int>, std::greater<int>>
        min_priority_queue1(data.begin(), data.end());
 
    pop_println("min_priority_queue1", min_priority_queue1);
 
    // Second way to define a min priority queue.
    std::priority_queue min_priority_queue2(data.begin(), data.end(), std::greater<int>());
 
    pop_println("min_priority_queue2", min_priority_queue2);
 
    // Using a custom function object to compare elements.
    struct
    {
        bool operator()(const int l, const int r) const { return l > r; }
    } customLess;
 
    std::priority_queue custom_priority_queue(data.begin(), data.end(), customLess);
 
    pop_println("custom_priority_queue", custom_priority_queue);
 
    // 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)> lambda_priority_queue(cmp);
 
    for (int n : data)
        lambda_priority_queue.push(n);
 
    pop_println("lambda_priority_queue", lambda_priority_queue);
}

出力

data: 1 8 5 6 3 4 0 9 7 2
max_priority_queue: 9 8 7 6 5 4 3 2 1 0
min_priority_queue1: 0 1 2 3 4 5 6 7 8 9
min_priority_queue2: 0 1 2 3 4 5 6 7 8 9
custom_priority_queue: 0 1 2 3 4 5 6 7 8 9
lambda_priority_queue: 8 9 6 7 4 5 2 3 0 1

[編集] 欠陥レポート

以下の動作変更を伴う欠陥報告が、以前に公開されたC++標準に遡って適用されました。

DR 適用対象 公開された動作 正しい動作
LWG 307 C++98 Containerはstd::vector<bool>にはなれません 許可
LWG 2566 C++98 Container::value_typeの要件がありません TがContainer::value_typeと同じ型でない場合、不正形式
LWG 2684 C++98 priority_queueは比較子を受け取りますが、
それに対応するメンバtypedefがありません		 追加された

[編集] 関連項目

 リサイズ可能な連続配列
(クラステンプレート) [編集]
 空間効率の良い動的ビットセット
(class template specialization) [編集]
 両端キュー
(クラステンプレート) [編集]
「https://ja.cppreference.dev/mwiki/index.php?title=cpp/container/priority_queue&oldid=180915」から取得
English 日本語 中文(简体) 中文(繁體)