std::deque 详解

一、概念

deque（double-ended queue，双端队列）：支持头部和尾部 O(1) 插入/删除，也支持 O(1) 随机访问（但比 vector 慢一点，因为有间接寻址），中间插入 O(n)。

典型实现（libstdc++）：分段连续空间（map 指针数组 + 若干连续 buffer）。

二、底层结构

        ┌─────────────────────────────── map（中控器，指针数组）──┐
        │  [buf] [buf] [buf] [buf] [buf] [buf] [buf] [buf]      │
        └────────────────────────────────────────────────────────┘
             每个 buf 是一段连续内存，存放若干元素

• map（中控器）：一个 T** 指针数组，每个元素指向一块「缓存段 buffer」。
• buffer：默认每个 buffer 存 512 / sizeof(T) 个元素（保证 ≤512 字节，便于缓存友好）。每段连续，但段与段之间不连续。
• 需要 start（map 起始迭代器指针）、finish、各段的 first/last 与当前 cursor 信息来维护「逻辑上连续」的双端队列。

为什么能两头 O(1)？：头尾操作仅涉及当前首/尾 buffer 里的游标 ±1；一段用尽后在中控器 map 中分配新的 buffer 挂上即可。随机访问为 O(1)：先通过 map 定位到第几段，再在段内偏移（多一层指针跳转，所以略慢于 vector）。

三、高频问答

Q1. deque 与 vector 的区别？

维度	vector	deque
底层	单块连续内存	分段连续（map + buffer）
头插	O(n)（不可）❌	O(1) ✅
尾插	O(1) 均摊	O(1) ✅
随机访问	极快（缓存友好）	快但需两次寻址，略慢
插入/删除中间	O(n)	O(n)
扩容	整块搬移，迭代器失效	只在 map 上增删指针，迭代器不失效，仅首尾操作使对应 iterator 失效
与 C 数组兼容	&v[0] 可用 ✅	不可用（不连续）❌
内存	可能有「尾大不掉」整块浪费	分段，无大块连续要求

Q2. 什么时候用 deque？

• 需要频繁头尾插入删除时（如实现滑动窗口、缓冲区、任务队列）；
• 也想快速随机访问但不能忍受 list 的 O(n) 访问。

Q3. 迭代器失效规则？

• 在中间插入/删除 → 所有迭代器、引用失效。
• 在头部或尾部插入 → 迭代器可能失效（map 可能要扩容），但元素引用不失效。
• 在头部或尾部删除 → 只有被删元素的迭代器失效，其余不受影响。

libstdc++ 中 deque 在中控器两端预留了空闲指针位，多数头尾 push 不会失效迭代器，但标准只要求「引用不失效」，迭代器失效由实现决定——这是常被拿来出题的细节。

Q4. 为什么中间插入慢？

因为要搬移元素以维持逻辑顺序；且 deque 是分段（多段）结构，搬到哪、怎么在段间迁移实现相对复杂。

四、最小的模拟结构（思路）

template <typename T>
class Deque {
    // 概念示意，不含完整实现
    T** map_;        // 中控器：指针数组
    size_t map_size_;
    // first：指向第一个 buffer；first cursor 标记首个有效元素
    // last：指向最后一个 buffer；last cursor 标记末元素之后
};

面试一般只考结构理解而非完整手写 deque（相对复杂）。重点讲清：为什么头尾 O(1)、为什么随机访问稍慢、为什么中间插入要搬移。

五、常见追问

1. deque 为什么不用链表？—— 链表中部随机访问 O(n)，deque 接近 O(1)，且缓存局部性优于链表。
2. deque 扩容时旧引用为什么不失效？—— 因为元素本身在各自 buffer 中不移动，只是中控器指针数组可能换新的（引用指向元素所在 buffer，不随 map 移动）。
3. stack/queue 为什么常用 deque 作底层？—— deque 两头 O(1)，且本身不要求随机访问；用 vector 做 stack 也可，但 deque 头尾都高效，故 std::stack/std::queue 默认容器适配器是 deque。