在C++标准库中,容器是构建高效算法的基石,而
priority_queue和deque作为两种特性迥异却同样强大的数据结构,分别代表了优先级管理与线性操作的典范。priority_queue基于堆实现,以O(log n)的代价维护元素优先级,成为任务调度、贪心算法等场景的核心工具;而deque通过分块数组的巧妙设计,实现了首尾O(1)时间复杂度的插入删除,在滑动窗口、缓存系统等领域展现出不可替代性。本文将从底层实现、性能对比到典型应用场景,深入剖析二者的设计理念与工程实践价值,帮助大家在面对不同需求时做出精准选择。现在就让我们正式开始吧!
priority_queue(优先队列)是一种特殊的队列,其核心特性是 “队头元素始终是队列中优先级最高的元素”(默认是最大值优先)。
priority_queue 的底层实现是 “堆”(heap),堆是一种完全二叉树,分为大堆(根节点是最大值)和小堆(根节点是最小值)。STL 中的 priority_queue 默认是大堆。
priority_queue 的核心操作:
priority_queue 适用于需要 “动态获取优先级最高元素” 的场景,例如任务调度(优先执行高优先级任务)、找出数组中第 K 大的元素等。
STL 为 priority_queue 提供的常用成员函数如下表所示:
函数声明 | 接口说明 |
|---|---|
priority_queue() | 构造一个空的优先队列(默认大堆) |
priority_queue(InputIterator first, InputIterator last) | 用 [first, last) 区间的元素构造优先队列 |
empty() | 检测优先队列是否为空,为空返回 true,否则返回 false |
size() | 返回优先队列中有效元素的个数 |
top() | 返回堆顶元素的引用(非 const 对象调用) |
const T& top() const | 返回堆顶元素的 const 引用(const 对象调用) |
push(const T& x) | 将元素 x 插入优先队列,并调整堆结构 |
pop() | 删除堆顶元素,并调整堆结构(不返回元素值) |
#include <iostream>
#include <queue>
#include <vector>
#include <functional> // greater<> 仿函数的头文件
using namespace std;
int main() {
// 1. 默认大堆(底层用vector,比较方式为less<>)
priority_queue<int> maxHeap;
maxHeap.push(3);
maxHeap.push(1);
maxHeap.push(4);
maxHeap.push(2);
cout << "大堆的堆顶元素:" << maxHeap.top() << endl; // 输出:4
cout << "大堆的大小:" << maxHeap.size() << endl; // 输出:4
maxHeap.pop();
cout << "删除堆顶后,大堆的堆顶元素:" << maxHeap.top() << endl; // 输出:3
// 2. 小堆(需指定比较方式为greater<>)
// 模板参数:元素类型、底层容器类型、比较仿函数
priority_queue<int, vector<int>, greater<int>> minHeap;
minHeap.push(3);
minHeap.push(1);
minHeap.push(4);
minHeap.push(2);
cout << "小堆的堆顶元素:" << minHeap.top() << endl; // 输出:1
minHeap.pop();
cout << "删除堆顶后,小堆的堆顶元素:" << minHeap.top() << endl; // 输出:2
// 3. 用区间构造优先队列
vector<int> nums = {5, 2, 7, 3, 9};
priority_queue<int> heap(nums.begin(), nums.end());
cout << "区间构造的大堆堆顶:" << heap.top() << endl; // 输出:9
return 0;
} 当 priority_queue 存储自定义类型时,需要为该类型提供比较规则(重载<或>运算符,或自定义比较仿函数),因为 priority_queue 需要通过比较来维护堆结构。
示例:存储日期类型的 priority_queue
#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
// 日期类
class Date {
public:
Date(int year = 1900, int month = 1, int day = 1)
: _year(year), _month(month), _day(day) {}
// 重载<运算符:用于大堆(默认比较方式)
bool operator<(const Date& d) const {
// 按年、月、日的顺序比较,年份大的日期优先级高
if (_year != d._year) {
return _year < d._year;
}
if (_month != d._month) {
return _month < d._month;
}
return _day < d._day;
}
// 重载>运算符:用于小堆
bool operator>(const Date& d) const {
if (_year != d._year) {
return _year > d._year;
}
if (_month != d._month) {
return _month > d._month;
}
return _day > d._day;
}
// 友元函数:重载<<运算符,用于输出Date对象
friend ostream& operator<<(ostream& os, const Date& d) {
os << d._year << "-" << d._month << "-" << d._day;
return os;
}
private:
int _year;
int _month;
int _day;
};
int main() {
// 大堆:优先级高的日期(年份大、月份大、日期大)在堆顶
priority_queue<Date> maxHeap;
maxHeap.push(Date(2018, 10, 29));
maxHeap.push(Date(2018, 10, 28));
maxHeap.push(Date(2019, 1, 1));
cout << "大堆堆顶日期:" << maxHeap.top() << endl; // 输出:2019-1-1
maxHeap.pop();
cout << "删除堆顶后,大堆堆顶日期:" << maxHeap.top() << endl; // 输出:2018-10-29
// 小堆:优先级低的日期(年份小、月份小、日期小)在堆顶
priority_queue<Date, vector<Date>, greater<Date>> minHeap;
minHeap.push(Date(2018, 10, 29));
minHeap.push(Date(2018, 10, 28));
minHeap.push(Date(2019, 1, 1));
cout << "小堆堆顶日期:" << minHeap.top() << endl; // 输出:2018-10-28
minHeap.pop();
cout << "删除堆顶后,小堆堆顶日期:" << minHeap.top() << endl; // 输出:2018-10-29
return 0;
}pop()函数只删除堆顶元素,不返回该元素的值;top()前,必须确保优先队列不为空,否则会导致未定义行为;priority_queue<T>),需重载<运算符;priority_queue<T, vector<T>, greater<T>>),需重载>运算符;priority_queue 的底层是堆,因此模拟实现的核心是:
堆的核心算法(以大堆为例):
#include <vector>
#include <cassert>
#include <functional> // 用于greater<>仿函数
namespace bite {
// 模板参数:T-元素类型,Container-底层容器类型,Compare-比较仿函数(默认大堆)
template <class T, class Container = std::vector<T>, class Compare = std::less<T>>
class priority_queue {
public:
// 构造函数:默认构造
priority_queue() {}
// 区间构造:用[first, last)区间的元素构造堆
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
: _container(first, last) {
// 建堆:从最后一个非叶子节点开始向下调整
int parent = (_container.size() - 2) / 2;
for (int i = parent; i >= 0; --i) {
adjustDown(i);
}
}
// 检测优先队列是否为空
bool empty() const {
return _container.empty();
}
// 获取优先队列的大小
size_t size() const {
return _container.size();
}
// 访问堆顶元素
T& top() {
assert(!empty());
return _container[0];
}
const T& top() const {
assert(!empty());
return _container[0];
}
// 插入元素:尾插后向上调整
void push(const T& x) {
_container.push_back(x);
adjustUp(_container.size() - 1);
}
// 删除堆顶元素:交换堆顶与堆尾元素,尾删后向下调整
void pop() {
assert(!empty());
// 交换堆顶和堆尾元素
std::swap(_container[0], _container[_container.size() - 1]);
// 尾删堆尾元素(原堆顶)
_container.pop_back();
// 向下调整堆顶元素
adjustDown(0);
}
private:
// 向上调整:用于插入元素后维持堆特性
void adjustUp(size_t child) {
Compare comp; // 比较仿函数:大堆用less,小堆用greater
size_t parent = (child - 1) / 2; // 父节点索引
while (child > 0) {
// 若子节点优先级高于父节点(大堆:子>父;小堆:子<父),则交换
if (comp(_container[parent], _container[child])) {
std::swap(_container[parent], _container[child]);
// 更新父、子节点索引,继续向上调整
child = parent;
parent = (child - 1) / 2;
} else {
// 满足堆特性,调整结束
break;
}
}
}
// 向下调整:用于删除元素后维持堆特性
void adjustDown(size_t parent) {
Compare comp;
size_t child = 2 * parent + 1; // 左子节点索引
while (child < _container.size()) {
// 选择优先级更高的子节点(大堆:选较大的子节点;小堆:选较小的子节点)
if (child + 1 < _container.size() && comp(_container[child], _container[child + 1])) {
child++;
}
// 若子节点优先级高于父节点,则交换
if (comp(_container[parent], _container[child])) {
std::swap(_container[parent], _container[child]);
// 更新父、子节点索引,继续向下调整
parent = child;
child = 2 * parent + 1;
} else {
break;
}
}
}
private:
Container _container; // 底层容器
};
}题目描述:给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。
解题思路:
代码实现(大堆方法):
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
// 构造大堆
priority_queue<int> pq(nums.begin(), nums.end());
// 弹出k-1个最大元素
for (int i = 0; i < k - 1; ++i) {
pq.pop();
}
// 剩余堆顶元素即为第k个最大元素
return pq.top();
}
};
// 测试代码
int main() {
Solution sol;
vector<int> nums = {3,2,1,5,6,4};
int k = 2;
cout << "第" << k << "个最大的元素:" << sol.findKthLargest(nums, k) << endl; // 输出:5
vector<int> nums2 = {3,2,3,1,2,4,5,5,6};
k = 4;
cout << "第" << k << "个最大的元素:" << sol.findKthLargest(nums2, k) << endl; // 输出:4
return 0;
}题目描述:给你一个链表数组,每个链表都已经按升序排列。请你将所有链表合并成一个升序链表,返回合并后的链表。
解题思路:
代码实现:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 链表节点定义
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 自定义比较仿函数:用于小堆(优先级队列存储ListNode*,按节点值从小到大排序)
struct Compare {
bool operator()(ListNode* a, ListNode* b) {
return a->val > b->val;
}
};
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
// 小堆:存储每个链表的头节点
priority_queue<ListNode*, vector<ListNode*>, Compare> pq;
// 将所有非空链表的头节点入堆
for (ListNode* list : lists) {
if (list != nullptr) {
pq.push(list);
}
}
// 虚拟头节点,用于构建结果链表
ListNode* dummy = new ListNode(0);
ListNode* curr = dummy;
while (!pq.empty()) {
// 取出当前最小节点
ListNode* minNode = pq.top();
pq.pop();
// 加入结果链表
curr->next = minNode;
curr = curr->next;
// 若该节点有后继节点,入堆
if (minNode->next != nullptr) {
pq.push(minNode->next);
}
}
return dummy->next;
}
};
// 辅助函数:打印链表
void printList(ListNode* head) {
while (head != nullptr) {
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
// 测试代码
int main() {
// 构建链表数组
ListNode* l1 = new ListNode(1);
l1->next = new ListNode(4);
l1->next->next = new ListNode(5);
ListNode* l2 = new ListNode(1);
l2->next = new ListNode(3);
l2->next->next = new ListNode(4);
ListNode* l3 = new ListNode(2);
l3->next = new ListNode(6);
vector<ListNode*> lists = {l1, l2, l3};
Solution sol;
ListNode* mergedList = sol.mergeKLists(lists);
printList(mergedList); // 输出:1 1 2 3 4 4 5 6
return 0;
}在之前的博客中,我们提到 stack 和 queue 的默认底层容器是 deque,而 priority_queue 的默认底层容器是 vector。本节将深入解析 deque 的原理、特性及为何成为 stack 和 queue 的默认选择。



deque(双端队列,Double-Ended Queue)是一种双开口的 “连续” 空间数据结构,支持在头尾两端进行插入和删除操作,且时间复杂度均为 O (1)。

deque 的核心特性:
deque 的底层结构较为复杂,主要由三部分组成:
cur:指向当前缓冲区中的当前元素;first:指向当前缓冲区的起始位置;last:指向当前缓冲区的末尾位置;node:指向中控器中当前缓冲区对应的指针。deque 的底层结构示意图:

当 deque 需要扩容时:
deque 的迭代器设计是其能够 “假装” 连续的关键。当迭代器移动到缓冲区的边界时,会自动切换到下一个或上一个缓冲区。
以++it(迭代器自增)为例,其核心逻辑:
it->cur++:移动到当前缓冲区的下一个元素;it->cur == it->last(已到达当前缓冲区末尾): it->node++:指向中控器的下一个缓冲区指针;it->cur = it->node->first:指向新缓冲区的起始位置; 同理,--it(迭代器自减)会处理缓冲区的左边界切换。
stack 和 queue 的核心操作有如下特点:
deque 是完美契合 stack 和 queue 的需求的,同时避开了自身的缺点:
因此,STL 选择 deque 作为 stack 和 queue 的默认底层容器,是综合考虑操作效率、空间开销后的最优选择。
容器适配器 | 核心特性 | 底层容器 | 时间复杂度(关键操作) | 适用场景 |
|---|---|---|---|---|
stack | 后进先出(LIFO) | deque(默认)、vector、list | push/pop/top:O(1) | 函数调用栈、表达式求值、括号匹配、回溯算法 |
queue | 先进先出(FIFO) | deque(默认)、list | push/pop/front/back:O(1) | 任务调度、消息队列、广度优先搜索(BFS) |
priority_queue | 优先级最高元素优先 | vector(默认)、deque | push:O(log n)、pop:O(log n)、top:O(1) | 任务调度(高优先级优先)、Top K 问题、堆排序 |
<或>运算符,stack 和 queue 无需(除非需要自定义底层容器);stack、queue 和 priority_queue 是 C++ STL 中非常实用的容器适配器,它们基于底层容器封装,提供了简洁高效的接口,适用于不同的业务场景。本文从概念、接口、模拟实现、实战应用到底层原理,全方位解析了这三种容器适配器,希望能帮助大家深入理解其设计思想与使用方法。 在实际开发中,应根据具体需求选择合适的容器适配器及底层容器,充分发挥 STL 的高效性和便捷性。同时,深入理解底层原理有助于解决复杂问题,优化代码性能。 如果本文对你有帮助,欢迎点赞、收藏、转发,也欢迎在评论区交流讨论!