deque底层是分段连续内存而非链表，由固定大小缓冲区和map数组组成，支持头尾均摊O(1)操作但中间插入为O(n)，随机访问O(1)但常数较大，迭代器在增减缓冲区时全部失效。
deque 的底层确实是分段连续内存，但不是链表
很多人看到 deque 支持头尾 O(1) 插入就默认它是双向链表，其实完全相反：deque 用的是“分段连续”的数组块（通常叫 map 数组 + 固定大小的缓冲区），每块内部连续，块之间通过索引间接连接。它不存指针，不涉及动态分配节点，因此没有链表的 cache 不友好问题。
典型实现中（如 libstdc++ 和 libc++），每个缓冲区大小是固定的，常见为 512 字节（具体取决于元素类型和编译器），map 是一个动态数组，里面存的是各缓冲区首地址的指针。逻辑上连续的元素，物理上可能跨两个缓冲区。
这意味着：
-
deque迭代器必须是随机访问迭代器（RandomAccessIterator），它内部封装了map索引 + 缓冲区内偏移，重载了operator+、operator[]等 - 任意位置
operator[]是 O(1)，但常数比vector大：一次map查找 + 一次指针偏移计算 - 迭代时跨缓冲区边界会触发额外分支判断（现代 CPU 预测效果好，实际影响有限）
为什么 push_front / push_back 是均摊 O(1)，但中间插入仍是 O(n)
push_front 和 push_back 快，是因为只操作首尾缓冲区：若当前缓冲区有空位，直接构造；若满，则分配新缓冲区、更新 map，并调整 start/finish 迭代器的缓冲区索引和偏移量。整个过程不移动已有元素。
立即学习“C++免费学习笔记（深入）”；
但 insert 在中间位置（比如 deque.begin() + k）无法避免数据搬移：它必须把 [k, end) 区间整体后挪一位。由于内存不真正连续，这需要按缓冲区逐段拷贝——先腾出末尾缓冲区空间，再倒序搬运，最坏情况是 O(n) 时间 + O(1) 额外空间（不计新缓冲区分配）。
注意：libstdc++ 的 insert 实现甚至会优先尝试在靠近插入点的缓冲区里“挤”出空间（比如前一个缓冲区有空余，就挪一部分过去），但本质仍是线性搬移，不是链表式的指针重连。
迭代器失效规则和 vector 完全不同
deque 的迭代器失效规则非常特殊：只有当发生缓冲区增减（即 push_front/push_back 导致新缓冲区分配）时，**所有迭代器都可能失效**——即使你只是在尾部插入，begin() 返回的迭代器也可能变无效。这是因为它内部的 map 可能被 realloc，导致所有缓存的缓冲区指针地址作废。
而 vector 至少保证尾插不使已有迭代器失效（除非触发扩容）。所以：
- 永远不要在循环中边遍历
deque边push_front/push_back，除非你重新获取迭代器 -
erase单个元素只使指向被删位置的迭代器失效；但erase范围可能导致后续缓冲区重排，实践中建议视为“该范围及之后的迭代器全部失效” - 对
deque使用auto it = c.begin(); ++it;是安全的，但it += 1000后再push_back，it就不可用了
什么场景下该选 deque 而不是 vector 或 list
别为了“双端”就无脑选 deque。它真正的优势场景很窄：
- 频繁在头尾做
push/pop，且元素类型较大（避免vector头插时的大块内存搬移） - 需要随机访问（
operator[]），但又不能接受vector中间插入的 O(n) 搬移成本（这时你其实应该 rethink 设计） - 内存分配受限：
deque分配小块内存，比vector一次性大 alloc 更易成功（尤其在嵌入式或长期运行服务中）
反例：如果你只用 push_back 和 operator[]，vector 几乎总是更好；如果你真需要高频中间插入/删除且不关心随机访问，list（或 forward_list）更合适——尽管 cache 性能差，但语义清晰。
最容易被忽略的一点：deque 的 sizeof 比 vector 大得多（至少含两个指针 + 两个 size_t + 一个 map 指针），小对象、短生命周期容器时，这个开销明显。
