std::priority_queue
提供: cppreference.com
ヘッダ <queue> で定義 | ||
template< class T, | ||
優先度付きキューは (デフォルトでは) 最も大きな要素を定数時間で提供するコンテナアダプタです。 挿入および抽出は対数時間を要します。
順序を変更するためにユーザ提供の Compare を提供できます。 例えば std::greater<T> を使うと top() に最も小さな要素が現れるようになります。
priority_queue を用いるのは、何らかのランダムアクセスコンテナを使ってヒープを管理するのと同様ですが、誤ってヒープを壊さずに済むという利点があります。
目次 |
[編集]テンプレート引数
| T | - | 格納される要素の型。 T と Container::value_type が同じ型でない場合、動作は未定義です。(C++17以上) |
| Container | - | 要素を格納するために使用するベースとなるコンテナの型。 コンテナは SequenceContainer の要件を満たさなければならず、そのイテレータは LegacyRandomAccessIterator の要件を満たさなければなりません。 さらに、通常のセマンティクスを持つ以下の関数を提供していなければなりません。
標準のコンテナ std::vector および std::deque はこれらの要件を満たします。 |
| Compare | - | 狭義弱順序を提供する Compare 型。 |
Compare 引数は弱順序で第1引数が第2引数よりも前に来る場合に true を返すように定義されていることに注意してください。 しかし優先度付きキューは最も大きな要素を最初に出力するため、「前に来る」要素は実際には最後に出力されます。 つまり、 Compare によって定められる弱順序に従って「最後」の要素がキューの先頭に格納されます。
[編集]メンバ型
| メンバ型 | 定義 |
container_type | Container |
value_compare(C++17) | Compare |
value_type | Container::value_type |
size_type | Container::size_type |
reference | Container::reference |
const_reference | Container::const_reference |
[編集]メンバ関数
priority_queue を構築します (パブリックメンバ関数) | |
priority_queue を破棄します (パブリックメンバ関数) | |
| コンテナアダプタに値を代入します (パブリックメンバ関数) | |
要素アクセス | |
| トップの要素にアクセスします (パブリックメンバ関数) | |
容量 | |
| ベースとなるコンテナが空かどうか調べます (パブリックメンバ関数) | |
| 要素数を返します (パブリックメンバ関数) | |
変更 | |
| 要素を挿入してベースとなるコンテナをソートします (パブリックメンバ関数) | |
(C++11) | 要素をその場で構築してベースとなるコンテナをソートします (パブリックメンバ関数) |
| トップの要素を削除します (パブリックメンバ関数) | |
(C++11) | 内容を入れ替えます (パブリックメンバ関数) |
メンバオブジェクト | |
Container c | ベースとなるコンテナ (プロテクテッドメンバオブジェクト) |
Compare comp | 比較関数オブジェクト (プロテクテッドメンバオブジェクト) |
[編集]非メンバ関数
| std::swap アルゴリズムの特殊化 (関数テンプレート) |
[編集]ヘルパークラス
| std::uses_allocator 型特性の特殊化 (関数テンプレート) |
[編集]推定ガイド(C++17以上)
[編集]例
Run this code
#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); // 要素を比較するためにラムダを使用。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
