C STL之deque详解从使用到底层再到面试八股本文面向面试和日常开发先讲调用再讲原理最后给口语化面试答案。一、用法速查1.1 头文件与初始化#includedeque#includeiostream#includestringusingnamespacestd;intmain(){dequeintdq1;// 空dequedequeintdq2(5);// 5个元素默认0dequeintdq3(5,1);// 5个1dequeintdq4{10,20,30,40};// 初始化列表dequeintdq5(dq4);// 拷贝构造for(intx:dq4)coutx ;// 10 20 30 40}1.2 元素访问#includedeque#includeiostreamusingnamespacestd;intmain(){dequeintdq{10,20,30,40,50};coutdq[0]\n;// 10不检查越界coutdq.at(1)\n;// 20越界抛 out_of_rangecoutdq.front()\n;// 10coutdq.back()\n;// 50}1.3 两端操作所有四端操作都是O(1)——这是 deque 的核心优势。#includedeque#includeiostreamusingnamespacestd;voidprint(constdequeintdq){for(intx:dq)coutx ;cout\n;}intmain(){dequeintdq;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 中间插入与删除#includedeque#includeiostreamusingnamespacestd;voidprint(constdequeintdq){for(intx:dq)coutx ;cout\n;}intmain(){dequeintdq{10,20,30,40,50};autoitdq.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 大小操作#includedeque#includeiostreamusingnamespacestd;intmain(){dequeintdq{1,2,3,4,5};coutdq.size()\n;// 5coutdq.empty()\n;// 0 (false)dq.resize(3);// 只保留前3个coutdq.size()\n;// 3for(intx:dq)coutx ;// 1 2 3cout\n;dq.resize(5,99);// 扩充到5新元素填99for(intx:dq)coutx ;// 1 2 3 99 99cout\n;dq.clear();coutdq.size()\n;// 0}与 vector 的显著区别// deque 没有这两个函数——编译错误// dq.capacity(); // ❌// dq.reserve(100); // ❌deque 没有capacity()和reserve()因为它的分段连续结构不需要整体搬移——底层原理部分解释原因。1.6 遍历与排序#includedeque#includeiostream#includealgorithmusingnamespacestd;intmain(){dequeintdq{5,1,4,2,3};// 迭代器遍历for(autoitdq.begin();it!dq.end();it)cout*it ;// 5 1 4 2 3cout\n;// 范围forfor(intx:dq)coutx ;cout\n;// 反向迭代器for(autoitdq.rbegin();it!dq.rend();it)cout*it ;// 3 2 4 1 5cout\n;// sort排序——deque支持随机访问迭代器可以调用std::sortsort(dq.begin(),dq.end());for(intx:dq)coutx ;// 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]为例如果块大小是 4block_index 3 / 4 0 offset 3 % 4 3 → 取 map[0] 指向的块再取该块第 3 个位置这个两步寻址就是O(1)的——一次数组索引 一次指针偏移没有循环。2.3 块大小块大小依赖实现一般规则是// 典型实现gcc/libstdcstaticconstsize_t block_sizemax(1,512/sizeof(T));对于int4 字节512 / 4 128个元素每块对于double8 字节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 三维对比维度dequevectorlist内存布局分段连续多块整块连续节点离散指针连接随机访问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和reservevector 有capacity()是因为它的底层是一整块连续内存——当容量不够时必须整体搬迁reserve可以预分配来减少扩容次数。deque 不需要这两个函数根本原因在于它的分段结构push_back 时当前尾块满了只需分配一个新块挂到中控器尾部不需要搬移已有元素push_front 同理满则分配新块挂到头部没有整体扩容的概念——每次分配的都是单个小块的尺寸无需整体搬迁所以 deque 不需要预知最终大小来预留空间。如果一定要预留用resize即可。2.7 为什么 stack 和 queue 默认底层是 dequetemplateclassT,classContainerdequeTclassstack;templateclassT,classContainerdequeTclassqueue;stack 需要一端插入 一端删除queue 需要一端插入 另一端删除。deque 刚好对两端操作都是 O(1)而且支持随机访问虽然 adapter 不暴露这个能力。相比之下vector 只有尾部高效push_front O(n)list 虽然两端也快但缓存不友好且节点内存开销大。deque 是对 adapter 来说最均衡的选择。三、面试题 口语化答案Q1deque 底层是什么数据结构“deque 底层是分段连续存储——由一个中控器指针数组管理多个固定大小的连续内存块。每个块内部是连续的块与块之间不连续。访问元素时通过两步寻址map[block_index] offset两次指针偏移就到目标位置了。这个结构让 deque 同时做到了两端 O(1) 操作和随机访问 O(1)——相当于在 vector 和 list 之间取了一个折中。”map[0]块0[2, 10, 15, 20]map[1]块1[25, 30, 35, ...]map[2]块2[8, 12, ...]map[...]...Q2为什么 deque 没有capacity()和reserve()“因为 deque 不需要整体搬移。vector 需要 reserve 是因为当整块连续内存不够时必须整体扩容——搬迁所有元素到新内存。deque 是分段连续的尾块满了就分配一个小块挂到中控器尾部头块满同理。每块大小是固定的每次只分配一小块不存在 vector 那种 ‘一次性搬走所有元素’ 的大扩容。所以 capacity 和 reserve 对 deque 没有意义——用 resize 预占位就行。”Q3deque 的迭代器和 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/popvector 是 O(n) 的扛不住list 随机访问太慢deque 是刚好合适的选择。另外如果不想处理 vector 的那个vectorbool特化陷阱也可以用dequebool替代——deque 没有 bool 特化返回的是真的bool。”Q5deque 中间插入为什么是 O(n)“这个 O(n) 和 vector 的 O(n) 性质不同。vector 的中间插入 O(n) 是因为需要把插入点之后的所有元素后移一位——一次连续的memmove。deque 的插入也是 O(n)但原因是分段连续结构下的块间元素挪动假设你在块 2 的某个位置插入了元素块 2 在这个插入点之后的元素要往后挪如果块 2 满了最后一个元素要移到块 3 的头部然后块 3 的所有元素顺次后移以此类推——相当于把插入点后面的所有分段依次往后推了一个位置。如果面试官追问能不能比 vector 快可以说不一定——vector 的 memmove 流水线友好deque 的跨块挪动涉及多次拷贝且破坏缓存连续实际常数可能更大。”Q6deque 的块大小在不同平台下是多少“块大小取决于实现GCC libstdc 和 Clang libc 采用的是max(1, 512 / sizeof(T))——512 字节除元素类型大小至少为 1。对于int是 128 个元素每块double是 64 个。MSVC 的实现略有不同但整体思路一致——用 512 字节这个对齐边界是因为现代 malloc 对 512 字节以下的小块分配效率最高且能最小化内存碎片。这个常数是编译器决定的标准没有强制但主流实现大同小异。”Q7deque 中间插入后迭代器失效的范围是多大“只在被插入/删除位置所在的块以及之后的所有块中迭代器才有可能失效。具体来说如果你插入的是整个 deque 的中间位置从插入点开始到末尾的所有迭代器都可能失效——因为后续的元素在块内挪动了位置。不像 vector 那么极端扩容就全死但比 list 严重list 只死被删的那个。另外两端的 push/pop 不会让任何已有迭代器失效——这是 deque 的一个优势。”Q8deque 和 list 都是两端操作高效为什么 stack/queue 选 deque 作为默认底层“两个原因。第一随机访问——list 的迭代器是双向的不支持随机访问所以 list 不能传给std::sortdeque 的迭代器是随机访问的虽然 adapter 不会暴露这个能力但内部实现可以用operator[]做更高效的处理。第二内存效率——list 每个节点都要存储 prev 和 next 两个指针加上元素数据额外开销差不多 16 字节x64。deque 按块分配块内元素没有任何额外指针开销。数据量大时 deque 的内存占用比 list 少很多。所以 deque 是 adapter 的那个 ‘最均衡’ 的选择。”一句话总结deque 通过分段连续存储在中插 O(n) 的代价下换来了两端 O(1) 和随机访问 O(1) 的双重收益是 vector 和 list 之间的最佳折中——它的迭代器结构、无 capacity 的设计、以及作为 stack/queue 默认底层的选择都是面试中值得展开聊的考点。