Namespaces
Variants

std::priority_queue<T,Container,Compare>:: priority_queue

From cppreference.net
C++
Containers library
std::priority_queue
priority_queue ( ) : priority_queue ( Compare ( ) , Container ( ) ) { }
(1) (C++11以降)
explicit priority_queue ( const Compare & compare )
: priority_queue ( compare, Container ( ) ) { }
(2) (C++11以降)
(3)
explicit priority_queue ( const Compare & compare = Compare ( ) ,
const Container & cont = Container ( ) ) ;
(C++11まで)
priority_queue ( const Compare & compare, const Container & cont ) ;
(C++11以降)
priority_queue ( const Compare & compare, Container && cont ) ;
(4) (C++11以降)
priority_queue ( const priority_queue & other ) ;
(5)
priority_queue ( priority_queue && other ) ;
(6) (C++11以降)
template < class InputIt >

priority_queue ( InputIt first, InputIt last,

const Compare & compare = Compare ( ) ) ;
(7) (C++11以降)
(8)
template < class InputIt >

priority_queue ( InputIt first, InputIt last,
const Compare & compare = Compare ( ) ,

const Container & cont = Container ( ) ) ;
(C++11まで)
template < class InputIt >

priority_queue ( InputIt first, InputIt last,

const Compare & compare, const Container & cont ) ;
(C++11以降)
template < class InputIt >

priority_queue ( InputIt first, InputIt last,

const Compare & compare, Container && cont ) ;
(9) (C++11以降)
template < class Alloc >
explicit priority_queue ( const Alloc & alloc ) ;
(10) (C++11以降)
template < class Alloc >
priority_queue ( const Compare & compare, const Alloc & alloc ) ;
(11) (C++11以降)
template < class Alloc >

priority_queue ( const Compare & compare, const Container & cont,

const Alloc & alloc ) ;
(12) (C++11以降)
template < class Alloc >

priority_queue ( const Compare & compare, Container && cont,

const Alloc & alloc ) ;
(13) (C++11以降)
template < class Alloc >
priority_queue ( const priority_queue & other, const Alloc & alloc ) ;
(14) (C++11以降)
template < class Alloc >
priority_queue ( priority_queue && other, const Alloc & alloc ) ;
(15) (C++11以降)
template < class InputIt, class Alloc >
priority_queue ( InputIt first, InputIt last, const Alloc & alloc ) ;
(16) (C++11以降)
template < class InputIt, class Alloc >

priority_queue ( InputIt first, InputIt last, const Compare & compare,

const Alloc & alloc ) ;
(17) (C++11以降)
template < class InputIt, class Alloc >

priority_queue ( InputIt first, InputIt last, const Compare & compare,

const Container & cont, const Alloc & alloc ) ;
(18) (C++11以降)
template < class InputIt, class Alloc >

priority_queue ( InputIt first, InputIt last, const Compare & compare,

Container && cont, const Alloc & alloc ) ;
(19) (C++11以降)
template < container-compatible-range < T > R >

priority_queue ( std:: from_range_t , R && rg,

const Compare & compare = Compare ( ) ) ;
(20) (C++23以降)
template < container-compatible-range < T > R, class Alloc >

priority_queue ( std:: from_range_t , R && rg,

const Compare & compare, const Alloc & alloc ) ;
(21) (C++23以降)
template < container-compatible-range < T > R, class Alloc >
priority_queue ( std:: from_range_t , R && rg, const Alloc & alloc ) ;
(22) (C++23以降)

コンテナアダプタの基盤となる新しいコンテナを、様々なデータソースから構築します。

