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

提供: cppreference.com

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 Alloc > explicit priority_queue( const Alloc& alloc );		(7)	(C++11以上)
template< class Alloc > priority_queue( const Compare& compare, const Alloc& alloc );		(8)	(C++11以上)
template< class Alloc > priority_queue( const Compare& compare, const Container& cont, const Alloc& alloc );		(9)	(C++11以上)
template< class Alloc > priority_queue( const Compare& compare, Container&& cont, const Alloc& alloc );		(10)	(C++11以上)
template< class Alloc > priority_queue( const priority_queue& other, const Alloc& alloc );		(11)	(C++11以上)
template< class Alloc > priority_queue( priority_queue&& other, const Alloc& alloc );		(12)	(C++11以上)
template< class InputIt > priority_queue( InputIt first, InputIt last, const Compare& compare, const Container& cont );		(13)	(C++11以上)
template< class InputIt > priority_queue( InputIt first, InputIt last, const Compare& compare = Compare(), Container&& cont = Container() );		(14)	(C++11以上)

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

1) デフォルトコンストラクタ。比較子およびベースとなるコンテナを値初期化します。

2) 比較子 comp を compare の内容でコピー構築します。ベースとなる c を値初期化します。

3) cont の内容でベースとなるコンテナ c をコピー構築します。 compare の内容から比較関数オブジェクト comp をコピー構築します。 std::make_heap(c.begin(), c.end(), comp) を呼びます。これはデフォルトコンストラクタでもあります。 (C++11未満)

4) std::move(cont) でベースとなるコンテナ c をムーブ構築します。 compare の内容から比較関数オブジェクト comp をコピー構築します。 std::make_heap(c.begin(), c.end(), comp) を呼びます。これはデフォルトコンストラクタでもあります。 (C++11以上)

5) コピーコンストラクタ。アダプタは other.c の内容でコピー構築されます。比較関数オブジェクトは std::move(other.comp) で構築されます。 (暗黙に宣言)

6) ムーブコンストラクタ。アダプタは std::move(other.c) で構築されます。比較関数オブジェクトは std::move(other.comp) で構築されます。 (暗黙に宣言)

7-12) 以下のコンストラクタは std::uses_allocator<container_type, Alloc>::value == true、つまりベースとなるコンテナがアロケータ対応コンテナの場合にのみ定義されます (標準ライブラリのコンテナはすべて対応しています)。

7) alloc をアロケータとして使用してベースとなるコンテナを構築します。実質的に c(alloc) を呼びます。 comp は値初期化されます。

8) alloc をアロケータとして使用してベースとなるコンテナを構築します。実質的に c(alloc) を呼びます。 comp は compare からコピー構築します。

9) c(cont, alloc) を呼んだかのように、 alloc をアロケータとして使用して cont の内容でベースとなるコンテナを構築します。 comp は compare からコピー構築されます。その後 std::make_heap(c.begin(), c.end(), comp) を呼びます。

10) c(std::move(cont), alloc) を呼んだかのように、 alloc をアロケータとして使用し、ムーブセマンティクスを用いて、 cont の内容でベースとなるコンテナを構築します。 comp は compare からコピー構築されます。その後 std::make_heap(c.begin(), c.end(), comp) を呼びます。

11) alloc をアロケータとして使用して other.c の内容でアダプタを構築します。実質的に c(other.c, alloc) を呼びます。 comp は other.comp からコピー構築されます。

12) alloc をアロケータとして使用してムーブセマンティクスを用いて other の内容でアダプタを構築します。実質的に c(std::move(other.c), alloc) を呼びます。 comp は other.comp からムーブ構築されます。

13) c を cont から、 comp を compare からコピー構築します。その後 c.insert(c.end(), first, last); を呼び、その後 std::make_heap(c.begin(), c.end(), comp); を呼びます。

14) c を std::move(cont) から、 comp を std::move(compare) からムーブ構築します。その後 c.insert(c.end(), first, last); を呼び、その後 std::make_heap(c.begin(), c.end(), comp); を呼びます。

alloc	-	ベースとなるコンテナのすべてのメモリ確保に使用するアロケータ
other	-	ベースとなるコンテナを初期化するためのソースとして使用される別のコンテナアダプタ
cont	-	ベースとなるコンテナを初期化するためのソースとして使用されるコンテナ
compare	-	ベースとなる比較関数オブジェクトを初期化するための比較関数オブジェクト
first, last	-	初期化するための要素の範囲
型の要件
- `Alloc` は Allocator の要件を満たさなければなりません。
- `Container` は Container の要件を満たさなければなりません。コンストラクタ (5-10) は `Container` が AllocatorAwareContainer の要件を満たす場合のみ定義されます。
- `InputIt` は LegacyInputIterator の要件を満たさなければなりません。

