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 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 起)

从多种数据源构造容器适配器的底层容器。

1) 默认构造函数。值初始化底层容器。
2)compare 的内容复制构造比较函数对象 comp 。值初始化底层容器 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)
5) 复制构造函数。以 other.c 的内容复制构造底层容器。以 other.comp 复制构造比较函数对象。 (隐式声明)
6) 移动构造函数。以 std::move(other.c) 构造底层容器。以 std::move(other.comp) 构造比较函数对象。 (隐式声明)
7-9) 迭代器对构造函数。这些重载仅若 InputIt 满足老式输入迭代器 (LegacyInputIterator) 才参与重载决议。
7) 如同用 c(first, last) 构造 c 并从 compare 构造 comp ,然后调用 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)std::move(cont) 移动构造 c 并从 compare 复制构造 comp 。然后调用 c.insert(c.end(), first, last); ,再调用 std::make_heap(c.begin(), c.end(), comp);
10-15) 分配器扩展构造函数。这些重载仅若 std::uses_allocator<container_type, Alloc>::valuetrue ,即底层容器为知分配器容器(对所有标准库容器为真)才参与重载决议。
10)alloc 为分配器构造底层容器。等效地调用 c(alloc) 。值初始化 comp
11)alloc 为分配器构造底层容器。等效地调用 c(alloc) 。从 compare 复制构造 comp
12)cont 的内容,以 alloc 为分配器构造底层容器,如同用 c(cont, alloc) 。从 compare 复制构造 comp 。然后调用 std::make_heap(c.begin(), c.end(), comp)
13)cont 的内容,以 alloc 为分配器并以移动语义构造底层容器,如同用 c(std::move(cont), alloc) 。从 compare 复制构造 comp 。然后调用 std::make_heap(c.begin(), c.end(), comp)
14)other.c 的内容,以 alloc 为分配器构造底层容器。等效地调用 c(other.c, alloc) 。从 other.comp 复制构造 comp
15)other 的内容,同时以 alloc 为分配器构造适配器。等效地调用 c(std::move(other.c), alloc) 。从 other.comp 移动构造 comp
16-19) 分配器扩展迭代器对构造函数,同 (7-9) ,除了用 alloc 构造底层容器。这些重载仅若 std::uses_allocator<container_type, Alloc>::valuetrueInputIt 满足老式输入迭代器 (LegacyInputIterator) 才参与重载决议。

参数

alloc - 用于底层容器所有内存分配的分配器
other - 用作源初始化底层容器的另一容器适配器
cont - 用作源初始化底层容器的容器
compare - 用于初始化底层比较函数对象的比较函数对象
first, last - 要初始化的元素范围
类型要求
-
Alloc 必须满足分配器 (Allocator) 的要求。
-
Container 必须满足容器 (Container) 的要求。仅若 Container 满足知分配器容器 (AllocatorAwareContainer) 的要求才定义分配器扩展构造函数
-
InputIt 必须满足老式输入迭代器 (LegacyInputIterator) 的要求。

复杂度

1-2) 常数。
3,12) O(N) 次比较和 O(N)value_type 构造函数调用,其中 Ncont.size()
4) O(N) 次比较,其中 Ncont.size()
6) 常数。
7,16-17) O(M) 次比较,其中 Mstd::distance(first, last)
8,18) O(N+M) 次比较和 O(N)value_type 构造函数调用,其中 NM 分别为 cont.size()std::distance(first, last)
9) O(N) 次比较,其中 Ncont.size() + std::distance(first, last)
10-11) 常数。
12) O(N) 次比较和 O(N)value_type 构造函数调用,其中 Ncont.size()
13) O(N) 次比较,其中 Ncont.size()
14)other 的大小成线性。
15)Allocother 的分配器比较相等则为常数。否则与 other 的大小成线性。
19) O(N+M) 次比较与可能存在的 O(N)value_type 构造函数调用(若 Allocother 的分配器比较不相等则存在),其中 NM 分别为 cont.size()std::distance(first, last)

示例

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

输出:

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 使之为隐式
LWG 3506 C++11 分配器扩展迭代器对构造函数缺失 已添加
LWG 3522 C++11 迭代器对构造函数上的约束缺失 已添加
LWG 3529 C++11 从一对迭代器构造调用 insert 从它们构造容器

参阅

赋值给容器适配器
(公开成员函数)