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

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

AppMall应用商店

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

56

查看详情

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

以上就是C++中std::deque双端队列怎么用_C++ deque常用操作与应用场景的详细内容，更多请关注php中文网其它相关文章！