std::priority_queue

来自cppreference.com
< cpp‎ | container
 
C++
 
容器库
 
std::priority_queue
 
在标头 <queue> 定义
template<

    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>

> class priority_queue;

priority_queue 是容器适配器，它提供常数时间的（默认）最大元素查找，对数代价的插入与提取。

可以通过用户提供的 Compare 更改顺序，例如，用 std::greater<T> 将导致最小元素作为 top() 出现。

用 priority_queue 工作类似管理某些随机访问容器中的堆，优势是堆不可能突然失效。

模板形参

T - 存储的元素类型。 T 与 Container::value_type 不是同一类型时行为未定义。
Container - 用于存储元素的底层容器类型。容器必须满足序列容器 (SequenceContainer) 的要求，并且它的迭代器必须满足老式随机访问迭代器 (LegacyRandomAccessIterator) 的要求。另外，它必须提供拥有通常语义的下列函数：
  • front()
  • push_back()
  • pop_back()

标准容器 std::vector（包括 std::vector<bool>）和 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
 比较函数对象
(受保护成员对象)

非成员函数

(C++11)
 特化 std::swap 算法
(函数模板)

辅助类

(C++11)
 特化 std::uses_allocator 类型特征
(类模板特化)

推导指引(C++17 起)

示例

运行此代码
#include <functional>
#include <queue>
#include <vector>
#include <iostream>
#include <string_view>
 
template<typename T>
void print(std::string_view name, T const& q)
{
    std::cout << name << ": \t";
    for (auto const& n : q)
        std::cout << n << ' ';
    std::cout << '\n';
}
 
template<typename Q>
void print_queue(std::string_view name, Q q)
{
    // 注意：按值传递 q，这是因为无法在不清楚队列的情况下遍历 priority_queue 的内容。
    for (std::cout << name << "：\t"; !q.empty(); q.pop())
        std::cout << q.top() << ' ';
    std::cout << '\n';
}
 
int main()
{
    const auto data = {1, 8, 5, 6, 3, 4, 0, 9, 7, 2};
    print("data", data);
 
    std::priority_queue<int> q1; // 最大优先队列
    for (int n : data)
        q1.push(n);
 
    print_queue("q1", q1);
 
    // 最小优先队列
    // std::greater<int> 使得最大优先队列的行为变成最小优先队列的行为
    std::priority_queue<int, std::vector<int>, std::greater<int>>
        minq1(data.begin(), data.end());
 
    print_queue("minq1", minq1);
 
    // 定义最小优先队列的另一种方法
    std::priority_queue minq2(data.begin(), data.end(), std::greater<int>());
 
    print_queue("minq2", minq2);
 
    // 使用自定义的函数对象来比较元素。
    struct
    {
        bool operator() (const int l, const int r) const { return l > r; }
    } customLess;
    std::priority_queue minq3(data.begin(), data.end(), customLess);
 
    print_queue("minq3", minq3);
 
    // 使用 lambda 来比较元素。
    auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
    std::priority_queue<int, std::vector<int>, decltype(cmp)> q5(cmp);
 
    for (int n : data)
        q5.push(n);
 
    print_queue("q5", q5);
}

输出： 

data：	1 8 5 6 3 4 0 9 7 2 
q1：	9 8 7 6 5 4 3 2 1 0 
minq1：	0 1 2 3 4 5 6 7 8 9 
minq2：	0 1 2 3 4 5 6 7 8 9 
minq3：	0 1 2 3 4 5 6 7 8 9 
q5：	8 9 6 7 4 5 2 3 0 1

缺陷报告

下列更改行为的缺陷报告追溯地应用于以前出版的 C++ 标准。

缺陷报告 应用于 出版时的行为 正确行为
LWG 307 C++98 Container 不能是 std::vector<bool> 可以是
LWG 2684 C++98 priority_queue 接收比较器但缺少对它的成员 typedef 已添加

参阅

 动态的连续数组
(类模板)
节省空间的动态 bitset
(类模板特化)
双端队列
(类模板)
来自“https://zh.cppreference.com/mwiki/index.php?title=cpp/container/priority_queue&oldid=76132”