std::deque支持两端高效插入删除,适用于滑动窗口、任务调度等场景,对比vector和list具有操作灵活性与较好随机访问性能。
在c++中,std::deque(全称 double-ended queue)是一种支持在两端高效插入和删除元素的序列容器。它结合了vector的部分特性与链表的操作灵活性,是STL中非常实用的容器之一。
基本用法与常用操作
要使用 deque,需要包含头文件:#include <deque>。以下是常见操作示例:
1. 创建与初始化
-
std::deque<int> dq;
:创建一个空的int类型双端队列 -
std::deque<int> dq(5, 10);
:创建包含5个值为10的元素 -
std::deque<int> dq = {1, 2, 3, 4};
:使用初始化列表
2. 插入与删除
立即学习“C++免费学习笔记(深入)”;
-
dq.push_front(x);
:在队列前端插入x -
dq.push_back(x);
:在队列末尾插入x -
dq.pop_front();
:移除第一个元素(注意:不返回值) -
dq.pop_back();
:移除最后一个元素
3. 访问元素
-
dq.front();
:获取第一个元素 -
dq.back();
:获取最后一个元素 -
dq[i];
或dq.at(i);
:随机访问第i个元素(at会做越界检查)
4. 容量相关
-
dq.empty();
:判断是否为空 -
dq.size();
:返回当前元素个数
5. 清空与迭代
deque 与 vector、list 的对比
理解 deque 的优势需要对比其他容器:
- vs vector:vector只在尾部高效插入/删除,而deque在前后都高效;但vector内存连续,缓存友好性更好
- vs list:list虽然也支持两端操作且任意位置插入快,但占用更多内存(每个节点有指针开销),且不支持随机访问(实际支持但标准未要求高效)
deque在中间插入/删除效率不如list,但两端操作接近常数时间,且支持O(1)随机访问。
典型应用场景
由于其两端高效操作的特性,deque适用于以下场景:
- 滑动窗口问题:比如求最大值的滑动窗口,可用deque维护可能成为最大值的候选索引
- 任务调度缓冲区:新任务可从前或后加入,优先处理某一端的任务
- BFS中的双端队列(0-1 BFS):边权为0或1时,用deque实现类似Dijkstra的最短路径算法
- 实现双端队列ADT:比手写链表更安全、简洁
- 需要频繁首尾增删的日志缓冲:例如保留最近N条记录,超出时从另一端弹出
注意事项
使用deque时需注意:
- 插入可能导致迭代器失效,尤其是push_front/push_back后,原有迭代器可能不可用
- 虽然支持[]访问,但性能略低于vector(因内存分段连续)
- 不保证所有元素在物理上连续存储,因此不能像vector那样传给C风格API(如memcpy)
- 若大量在中间插入,应考虑list或vector配合算法
基本上就这些。std::deque是一个功能均衡、接口丰富的容器,在需要双端操作的场合表现优秀。合理使用能提升代码清晰度与运行效率。