std::priority_queue
来自cppreference.com
定义于头文件 <queue>
|
||
template< class T, |
||
priority_queue 是容器适配器,它提供常数时间的(默认)最大元素查找,对数代价的插入与释出。
可用用户提供的 Compare
更改顺序,例如,用 std::greater<T> 将导致最小元素作为 top() 出现。
用 priority_queue
工作类似管理某些随机访问容器中的堆,优势是不可能突然把堆非法化。
模板形参
T | - | 存储的元素类型。若 T 与 Container::value_type 不是同一类型则行为未定义。 (C++17 起)
|
Container | - | 用于存储元素的底层容器类型。容器必须满足序列容器 (SequenceContainer) 的要求,而其迭代器必须满足老式随机访问迭代器 (LegacyRandomAccessIterator) 的要求。另外,它必须提供拥有通常语义的下列函数:
标准容器 std::vector 和 std::deque 满足这些要求。 |
Compare | - | 提供严格弱序的比较 (Compare) 类型。 |
注意比较 (Compare) 形参的定义,使得若其第一参数在弱序中先于其第二参数则返回 true 。但因为 priority_queue 首先输出最大元素,故“先来”的元素实际上最后输出。即队列头含有按照比较 (Compare) 所施加弱序的“最后”元素。
成员类型
成员类型 | 定义 |
container_type
|
Container |
value_compare
|
Compare
|
value_type
|
Container::value_type |
size_type
|
Container::size_type |
reference
|
Container::reference |
const_reference
|
Container::const_reference |
成员函数
构造 priority_queue (公开成员函数) | |
析构 priority_queue (公开成员函数) | |
赋值给容器适配器 (公开成员函数) | |
元素访问 | |
访问栈顶元素 (公开成员函数) | |
容量 | |
检查底层容器是否为空 (公开成员函数) | |
返回容纳的元素数 (公开成员函数) | |
修改器 | |
插入元素,并对底层容器排序 (公开成员函数) | |
(C++11) |
原位构造元素并排序底层容器 (公开成员函数) |
删除队首元素 (公开成员函数) | |
(C++11) |
交换内容 (公开成员函数) |
成员对象 | |
Container c |
底层容器 (受保护成员对象) |
Compare comp |
比较函数对象 (受保护成员对象) |
非成员函数
特化 std::swap 算法 (函数模板) |
辅助类
特化 std::uses_allocator 类型特征 (类模板特化) |
推导指引(C++17 起)
示例
运行此代码
#include <functional> #include <queue> #include <vector> #include <iostream> template<typename T> void print_queue(T& q) { while(!q.empty()) { std::cout << q.top() << " "; q.pop(); } std::cout << '\n'; } int main() { std::priority_queue<int> q; for(int n : {1,8,5,6,3,4,0,9,7,2}) q.push(n); print_queue(q); std::priority_queue<int, std::vector<int>, std::greater<int> > q2; for(int n : {1,8,5,6,3,4,0,9,7,2}) q2.push(n); print_queue(q2); // 用 lambda 比较元素。 auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); }; std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp); for(int n : {1,8,5,6,3,4,0,9,7,2}) q3.push(n); print_queue(q3); }
输出:
9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 8 9 6 7 4 5 2 3 0 1
缺陷报告
下列更改行为的缺陷报告追溯地应用于以前出版的 C++ 标准。
DR | 应用于 | 出版时的行为 | 正确行为 |
---|---|---|---|
LWG 2684 | C++98 | priority_queue 接收比较器但缺少对它的成员 typedef
|
已添加 |