1) デフォルトコンストラクタ。コンパレータと基底コンテナを値初期化します。
2) 比較関数オブジェクト comp を compare の内容でコピー構築する。基となるコンテナ c を値初期化する。
3) 基となるコンテナ c を cont の内容でコピー構築します。比較関数オブジェクト comp を compare の内容でコピー構築します。 std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) を呼び出します。 これはデフォルトコンストラクタでもあります。 (C++11以前)
4) 基となるコンテナ c を std :: move ( cont ) でムーブ構築します。比較関数オブジェクト comp を compare でコピー構築します。 std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) を呼び出します。
5) コピーコンストラクタ . 基となるコンテナは other. c でコピー構築されます。比較関数オブジェクトは other. comp でコピー構築されます。 (暗黙的に宣言される)
6) Move constructor . 基となるコンテナは std :: move ( other. c ) で構築されます。比較関数オブジェクトは std :: move ( other. comp ) で構築されます。 (暗黙的に宣言)
7-9) イテレータペアコンストラクタ。これらのオーバーロードは、 InputIt が LegacyInputIterator を満たす場合にのみ、オーバーロード解決に参加します。
7) c を c ( first, last ) によって構築し、 comp を compare から構築する。その後、 std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) ; を呼び出す。
8) cont から c をコピー構築し、 compare から comp をコピー構築します。その後、 c. insert ( c. end ( ) , first, last ) ; を呼び出し、続いて std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) ; を呼び出します。
9) c を std :: move ( cont ) からムーブ構築し、 comp を compare からコピー構築します。その後、 c. insert ( c. end ( ) , first, last ) ; を呼び出し、続いて std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) ; を呼び出します。
10-15) アロケータ拡張コンストラクタ。これらのオーバーロードは、以下の条件が満たされる場合にのみオーバーロード解決に参加します： std:: uses_allocator < container_type, Alloc > :: value が true である場合、つまり基盤となるコンテナがアロケータ対応コンテナである場合です（標準ライブラリのすべてのコンテナでtrueとなります）。
10) 基盤となるコンテナを alloc をアロケータとして使用して構築します。実質的に c ( alloc ) を呼び出します。 comp は値初期化されます。
11) 基となるコンテナを alloc をアロケータとして使用して構築します。実質的に c ( alloc ) を呼び出します。 comp を compare からコピー構築します。
12) 基となるコンテナを cont の内容とアロケータ alloc を使用して構築します（ c ( cont, alloc ) のように）。次に comp を compare からコピー構築します。その後 std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) を呼び出します。
13) ムーブセマンティクスを使用して cont の内容と alloc をアロケータとして基盤となるコンテナを構築します。具体的には c ( std :: move ( cont ) , alloc ) のように行われます。 comp を compare からコピー構築します。その後 std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) を呼び出します。
14) 基となるコンテナを other. c の内容と alloc をアロケータとして使用して構築します。実質的に c ( other. c , alloc ) を呼び出します。 comp を other. comp からコピー構築します。
15) ムーブセマンティクスを使用して other の内容で基盤となるコンテナを構築し、 alloc をアロケータとして使用します。実質的に c ( std :: move ( other. c ) , alloc ) を呼び出します。 comp を other. comp からムーブ構築します。
16-19) アロケータ拡張イテレータペアコンストラクタ。 (7-9) と同じですが、 alloc が基底コンテナの構築に使用されます。これらのオーバーロードは、 std:: uses_allocator < container_type, Alloc > :: value が true であり、かつ InputIt が LegacyInputIterator を満たす場合にのみ、オーバーロード解決に参加します。
20) comp を compare で初期化し、 c を ranges:: to < Container > ( std:: forward < R > ( rg ) ) で初期化します。その後、 std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) を呼び出します。
21) comp を compare で初期化し、 c を ranges:: to < Container > ( std:: forward < R > ( rg ) , alloc ) で初期化します。その後、 std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) を呼び出します。
22) c を ranges:: to < Container > ( std:: forward < R > ( rg ) , alloc ) で初期化します。その後、 std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) を呼び出します。

実装が型が LegacyInputIterator を満たすかどうかをチェックする方法は未規定であるが、整数型は拒否されることが要求されることに注意してください。

目次

パラメータ

alloc - 基盤となるコンテナの全てのメモリ割り当てに使用するアロケータ
other - 基盤となるコンテナを初期化するためのソースとして使用する別のコンテナアダプタ
cont - 基盤となるコンテナを初期化するためのソースとして使用するコンテナ
compare - 基盤となる比較ファンクタを初期化するための比較関数オブジェクト
first, last - 初期化する要素の 範囲 を定義するイテレータのペア
rg - コンテナ互換範囲 、すなわち要素が T に変換可能な input_range
型要件
-
Alloc は Allocator の要件を満たさなければならない。
-
Compare は Compare の要件を満たさなければならない。
-
Container は Container の要件を満たさなければならない。アロケータ拡張コンストラクタは、 Container が AllocatorAwareContainer の要件を満たす場合にのみ定義される。
-
InputIt は LegacyInputIterator の要件を満たさなければならない。

