priority_queue 容器适配器（仿函数运用）

是 C++ 标准模板库（STL）中提供的容器适配器（Container Adapter）。它并不是一种独立的数据结构，而是基于其他序列容器（默认为）构建的，通过堆（Heap）算法来维护元素的顺序，确保优先级最高的元素始终位于队首。与普通队列（FIFO，先进先出）不同，优先队列中的元素出队顺序完全取决于它们的优先级，而非插入顺序。的定义如下：2. 模板参数详解的模板定义包含三个关键参数：

睡一觉就好了。

72人浏览 · 2026-03-07 00:20:43

睡一觉就好了。 · 2026-03-07 00:20:43 发布

C++ `std::priority_queue` 容器适配器详解

std::priority_queue 是 C++ 标准模板库（STL）中提供的容器适配器（Container Adapter）。它并不是一种独立的数据结构，而是基于其他序列容器（默认为 std::vector）构建的，通过堆（Heap）算法来维护元素的顺序，确保优先级最高的元素始终位于队首。

与普通队列（FIFO，先进先出）不同，优先队列中的元素出队顺序完全取决于它们的优先级，而非插入顺序。

1. 核心特性

特性	说明
逻辑结构	堆（Heap）。默认是大根堆（Max-Heap），即最大值在顶部；也可配置为小根堆。
底层容器	默认使用 `std::vector`，也可指定为 `std::deque`。不支持 `std::list`（因为 list 不支持随机访问，而堆算法需要）。
访问限制	只能访问堆顶元素。不支持遍历、随机访问或修改中间元素。
时间复杂度	插入 (`push`) 和删除堆顶 (`pop`) 均为 $O(log⁡N)O(\log N)$ ；获取堆顶 (`top`) 为 $O (1)$ 。
头文件	`#include <queue>`

2. 模板定义与参数

priority_queue 的定义如下：

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

2. 模板参数详解

std::priority_queue 的模板定义包含三个关键参数：

T (元素类型)

说明：存储在队列中的数据类型。

Container (底层容器类型)

默认值：std::vector<T>
作用：实际存储数据的容器。必须是支持随机访问迭代器的序列容器。
可选值：std::deque<T>
注意：不能使用 std::list。
- 原因：堆算法（Heap Algorithm）需要通过下标快速计算并访问父节点和子节点（索引公式通常为 2*i+1 和 2*i+2），而链表不支持 $O (1)$ 的随机访问。

Compare (比较函数对象/仿函数)

默认值：std::less<T>
作用：定义元素的优先级规则。
关键逻辑（这是最容易混淆的部分）：
- std::less<T>（默认）：
  - 含义：表示“小于”关系。
  - 行为：在优先队列内部，如果 comp(a, b) 返回 true（即 a < b），则认为 b 的优先级更高，b 会浮到堆顶。
  - 结果：大根堆（最大值在顶部）。
- std::greater<T>：
  - 含义：表示“大于”关系。
  - 行为：如果 comp(a, b) 返回 true（即 a > b），则认为 b 的优先级更高（意味着较小的值会浮上来）。
  - 结果：小根堆（最小值在顶部）。
- 自定义：可以传入自定义的仿函数（Functor）或 Lambda 表达式，以实现复杂的优先级逻辑（例如比较结构体的特定成员、比较指针指向的内容等）。

struct TaskCompare {
bool operator()(const Task& a, const Task& b) const {
    if (a.priority != b.priority) {
        // 优先级不同：数值大的应该“沉”下去（返回 true，表示 a < b，b 优先）
        // 这样数值小的就会浮在顶部 -> 小根堆
        return a.priority > b.priority; 
    }
    // 优先级相同：按名字字典序，名字大的“沉”下去，名字小的浮上来
    return a.name > b.name;
}

仿函数类中只要重载（）符号即可，其余均无需实现
调用仿函数时，必须通过仿函数类的对象调用。
Compare默认的仿函数Less与greater都在 < founction >头文件中

3. 常用接口一览

接口函数	功能描述	时间复杂度
`push(const T& value)`	将元素插入队列，并自动调整堆结构。	$O(log⁡N)O(\log N)$
`emplace(Args&&... args)`	原地构造元素并插入（避免拷贝/移动开销）。	$O(log⁡N)O(\log N)$
`top()`	返回堆顶元素的引用（不删除）。若队列为空，行为未定义。	$O (1)$
`pop()`	删除堆顶元素，并调整堆结构。无返回值。	$O(log⁡N)O(\log N)$
`empty()`	判断队列是否为空。	$O (1)$
`size()`	返回队列中元素的个数。	$O (1)$
`swap(priority_queue& other)`	交换两个优先队列的内容。	$O (1)$

** 重要提示**：
std::priority_queue 没有迭代器。

不能使用范围 for 循环遍历（如 for(auto x : pq)）。

不能使用 std::sort、std::find 等依赖迭代器的 STL 算法。

只能通过 top() 访问堆顶，或通过 pop() 逐个取出元素。