C++ STL之deque详解：从使用到底层，再到面试八股
本文面向面试和日常开发，先讲调用，再讲原理，最后给口语化面试答案。
一、用法速查
1.1 头文件与初始化
#include<deque>#include<iostream>#include<string>usingnamespacestd;intmain(){deque<int>dq1;// 空dequedeque<int>dq2(5);// 5个元素，默认0deque<int>dq3(5,1);// 5个1deque<int>dq4{10,20,30,40};// 初始化列表deque<int>dq5(dq4);// 拷贝构造for(intx:dq4)cout<<x<<" ";// 10 20 30 40}1.2 元素访问
#include<deque>#include<iostream>usingnamespacestd;intmain(){deque<int>dq{10,20,30,40,50};cout<<dq[0]<<"\n";// 10，不检查越界cout<<dq.at(1)<<"\n";// 20，越界抛 out_of_rangecout<<dq.front()<<"\n";// 10cout<<dq.back()<<"\n";// 50}1.3 两端操作
所有四端操作都是O(1)——这是 deque 的核心优势。
#include<deque>#include<iostream>usingnamespacestd;voidprint(constdeque<int>&dq){for(intx:dq)cout<<x<<" ";cout<<"\n";}intmain(){deque<int>dq;dq.push_back(10);dq.push_back(20);dq.push_front(5);dq.push_front(1);print(dq);// 1 5 10 20dq.pop_back();print(dq);// 1 5 10dq.pop_front();print(dq);// 5 10}1.4 中间插入与删除
#include<deque>#include<iostream>usingnamespacestd;voidprint(constdeque<int>&dq){for(intx:dq)cout<<x<<" ";cout<<"\n";}intmain(){deque<int>dq{10,20,30,40,50};autoit=dq.begin()+2;dq.insert(it,99);// 在20和30之间插入99print(dq);// 10 20 99 30 40 50dq.erase(dq.begin()+1);// 删除20print(dq);// 10 99 30 40 50dq.erase(dq.begin()+1,dq.begin()+3);// 删除 [99, 30)print(dq);// 10 40 50}注意：deque 的中间插入/删除是O(n)，因为需要移动插入点所在块以及后续所有块的元素——后面的面试题会细讲。
1.5 大小操作
#include<deque>#include<iostream>usingnamespacestd;intmain(){deque<int>dq{1,2,3,4,5};cout<<dq.size()<<"\n";// 5cout<<dq.empty()<<"\n";// 0 (false)dq.resize(3);// 只保留前3个cout<<dq.size()<<"\n";// 3for(intx:dq)cout<<x<<" ";// 1 2 3cout<<"\n";dq.resize(5,99);// 扩充到5，新元素填99for(intx:dq)cout<<x<<" ";// 1 2 3 99 99cout<<"\n";dq.clear();cout<<dq.size()<<"\n";// 0}与 vector 的显著区别：
// deque 没有这两个函数——编译错误// dq.capacity(); // ❌// dq.reserve(100); // ❌deque 没有capacity()和reserve()，因为它的分段连续结构不需要整体搬移——底层原理部分解释原因。
1.6 遍历与排序
#include<deque>#include<iostream>#include<algorithm>usingnamespacestd;intmain(){deque<int>dq{5,1,4,2,3};// 迭代器遍历for(autoit=dq.begin();it!=dq.end();++it)cout<<*it<<" ";// 5 1 4 2 3cout<<"\n";// 范围forfor(intx:dq)cout<<x<<" ";cout<<"\n";// 反向迭代器for(autoit=dq.rbegin();it!=dq.rend();++it)cout<<*it<<" ";// 3 2 4 1 5cout<<"\n";// sort排序——deque支持随机访问迭代器，可以调用std::sortsort(dq.begin(),dq.end());for(intx:dq)cout<<x<<" ";// 1 2 3 4 5cout<<"\n";}1.7 函数速查表
| 方法 | 含义 | 复杂度 |
|---|---|---|
dq[i] | 下标访问，不检查越界 | O(1) |
dq.at(i) | 带边界检查，越界抛异常 | O(1) |
front() / back() | 队首/队尾元素 | O(1) |
push_front(v) / push_back(v) | 首/尾插入 | O(1) |
pop_front() / pop_back() | 首/尾删除 | O(1) |
insert(pos, v) | 中间插入 | O(n) |
erase(pos) / erase(first, last) | 中间删除 | O(n) |
size() / empty() | 大小/判空 | O(1) |
resize(n) | 改变大小 | O(n) |
clear() | 清空 | O(n) |
begin() / end() | 迭代器 | O(1) |
二、底层原理
2.1 分段连续存储结构
deque的底层既不是 vector 的整块连续内存，也不是 list 的完全离散节点。它采用了一种巧妙的折中——分段连续存储（segmented contiguous storage）。
中控器 (map) ┌──────────────────────────┐ │ ptr │ ptr │ ptr │ … │ └───┬───┴───┬───┴───┬───┴──┘ │ │ │ ┌─────┘ │ └─────┐ ▼ ▼ ▼ ┌──────┐ ┌──────┐ ┌──────┐ │ 2 │ │ 25 │ │ 8 │ │ 10 │ │ 30 │ │ 12 │ │ 15 │ │ 35 │ │ — │ │ 20 │ │ — │ │ — │ └──────┘ └──────┘ └──────┘ buffer0 buffer1 buffer2 (块0) (块1) (块2)数据被切分成若干个固定大小的块（buffer），每个块内部是连续内存。块与块之间不连续，但通过一个中控器（通常称作 map，实际上是指针数组）来串联管理。
2.2operator[]的两步寻址
当你执行dq[i]时，deque 内部通过两步找到真正的内存位置：
block_index = i / block_size offset = i % block_size result = map[block_index][offset] // 等价于 *(map[block_index] + offset)以dq[3]为例，如果块大小是 4：
block_index = 3 / 4 = 0 offset = 3 % 4 = 3 → 取 map[0] 指向的块，再取该块第 3 个位置这个两步寻址就是O(1)的——一次数组索引 + 一次指针偏移，没有循环。
2.3 块大小
块大小依赖实现，一般规则是：
// 典型实现（gcc/libstdc++）staticconstsize_t block_size=max(1,512/sizeof(T));- 对于
int（4 字节）：512 / 4 = 128个元素每块 - 对于
double（8 字节）：512 / 8 = 64个元素每块 - 对于自定义大对象（sizeof > 512）：每块只放 1 个元素
512 字节是常见的内存页对齐值，由malloc的元数据效率决定。
2.4push_front/pop_front为何是 O(1)
vector 的push_front是 O(n) 的，因为需要把所有元素后移一位。但 deque 的分段连续结构完美解决了这个问题：
块0（头部有空位） 块1 块2 ┌──────┬──┐ ┌──────┐ ┌──────┐ │ — │ 5 │←front │ 10 │ │ 20 │ │ — │ 3 │ │ 15 │ │ 25 │ │ — │ 1 │ │ — │ │ — │ │ — │ 2 │ │ — │ │ — │ └──────┴──┘ └──────┘ └──────┘每个块在两端都预留了空间。执行push_front时：
- 如果当前首块前端还有空位，直接在该块的前一个槽位写入
- 如果首块前端已满，新分配一个块放到中控器前端，在新块尾部写入
pop_front对称——直接移动首块内的起始指针，如果整块元素全 pop 完，释放该块。
这就是为什么 deque 两端操作能保持 O(1)：不需要搬移已有元素，只需要操作首尾块的空位或分配释放块。
2.5 deque vs vector vs list 三维对比
| 维度 | deque | vector | list |
|---|---|---|---|
| 内存布局 | 分段连续（多块） | 整块连续 | 节点离散，指针连接 |
| 随机访问 | O(1)（两步寻址） | O(1)（直接偏移） | O(n)（逐个遍历） |
| 头插/头删 | O(1) | O(n)（整体后移） | O(1) |
| 尾插/尾删 | O(1) | O(1)（均摊） | O(1) |
| 中间插入/删除 | O(n) | O(n) | O(1)（有迭代器时） |
| 缓存局部性 | 中等（块内连续） | 最佳（整块连续） | 差（离散节点） |
| 迭代器失效（插入） | 仅两端操作不失效 | 可能全部失效 | 仅被删节点失效 |
| 有 capacity/reserve | 无 | 有 | 无 |
| 默认底层（stack/queue） | 自身 | — | — |
2.6 为什么 deque 没有capacity和reserve
vector 有capacity()是因为它的底层是一整块连续内存——当容量不够时必须整体搬迁，reserve可以预分配来减少扩容次数。
deque 不需要这两个函数，根本原因在于它的分段结构：
- push_back 时当前尾块满了，只需分配一个新块挂到中控器尾部，不需要搬移已有元素
- push_front 同理，满则分配新块挂到头部
- 没有"整体扩容"的概念——每次分配的都是单个小块的尺寸，无需整体搬迁
所以 deque 不需要预知最终大小来预留空间。如果一定要预留，用resize即可。
2.7 为什么 stack 和 queue 默认底层是 deque
template<classT,classContainer=deque<T>>classstack;template<classT,classContainer=deque<T>>classqueue;stack 需要一端插入 + 一端删除；queue 需要一端插入 + 另一端删除。deque 刚好对两端操作都是 O(1)，而且支持随机访问（虽然 adapter 不暴露这个能力）。相比之下，vector 只有尾部高效（push_front O(n)），list 虽然两端也快但缓存不友好且节点内存开销大。deque 是对 adapter 来说最均衡的选择。
三、面试题 + 口语化答案
Q1：deque 底层是什么数据结构？
“deque 底层是分段连续存储——由一个中控器（指针数组）管理多个固定大小的连续内存块。每个块内部是连续的，块与块之间不连续。访问元素时通过两步寻址：map[block_index] + offset，两次指针偏移就到目标位置了。这个结构让 deque 同时做到了两端 O(1) 操作和随机访问 O(1)——相当于在 vector 和 list 之间取了一个折中。”
Q2：为什么 deque 没有capacity()和reserve()？
“因为 deque 不需要整体搬移。vector 需要 reserve 是因为当整块连续内存不够时必须整体扩容——搬迁所有元素到新内存。deque 是分段连续的，尾块满了就分配一个小块挂到中控器尾部，头块满同理。每块大小是固定的，每次只分配一小块，不存在 vector 那种 ‘一次性搬走所有元素’ 的大扩容。所以 capacity 和 reserve 对 deque 没有意义——用 resize 预占位就行。”
Q3：deque 的迭代器和 vector 的迭代器有什么不同？
“两个核心区别。第一，大小不同——vector 的迭代器可以就是一个T*指针，8 字节就够（x64）。deque 的迭代器至少包含三个字段：当前元素的指针、当前所在块的指针、中控器的位置指针，在 GCC 里大约 16-24 字节。第二，失效规则不同——vector 只要触发扩容或中间插入删除，从操作位置往后的迭代器全部失效；deque 只在中间插入删除时失效，两端的push/pop操作不影响已有迭代器（push_front和push_back不失效）。”
Q4：什么时候用 deque 而不是 vector？
“典型的场景是需要在两端频繁操作——比如任务队列、滑动窗口、双端 BFS。如果大部分操作是 push_back + 随机访问，那就用 vector。如果要在头部频繁 push/pop，vector 是 O(n) 的扛不住，list 随机访问太慢，deque 是刚好合适的选择。另外如果不想处理 vector 的那个vector<bool>特化陷阱，也可以用deque<bool>替代——deque 没有 bool 特化，返回的是真的bool&。”
Q5：deque 中间插入为什么是 O(n)？
“这个 O(n) 和 vector 的 O(n) 性质不同。vector 的中间插入 O(n) 是因为需要把插入点之后的所有元素后移一位——一次连续的memmove。deque 的插入也是 O(n)，但原因是分段连续结构下的块间元素挪动：假设你在块 2 的某个位置插入了元素，块 2 在这个插入点之后的元素要往后挪；如果块 2 满了，最后一个元素要移到块 3 的头部，然后块 3 的所有元素顺次后移，以此类推——相当于把插入点后面的所有分段依次往后推了一个位置。如果面试官追问能不能比 vector 快，可以说不一定——vector 的 memmove 流水线友好，deque 的跨块挪动涉及多次拷贝且破坏缓存连续，实际常数可能更大。”
Q6：deque 的块大小在不同平台下是多少？
“块大小取决于实现，GCC libstdc++ 和 Clang libc++ 采用的是max(1, 512 / sizeof(T))——512 字节除元素类型大小，至少为 1。对于int是 128 个元素每块，double是 64 个。MSVC 的实现略有不同，但整体思路一致——用 512 字节这个对齐边界是因为现代 malloc 对 512 字节以下的小块分配效率最高，且能最小化内存碎片。这个常数是编译器决定的，标准没有强制，但主流实现大同小异。”
Q7：deque 中间插入后迭代器失效的范围是多大？
“只在被插入/删除位置所在的块以及之后的所有块中，迭代器才有可能失效。具体来说，如果你插入的是整个 deque 的中间位置，从插入点开始到末尾的所有迭代器都可能失效——因为后续的元素在块内挪动了位置。不像 vector 那么极端（扩容就全死），但比 list 严重（list 只死被删的那个）。另外两端的 push/pop 不会让任何已有迭代器失效——这是 deque 的一个优势。”
Q8：deque 和 list 都是两端操作高效，为什么 stack/queue 选 deque 作为默认底层？
“两个原因。第一，随机访问——list 的迭代器是双向的，不支持随机访问（所以 list 不能传给std::sort）；deque 的迭代器是随机访问的，虽然 adapter 不会暴露这个能力，但内部实现可以用operator[]做更高效的处理。第二，内存效率——list 每个节点都要存储 prev 和 next 两个指针，加上元素数据，额外开销差不多 16 字节（x64）。deque 按块分配，块内元素没有任何额外指针开销。数据量大时 deque 的内存占用比 list 少很多。所以 deque 是 adapter 的那个 ‘最均衡’ 的选择。”
一句话总结：deque 通过分段连续存储在中插 O(n) 的代价下换来了两端 O(1) 和随机访问 O(1) 的双重收益，是 vector 和 list 之间的最佳折中——它的迭代器结构、无 capacity 的设计、以及作为 stack/queue 默认底层的选择，都是面试中值得展开聊的考点。
