◐ Shell
clean mode source ↗

std::priority_queue - cppreference.com

来自cppreference.com

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

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

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

priority_queue 的作用类似于管理某些随机访问容器中的堆，其优势是不可能意外使堆失效。

std::priority_queue 的全部成员函数均为 constexpr：在常量表达式求值中创建并使用 std::priority_queue 对象是可能的。

然而，定义一个 constexpr std::priority_queue 变量通常是错误，这是因为常量求值要求任何动态分配的存储都要在相同求值中释放，而 std::priority_queue 的初始化器通常不符合这点。

(C++26 起)

模板形参

成员类型

成员 定义
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)

 交换内容
(公开成员函数) [编辑]

成员对象

非成员函数

辅助类

注解

功能特性测试宏 值 标准 功能特性
__cpp_lib_containers_ranges 202202L (C++23) 容器的按范围构造和插入
__cpp_lib_constexpr_queue 202502L (C++26) constexpr std::priority_queue

示例

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

    // 填充优先级队列。
    for (int n : data)
        max_priority_queue.push(n);

    pop_println("max_priority_queue", max_priority_queue);

    // std::greater<int> 使得最大优先队列表现为最小优先队列。
    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);

    // 定义最小优先队列的另一种方法
    std::priority_queue min_priority_queue2(data.begin(), data.end(), std::greater<int>());

    pop_println("min_priority_queue2", min_priority_queue2);

    // 使用自定义的函数对象来比较元素。
    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);

    // 使用 lambda 来比较元素。
    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++ 标准。

缺陷报告 应用于 出版时的行为 正确行为
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 接收比较器但缺少对它的成员 typedef 已添加

参阅