std::priority_queue<T,Container,Compare>::priority_queue - cppreference.com

<tbody> </tbody> <tbody class="t-dcl-rev t-dcl-rev-num "> </tbody><tbody> </tbody>

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

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); を呼びます。

引数

計算量

1-2) 一定。

3,5) O(N) の比較、ただし N は cont.size() です。

それに加えて O(N) の value_type コンストラクタ呼び出し、ただし N は cont.size() です。

4) O(N) の比較、ただし N は cont.size() です。

6-8) 一定。

9) 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++ 標準に遡って適用されました。

例

#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';
}

カスタム比較関数を使用した例

#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();
    }
}

関連項目