std::priority_queue<T,Container,Compare>::priority_queue
来自cppreference.com
< cpp | container | 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, |
(7) | (C++11 起) |
(8) | ||
template< class InputIt > priority_queue( InputIt first, InputIt last, |
(C++11 前) | |
template< class InputIt > priority_queue( InputIt first, InputIt last, |
(C++11 起) | |
template< class InputIt > priority_queue( InputIt first, InputIt last, |
(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, |
(12) | (C++11 起) |
template< class Alloc > priority_queue( const Compare& compare, Container&& cont, |
(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, |
(17) | (C++11 起) |
template< class InputIt, class Alloc > priority_queue( InputIt first, InputIt last, const Compare& compare, |
(18) | (C++11 起) |
template< class InputIt, class Alloc > priority_queue( InputIt first, InputIt last, const Compare& compare, |
(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) 构造比较函数对象。 (隐式声明)
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>::value 为 true ,即底层容器为知分配器容器(对所有标准库容器为真)才参与重载决议。
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>::value 为 true 且 InputIt
满足老式输入迭代器 (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
构造函数调用,其中 N 为 cont.size() 。4) O(N) 次比较,其中 N 为 cont.size() 。
6) 常数。
10-11) 常数。
12) O(N) 次比较和 O(N) 次
value_type
构造函数调用,其中 N 为 cont.size() 。13) O(N) 次比较,其中 N 为 cont.size() 。
14) 与
other
的大小成线性。15) 若
Alloc
与 other
的分配器比较相等则为常数。否则与 other
的大小成线性。19) O(N+M) 次比较与可能存在的 O(N) 次
value_type
构造函数调用(若 Alloc
与 other
的分配器比较不相等则存在),其中 N 与 M 分别为 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
|
从它们构造容器 |
参阅
赋值给容器适配器 (公开成员函数) |