Namespaces
Variants

std:: priority_queue

From cppreference.net
C++
Containers library
std::priority_queue
定义于头文件 <queue>
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 对象。

但 std::priority_queue 对象本身通常不能是 constexpr ，因为任何动态分配的存储都必须在同一常量表达式求值过程中释放。

(since C++26)

目录

模板参数

T - 存储元素的类型。若 T 与 Container::value_type 不是同一类型，则程序非良构。
Container - 用于存储元素的底层容器类型。该容器必须满足 SequenceContainer 要求，其迭代器必须满足 LegacyRandomAccessIterator 要求。此外，必须提供以下具有 常规语义 的函数：

标准容器 std::vector （不包括 std::vector<bool> ）和 std::deque 满足这些要求。

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)
交换内容
(公开成员函数)

非成员函数

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

辅助类

(C++11)
特化 std::uses_allocator 类型特征
(类模板特化)
(C++23)
std::priority_queue 的格式化支持
(类模板特化)

推导指引

(C++17 起)

注释

功能测试 宏 值 标准 功能特性
__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 接受比较器
但缺少对应的成员类型定义 		已添加

参见

可调整大小的连续数组
(类模板)
空间优化的动态位集
(类模板特化)
双端队列
(类模板)