計算量

1,2) 定数。
3,5,12) O(N) 回の比較と O(N) 回の value_type コンストラクタ呼び出し。ここで N は cont. size ( ) である。
4) O(N) 回の比較、ここで N は cont. size ( ) です。
6) 定数。
7,16,17) O(M) 回の比較。ここで M は std:: distance ( first, last ) である。
8,18) O(N + M) 回の比較と O(N) 回の value_type コンストラクタ呼び出し。ここで N は cont. size ( ) 、 M は std:: distance ( first, last ) である。
9) O(N + M) 回の比較。ここで N は cont. size ( ) 、 M は std:: distance ( first, last ) である。
10,11) 定数。
13) O(N) 回の比較、ここで N は cont. size ( ) です。
14) サイズは other に対して線形。
15) Alloc が other のアロケータと等しく比較される場合は定数時間。 それ以外の場合は other のサイズに対して線形時間。
19) O(N + M) 回の比較と、場合によっては O(N) 回の value_type のコンストラクタ呼び出し（ Alloc が other のアロケータと等しくない場合に発生）が発生します。ここで N は cont. size ( ) であり、 M は std:: distance ( first, last ) です。
20) O(N) 回の比較と O(N) 回の value_type コンストラクタ呼び出し。ここで N は ranges:: distance ( rg ) である。
21,22)
このセクションは不完全です

注記

機能テスト マクロ 値 標準 機能
__cpp_lib_containers_ranges 202202L (C++23) Ranges-aware 構築と挿入; オーバーロード ( 20-22 )

例

このコードを実行 
#include <complex>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
int main()
{
    std::priority_queue<int> pq1;
    pq1.push(5);
    std::cout << "pq1.size() = " << pq1.size() << '\n';
    std::priority_queue<int> pq2 {pq1};
    std::cout << "pq2.size() = " << pq2.size() << '\n';
    std::vector<int> vec {3, 1, 4, 1, 5};
    std::priority_queue<int> pq3 {std::less<int>(), vec};
    std::cout << "pq3.size() = " << pq3.size() << '\n';
    for (std::cout << "pq3 : "; !pq3.empty(); pq3.pop())
        std::cout << pq3.top() << ' ';
    std::cout << '\n';
    // カスタム比較関数を使用したデモ:
    using my_value_t = std::complex<double>;
    using my_container_t = std::vector<my_value_t>;
    auto my_comp = [](const my_value_t& z1, const my_value_t& z2)
    {
        return z2.real() < z1.real();
    };
    std::priority_queue<my_value_t,
                        my_container_t,
                        decltype(my_comp)> pq4{my_comp};
    using namespace std::complex_literals;
    pq4.push(5.0 + 1i);
    pq4.push(3.0 + 2i);
    pq4.push(7.0 + 3i);
    for (; !pq4.empty(); pq4.pop())
    {
        const auto& z = pq4.top();
        std::cout << "pq4.top() = " << z << '\n';
    }
    // TODO: C++23 レンジ対応コンストラクタ
}

出力: 

pq1.size() = 1
pq2.size() = 1
pq3.size() = 5
pq3 : 5 4 3 1 1
pq4.top() = (3,2)
pq4.top() = (5,1)
pq4.top() = (7,3)

欠陥報告

以下の動作変更の欠陥報告書は、以前に公開されたC++規格に対して遡及的に適用されました。

DR 適用バージョン 公開時の動作 正しい動作
P0935R0 C++11 デフォルトコンストラクタとコンストラクタ (4) がexplicitであった 暗黙的(implicit)に変更
LWG 3506 C++11 アロケータ拡張イテレータペアコンストラクタが欠落していた 追加
LWG 3522 C++11 イテレータペアコンストラクタの制約が欠落していた 追加
LWG 3529 C++11 イテレータペアからの構築が insert を呼び出していた イテレータペアからコンテナを構築する

関連項目

コンテナアダプタに値を代入する
(公開メンバ関数)