deque容器——双端队列
C++std::deque双端队列详解
std::deque(Double-Ended Queue，发音为 “deck”) 是 C++ 标准模板库 (STL) 中的一种序列式容器。它的核心特性是支持在容器的头部和尾部进行常数时间O(1)O(1)O(1)的插入和删除操作，同时保留了类似数组的随机访问能力。
与std::vector不同，deque的内存布局是分段连续的（由多个固定大小的缓冲区组成），这使得它在头部扩展时无需像vector那样搬运所有数据，但也导致了其遍历性能略低于vector。
1. 核心接口速查表
下表列出了std::deque最常用的成员函数。** 请特别注意“特殊返回值/行为”一列，其中标明了空容器访问、异常抛出等关键细节。**
| 分类 | 函数签名 | 功能描述 | 时间复杂度 | 特殊返回值 / 行为说明 |
|---|---|---|---|---|
| 构造 | deque() | 默认构造空队列 | O(1)O(1)O(1) | - |
deque(n, val) | 构造含 n 个 val 的队列 | O(n)O(n)O(n) | - | |
| 容量 | size() | 返回元素个数 | O(1)O(1)O(1) | 返回size_type(无符号整数) |
empty() | 判断是否为空 | O(1)O(1)O(1) | 返回bool，空则 true | |
max_size() | 返回最大可容纳元素数 | O(1)O(1)O(1) | 理论上限，通常受内存限制 | |
resize(n) | 调整大小为 n | O(n)O(n)O(n) | 若 n>size()，新元素默认初始化；若 n<size()，尾部被丢弃 | |
| 访问 | operator[] | 下标访问 (不检查边界) | O(1)O(1)O(1) | 未定义行为 (UB)：若下标越界，不报错但程序可能崩溃 |
at(n) | 下标访问 (检查边界) | O(1)O(1)O(1) | 抛异常：若下标越界，抛出std::out_of_range | |
front() | 返回首元素引用 | O(1)O(1)O(1) | 未定义行为 (UB)：若在空容器上调用 | |
back() | 返回尾元素引用 | O(1)O(1)O(1) | 未定义行为 (UB)：若在空容器上调用 | |
| 修改 | push_back(val) | 尾部插入元素 | O(1)∗O(1)*O(1)∗ | *均摊常数时间，可能触发内存分配 |
push_front(val) | 头部插入元素 | O(1)∗O(1)*O(1)∗ | *均摊常数时间，vector 不支持此操作 | |
pop_back() | 删除尾部元素 | O(1)O(1)O(1) | 未定义行为 (UB)：若在空容器上调用；无返回值(void) | |
pop_front() | 删除头部元素 | O(1)O(1)O(1) | 未定义行为 (UB)：若在空容器上调用；无返回值(void) | |
insert(pos, val) | 在 pos 位置插入 | O(n)O(n)O(n) | 返回指向新元素的迭代器；pos 可以是begin()到end() | |
erase(pos) | 删除 pos 位置元素 | O(n)O(n)O(n) | 返回指向被删元素下一位置的迭代器；迭代器失效 | |
clear() | 清空所有元素 | O(n)O(n)O(n) | 销毁所有元素，size 变为 0 | |
swap(other) | 交换两个 deque 内容 | O(1)O(1)O(1) | 仅交换内部指针，不复制元素 |
注：
- UB (Undefined Behavior)：意味着代码不会报错，但结果不可预测（如返回垃圾值、段错误）。调用
front(),back(),pop_*()前务必检查!empty()。- 迭代器失效：除了两端操作 (
push/pop_front/back) 外，在中间插入或删除会导致指向该位置及之后元素的迭代器失效。
2. 接口简要介绍
2.1 构造与容量
- 构造：
deque支持默认构造、填充构造（指定数量和初始值）以及范围构造（从其他容器复制）。 size()vsempty()：虽然size() == 0也能判断空，但empty()语义更清晰且在某些实现中效率略高。resize()：常用于预分配空间或截断数据。如果扩大，新增部分会被值初始化（基本类型为 0，类类型调用默认构造函数）。
2.2 元素访问 (关键区别)
operator[]：最快，但不安全。适用于循环遍历或确信下标合法的场景。at()：安全，但稍慢（因为有边界检查）。推荐在调试阶段或处理用户输入索引时使用，它能通过抛出std::out_of_range异常帮你定位越界 bug。front()/back()：直接引用首尾元素。切记：在空 deque 上调用它们是 C++ 中最常见的崩溃原因之一。
2.3 修改操作 (核心优势)
- 双端插入/删除：
push_front和pop_front是deque区别于vector的最大特征。vector的insert(begin(), ...)是O(N)O(N)O(N)的，而deque是O(1)O(1)O(1)。 pop系列无返回值：与stack适配器不同，deque的pop_front()和pop_back()返回void。- 正确用法：先获取值，再弹出。
if(!dq.empty()){intval=dq.front();// 1. 取值dq.pop_front();// 2. 删除} - 错误用法：
int val = dq.pop_front();(编译错误)
- 正确用法：先获取值，再弹出。
insert/erase：虽然支持中间操作，但效率较低 (O(N)O(N)O(N))，因为需要移动元素。如果频繁在中间插删，应考虑std::list。
3. 代码示例
#include<iostream>#include<deque>#include<stdexcept>intmain(){std::deque<int>dq;// 1. 双端插入dq.push_back(10);dq.push_back(20);dq.push_front(5);// 现在: 5, 10, 20// 2. 安全访问 (at)try{std::cout<<"Element at 0: "<<dq.at(0)<<std::endl;// 输出 5// dq.at(10); // 如果取消注释，会抛出 std::out_of_range}catch(conststd::out_of_range&e){std::cerr<<"Out of range error: "<<e.what()<<std::endl;}// 3. 不安全访问 ([]) - 必须确保不越界if(!dq.empty()){std::cout<<"Front element: "<<dq[0]<<std::endl;}// 4. 正确的 pop 用法if(!dq.empty()){intfirst=dq.front();// 取值dq.pop_front();// 删除 (无返回值)std::cout<<"Popped: "<<first<<", New size: "<<dq.size()<<std::endl;}// 5. 遍历for(intx:dq){std::cout<<x<<" ";}std::cout<<std::endl;return0;}