C++中std::deque双端队列怎么用_C++ deque常用操作与应用场景

std::deque支持两端高效插入删除,适用于滑动窗口、任务调度等场景,对比vector和list具有操作灵活性与较好随机访问性能。

C++中std::deque双端队列怎么用_C++ deque常用操作与应用场景

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. 容量相关

C++中std::deque双端队列怎么用_C++ deque常用操作与应用场景

AppMall应用商店

AI应用商店,提供即时交付、按需付费的人工智能应用服务

C++中std::deque双端队列怎么用_C++ deque常用操作与应用场景56

查看详情 C++中std::deque双端队列怎么用_C++ deque常用操作与应用场景

  • dq.empty();:判断是否为空
  • dq.size();:返回当前元素个数

5. 清空与迭代

  • dq.clear();:清空所有元素
  • 可用范围for循环或迭代器遍历:
    for (const auto& x : dq) {     std::cout << x << " "; }

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是一个功能均衡、接口丰富的容器,在需要双端操作的场合表现优秀。合理使用能提升代码清晰度与运行效率。

上一篇
下一篇
text=ZqhQzanResources