std::priority_queue
来自 cppreference.com
定义在头文件 <queue> 中 |
||
template< class T, |
||
优先级队列 是一个 容器适配器,它以对数插入和提取为代价提供最大(默认)元素的常数时间查找。
可以提供用户提供的 Compare
来更改排序,例如使用 std::greater<T> 将导致最小的元素显示为 top()。
使用 priority_queue
与在一些随机访问容器中管理 堆 类似,好处是无法意外地使堆失效。
内容 |
[编辑] 模板参数
T | - | 存储元素的类型。如果 T 与 Container::value_type 不是同一种类型,则程序格式错误。 |
Container | - | 用于存储元素的底层容器的类型。容器必须满足 SequenceContainer 的要求,其迭代器必须满足 LegacyRandomAccessIterator 的要求。此外,它必须提供以下函数,具有 通常的语义
标准容器 std::vector(包括 |
Compare | - | 提供严格弱排序的 Compare 类型。 注意,Compare 参数的定义方式是,如果它的第一个参数在弱排序中位于第二个参数之前,则返回 true。但由于优先级队列首先输出最大元素,因此“位于之前”的元素实际上是最后输出的。也就是说,队列的头部包含根据 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 |
[编辑] 成员对象
成员名称 | 定义 |
Container c |
底层容器 (受保护成员对象) |
Compare comp |
比较函数对象 (受保护成员对象) |
[编辑] 成员函数
构造 priority_queue (公共成员函数) | |
析构 priority_queue (公共成员函数) | |
将值赋值给容器适配器 (公共成员函数) | |
元素访问 | |
访问顶部元素 (公共成员函数) | |
容量 | |
检查容器适配器是否为空 (公共成员函数) | |
返回元素数量 (公共成员函数) | |
修改器 | |
插入元素并对底层容器进行排序 (公共成员函数) | |
(C++23) |
插入一系列元素并对底层容器进行排序 (公共成员函数) |
(C++11) |
原地构造元素并对底层容器进行排序 (公有成员函数) |
移除顶部元素 (公有成员函数) | |
(C++11) |
交换内容 (公有成员函数) |
[编辑] 非成员函数
专门化了 std::swap 算法 (函数模板) |
[编辑] 辅助类
专门化了 std::uses_allocator 类型特征 (类模板专门化) | |
std::priority_queue 的格式化支持(类模板专门化) |
推导指南 |
(自 C++17 起) |
[编辑] 注释
功能测试 宏 | 值 | Std | 功能 |
---|---|---|---|
__cpp_lib_containers_ranges |
202202L | (C++23) | 范围感知 的容器构造和插入 |
[编辑] 示例
运行此代码
#include <functional> #include <iostream> #include <queue> #include <string_view> #include <vector> template<typename T> void pop_println(std::string_view rem, T& pq) { std::cout << rem << ": "; for (; !pq.empty(); pq.pop()) std::cout << pq.top() << ' '; std::cout << '\n'; } template<typename T> void println(std::string_view rem, const T& v) { std::cout << rem << ": "; for (const auto& e : v) std::cout << e << ' '; std::cout << '\n'; } int main() { const auto data = {1, 8, 5, 6, 3, 4, 0, 9, 7, 2}; println("data", data); std::priority_queue<int> max_priority_queue; // Fill the priority queue. for (int n : data) max_priority_queue.push(n); pop_println("max_priority_queue", max_priority_queue); // std::greater<int> makes the max priority queue act as a min priority queue. std::priority_queue<int, std::vector<int>, std::greater<int>> min_priority_queue1(data.begin(), data.end()); pop_println("min_priority_queue1", min_priority_queue1); // Second way to define a min priority queue. std::priority_queue min_priority_queue2(data.begin(), data.end(), std::greater<int>()); pop_println("min_priority_queue2", min_priority_queue2); // Using a custom function object to compare elements. struct { bool operator()(const int l, const int r) const { return l > r; } } customLess; std::priority_queue custom_priority_queue(data.begin(), data.end(), customLess); pop_println("custom_priority_queue", custom_priority_queue); // Using lambda to compare elements. auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); }; std::priority_queue<int, std::vector<int>, decltype(cmp)> lambda_priority_queue(cmp); for (int n : data) lambda_priority_queue.push(n); pop_println("lambda_priority_queue", lambda_priority_queue); }
输出
data: 1 8 5 6 3 4 0 9 7 2 max_priority_queue: 9 8 7 6 5 4 3 2 1 0 min_priority_queue1: 0 1 2 3 4 5 6 7 8 9 min_priority_queue2: 0 1 2 3 4 5 6 7 8 9 custom_priority_queue: 0 1 2 3 4 5 6 7 8 9 lambda_priority_queue: 8 9 6 7 4 5 2 3 0 1
[编辑] 错误报告
以下行为更改缺陷报告被追溯应用于先前发布的 C++ 标准。
DR | 应用于 | 已发布的行为 | 正确行为 |
---|---|---|---|
LWG 307 | C++98 | Container 不能是 std::vector<bool> |
允许 |
LWG 2566 | C++98 | 缺少 Container::value_type 的要求 |
如果 T 与 Container::value_type 类型不同,则为不合格 |
LWG 2684 | C++98 | priority_queue 采用比较器但缺少其成员类型定义 |
添加 |
[编辑] 另见
动态连续数组 (类模板) | |
空间效率高的动态位集 (类模板专门化) | |
双端队列 (类模板) |