前言前面分析stack和queue时我们会反复看到一个很容易被忽略的细节templateclass T, class Container dequeT class stack; templateclass T, class Container dequeT class queue;两种容器适配器的默认底层容器都是deque如果只停留在“deque 支持头尾操作所以适合 stack 和 queue”这一层其实还没有真正解释清楚 STL 的设计选择。因为这里至少还存在几个问题vector 的尾部操作同样很快为什么 stack 不默认使用 vector list 的头删、尾插也都是 O(1)为什么 queue 不默认使用 list deque 明明没有 vector 那样漂亮的连续内存为什么反而成了折中的默认方案要回答这些问题就需要稍微往 deque 的内部再走一步。一、deque 的核心并不是“双端”而是它如何做到“双端”deque的全称是double-ended queue也就是“双端队列”。它最直观的能力是头部可以插入 头部可以删除 尾部可以插入 尾部可以删除从接口上看就是push_front(); pop_front(); push_back(); pop_back();并且两端插入、删除都可以做到很高的效率。但真正值得关注的不是“deque 两头都能操作”这句话而是它为什么能避免 vector 在头部操作时的大规模元素移动答案就在 deque 的存储结构里。二、deque 不是“大 vector”而是“分段连续 集中管理”很多初学者第一次看到 deque会下意识把它理解成可以从两头操作的 vector这种理解只能描述它的使用方式却不能解释它的底层机制。vector的核心特点是所有元素处于一整块连续内存中。可以简单表示成┌────┬────┬────┬────┬────┐ │ 10 │ 20 │ 30 │ 40 │ 50 │ └────┴────┴────┴────┴────┘连续存储给 vector 带来了非常优秀的随机访问能力 缓存局部性 遍历性能但代价也很明显当现有连续空间不足时vector 可能需要重新申请一块更大的连续空间再搬迁已有元素。deque 选择了另一条路线。它通常不是申请一整块巨大的连续空间而是把数据拆分到若干块固定大小或实现相关大小的缓冲区中buffer 1 ┌────┬────┬────┬────┐ │ │ │ │ │ └────┴────┴────┴────┘ buffer 2 ┌────┬────┬────┬────┐ │ │ │ │ │ └────┴────┴────┴────┘ buffer 3 ┌────┬────┬────┬────┐ │ │ │ │ │ └────┴────┴────┴────┘然后再通过一个用于管理这些缓冲区的结构将它们组织成一个逻辑上的整体。在常见 STL 实现中可以把这个结构理解为map ↓ 保存若干 buffer 的地址于是整体关系更接近map ┌────┬────┬────┬────┬────┐ │ * │ * │ * │ * │ * │ └─┬──┴─┬──┴─┬──┴─┬──┴─┬──┘ │ │ │ │ │ ↓ ↓ ↓ ↓ ↓ buf buf buf buf buf这里有一个需要说得严谨一点的地方C 标准规定的是 deque 对外表现出的行为和复杂度要求并没有要求所有标准库必须采用完全相同的内部布局。不同编译器、不同 STL 实现的细节可能不同。但是在理解 deque 时使用“分段连续空间 中央映射结构管理各段 buffer”这个典型模型是非常合适的。这种设计到底解决了什么问题假设 deque 尾部空间已经用完。它不一定需要像 vector 那样重新申请一整块更大的连续空间 ↓ 搬迁所有已有元素 ↓ 释放旧空间而是可以继续增加新的 buffer再让管理结构记录新的缓冲区。因此从设计思想上来看vector 更强调“整体连续” deque 更强调“分段组织”这使 deque 在不断向两端增长时具有很大的灵活性。注意这里不要简单理解为deque 扩容永远什么都不用调整。如果用于管理 buffer 的映射结构空间本身不足它同样可能需要调整自己的管理结构。真正的区别在于deque 不需要为了维持“一整块元素连续内存”像 vector 那样搬迁全部已有元素。这才是两者扩展机制上的核心差别。三、为什么 deque 看起来连续实际上却不是连续的站在使用者角度我们完全可以这样写dequeint dq; dq.push_back(10); dq.push_back(20); dq.push_back(30); cout dq[1] endl;甚至可以for (auto it dq.begin(); it ! dq.end(); it) { cout *it ; }看起来和 vector 非常相似。但两者底层发生的事情完全不同。vector 的迭代器可以粗略理解成一个非常接近普通指针的东西当前位置 ↓ [10][20][30][40] ↓ it ↓ 直接走到下一个元素因为元素真正连续。deque 则要复杂得多。假设当前元素位于某一个 buffer 中buffer A [10][20][30][40] ↑ cur只要还没有走到当前 buffer 的末尾it;仍然比较简单。但如果已经来到buffer A 的最后一个元素再执行it;迭代器就必须完成类似下面的工作当前 buffer 已经结束 ↓ 找到当前 buffer 在 map 中的位置 ↓ 定位下一个 buffer ↓ 跳到下一个 buffer 的起始位置 ↓ 继续遍历所以典型 deque 迭代器需要维护的不只是“当前元素在哪里”还要知道当前 buffer 的开始位置 当前 buffer 的结束位置 当前 buffer 在 map 中的位置因此在一些经典 STL 实现分析中经常能看到类似cur first last node这样的成员。可以粗略理解成cur → 当前正在访问哪个元素 first → 当前 buffer 的起始位置 last → 当前 buffer 的结束位置 node → 当前 buffer 在 map 中的位置这样 deque 才能给用户制造出一种“虽然物理空间并不完全连续但我仍然可以像访问一个整体容器一样进行迭代”的效果。这也是 deque 实现中一个很有意思的地方连续性不一定非要由底层内存天然提供也可以通过迭代器这一抽象层在逻辑上重新构造出来。四、deque 为什么说是一种“折中型容器”理解了内部结构以后再比较vector deque list会更加清楚。vector 的优势非常极端vector 追求连续存储所以它特别擅长随机访问 顺序遍历 缓存命中 尾部操作但如果需要从最前面删除一个元素1 2 3 4 5删除 1 后2 3 4 5为了维持连续结构后面的元素需要向前移动。因此头删不是 vector 擅长的事情。list 走的是另一个极端list 不要求元素连续。每个元素通常以节点形式组织┌──────┐ ┌──────┐ ┌──────┐ │ node │ ⇄ │ node │ ⇄ │ node │ └──────┘ └──────┘ └──────┘因此已知位置附近的插入和删除非常灵活。但是每个节点除了真正的数据以外通常还需要保存额外的链接信息。而且节点可能分散在内存的不同位置。这意味着额外指针空间 缓存局部性相对较差deque 站在两者中间deque 没有要求所有元素整体连续所以它不会完全受到 vector 那种连续空间要求的限制。但它也没有采用一个元素对应一个独立链表节点这样的组织方式。而是很多个元素 ↓ 组成一个连续 buffer 多个 buffer ↓ 通过 map 组织起来因此可以把它理解成vector ↓ 整体连续 │ │ deque分段连续 │ │ ↓ list 节点式离散这也是为什么我更愿意把 deque 称为一种在连续存储和链式组织之间进行工程折中的容器。它不是所有指标上最强的那个但是它把两端操作 随机访问 空间扩展 缓存局部性这些需求平衡得比较好。五、为什么它恰好适合 stack 和 queue现在再回过头看 STL 的选择就比较容易理解了。先看stack。stack 需要的核心能力其实非常少push(); pop(); top();映射到底层就是push() ↓ push_back() pop() ↓ pop_back() top() ↓ back()所以 stack 要求的核心能力其实就是高效操作容器尾部。这一点vector deque list都可以做到。因此我们确实可以写stackint, vectorint st1; stackint, dequeint st2; stackint, listint st3;再来看queue。queue 的操作方向不同新元素 ↓ 从队尾进入 旧元素 ↓ 从队头离开因此底层要求push_back() pop_front() front() back()这里需要特别说明一个容易说得不够严谨的地方。很多时候会看到vector 头删效率低所以不适合 queue。这句话方向没错但如果讨论的是std::queueT, Container还可以再准确一步vector 本身没有pop_front()因此它并不满足标准 queue 对底层容器所需要的接口。也就是说queueint, vectorint并不是单纯“能用但效率低”而是标准接口层面就不满足要求。如果我们自己设计一个 queue然后强行使用v.erase(v.begin());模拟头删才会进一步遇到后续元素整体移动 ↓ O(n)的问题。而deque list都天然支持pop_front();所以两者都可以作为 queue 的底层容器。那为什么最终选 deque而不是 list这才是最值得分析的地方。queue 只需要头部 尾部的操作。它根本不要求使用者从中间遍历 进行复杂迭代器操作stack 更是只需要操作尾部而 stack 和 queue 本身都没有给用户暴露普通迭代器。于是 deque 的一个主要复杂点迭代器需要处理跨 buffer 跳转在 stack / queue 这个场景中几乎不会直接暴露给用户。与此同时deque 的优势头部操作效率高 尾部操作效率高 不依赖整体连续扩容 比链表具有更好的局部性却刚好全部能够发挥出来。这实际上是一种非常典型的工程设计不是选择“理论上某一项性能最强”的结构而是选择“优点正好匹配需求同时缺点在当前场景中又不明显”的结构。这也是 deque 成为stack queue默认底层容器的重要原因。六、从 deque 再看一次“容器适配器”学到这里其实还能反过来加深我们对Container Adapter 容器适配器这个概念的理解。stack 和 queue 自己并不关心你底层到底是怎么申请内存的。它们真正关心的是你能不能提供我需要的操作例如 stack 需要back push_back pop_backqueue 需要front back push_back pop_front只要底层容器满足这些能力上层适配器就可以把它包装成stack 或者 queue于是整个设计关系就变成底层容器 负责 数据到底怎么存 ↓ 容器适配器 负责 数据允许怎么被使用 ↓ stack LIFO 后进先出 queue FIFO 先进先出这也是我觉得学习 deque 最有价值的地方。表面上这一节只是在补充一个 STL 容器但实际上它把前面很多内容重新串了起来vector 的连续存储 ↓ list 的链式存储 ↓ deque 的分段连续存储 ↓ 模板参数替换底层容器 ↓ stack / queue 容器适配器到了这里我们已经不只是知道queueint q;“默认用了 deque”。而是开始能够解释为什么设计者会选择 deque。总结如果让我现在用一句话描述 deque我不会只说deque 是一个双端队列。我更愿意把它理解成deque 通过分段连续存储和额外的映射管理结构在保持随机访问能力的同时获得了高效的两端扩展能力是一种典型的工程折中型顺序容器。把它放回 stack 和 queue 中deque │ ├── 两端操作高效 │ ├── 不要求整体连续扩容 │ ├── 相比 list 局部性更好 │ └── 迭代器虽然复杂 但 stack / queue 又不暴露迭代器 ↓ 非常契合适配器需求 ↓ 成为默认底层容器所以真正值得记住的并不是stack 默认 deque queue 默认 deque而是背后的设计逻辑一个好的底层数据结构不一定每一项能力都做到极致而是它的优势刚好覆盖上层需求它的缺点又恰好不会成为当前场景的主要矛盾。这才是理解 STL 设计比单纯记住 STL 接口更有意思的地方。