[編集] 計算量

1-2) 一定。

3,5)

O(N)

の比較、ただし

N

は cont.size() です。

それに加えて

O(N)

の value_type コンストラクタ呼び出し、ただし

N

は cont.size() です。

O(N)

の比較、ただし

N

は cont.size() です。

6-8) 一定。

O(N)

の比較、ただし

N

は cont.size() です。

それに加えて

O(N)

の value_type コンストラクタ呼び出し、ただし

N

は cont.size() です。

10)

O(N)

の比較、ただし

N

は cont.size() です。

11) other のサイズに比例。

12) 一定。

13)

O(N)

の比較、ただし

N

は cont.size() + std::distance(first, last) です。

それに加えて

O(N)

の value_type コンストラクタ呼び出し、ただし

N

は cont.size() です。

14)

O(N)

の比較、ただし

N

は cont.size() + std::distance(first, last) です。

[編集] 欠陥報告

以下の動作変更欠陥報告は以前に発行された C++ 標準に遡って適用されました。

DR	適用先	発行時の動作	正しい動作
P0935R0	C++11	default constructor and constructor (4) were explicit	made implicit

[編集] 例

Run this code

#include <queue>
#include <vector>
#include <iostream>
#include <functional>
 
int main()
{
    std::priority_queue<int> c1;
    c1.push(5);
    std::cout << c1.size() << '\n';
 
    std::priority_queue<int> c2(c1);
    std::cout << c2.size() << '\n';
 
    std::vector<int> vec={3, 1, 4, 1, 5};
    std::priority_queue<int> c3(std::less<int>(), vec);
    std::cout << c3.size() << '\n';
}

出力:

1
1
5

[編集] カスタム比較関数を使用した例

Run this code

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
 
using my_pair_t = std::pair<size_t,bool>;
 
using my_container_t = std::vector<my_pair_t>;
 
int main()
{
    auto my_comp =
        [](const my_pair_t& e1, const my_pair_t& e2) 
        { return e1.first > e2.first; };
    std::priority_queue<my_pair_t,
                        my_container_t,
                        decltype(my_comp)> queue(my_comp);
    queue.push(std::make_pair(5, true));
    queue.push(std::make_pair(3, false));
    queue.push(std::make_pair(7, true));
    std::cout << std::boolalpha;
    while(!queue.empty()) 
    {
        const auto& p = queue.top();
        std::cout << p.first << " " << p.second << "\n";
        queue.pop();
    }
}

出力:

3 false
5 true
7 true

[編集] 関連項目

operator=

コンテナアダプタに値を代入します
(パブリックメンバ関数) [edit]

「https://ja.cppreference.com/mwiki/index.php?title=cpp/container/priority_queue/priority_queue&oldid=40338」から取得

言語
標準ライブラリヘッダ
フリースタンディング処理系とホスト処理系
名前付き要件
言語サポートライブラリ
コンセプトライブラリ (C++20)
診断ライブラリ
ユーティリティライブラリ
文字列ライブラリ
コンテナライブラリ
イテレータライブラリ
範囲ライブラリ (C++20)
アルゴリズムライブラリ
数値演算ライブラリ
ローカライゼーションライブラリ
入出力ライブラリ
ファイルシステムライブラリ (C++17)
正規表現ライブラリ (C++11)
アトミック操作ライブラリ (C++11)
スレッドサポートライブラリ (C++11)
技術仕様書

array (C++11)
vector
deque
forward_list (C++11)
list
set
multiset
map
multimap
unordered_set (C++11)
unordered_multiset (C++11)
unordered_map (C++11)
unordered_multimap (C++11)
stack
queue
priority_queue
span (C++20)

メンバ関数
priority_queue::priority_queue
priority_queue::~priority_queue
priority_queue::operator=
要素アクセス
priority_queue::top
容量
priority_queue::empty
priority_queue::size
変更
priority_queue::push
priority_queue::emplace
priority_queue::pop
priority_queue::swap
推定ガイド(C++17)

cppreference.com

名前空間

変種

表示

操作

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

目次

[編集] 引数

[編集] 計算量

[編集] 欠陥報告

[編集] 例

[編集] カスタム比較関数を使用した例

[編集] 関連項目

案内

ツールボックス