deque 是什么？
双端队列（两头都能高效插入/删除）
deque<int> d; d.push_back(1); d.push_front(2);deque 和 vector 的本质区别
vector：一整块连续内存deque：分段连续（块状结构）
deque 底层结构
deque不是一块内存，而是：
中控数组（map）
↓ ↓ ↓ ↓ ↓
[块][块][块][块]
中控数组（map）
存的是“指针”
map: [ ptr ][ ptr ][ ptr ]
↓ ↓
block block
每个 block（缓冲区）
每个 block 是一段连续内存（比如 512 字节）
block1: [1 2 3]
block2: [4 5 6]
总体结构：
map → 多个连续小块 → 拼起来像连续
为什么要这样设计？
解决 vector 的一个痛点：
vector 头插很慢
v.insert(v.begin(), 10); // O(n)deque 两头都快
因为：
头部还有空间 直接插
不够 新开一个 block
不需要整体搬家
deque 的时间复杂度
| 操作 | 复杂度 |
|---|---|
| 随机访问 | O(1) |
| 尾插 | O(1) |
| 头插 | O(1) |
| 中间插入 | O(n) |
deque 的迭代器
deque迭代器不是普通指针
因为：
数据不是一整块连续内存
迭代器内部结构
struct deque_iterator { T* cur; // 当前元素 T* first; // 当前块起始 T* last; // 当前块结束 T** node; // 指向 map 中的块指针 };移动时：
++it:
如果到块末尾 → 跳到下一个 block
deque vs vector
| 对比 | vector | deque |
|---|---|---|
| 内存 | 完全连续 | 分段连续 |
| 随机访问 | O(1) | O(1) |
| 头插 | 慢 | 快 |
| 尾插 | 快 | 快 |
| 扩容 | 整体搬家 | 分块扩展 |
| cache | 非常好 | 略差 |
deque 的优缺点
优点
两端插入删除 O(1)
不需要整体扩容搬家
支持随机访问
缺点
结构复杂
cache 不如 vector
迭代器复杂（容易失效）
iterator 失效
deque 比较“中间态”：
插入可能导致 map 扩容 → 迭代器失效
d.push_back(10); // 可能失效中间插入 → 基本全失效
deque：比 vector 稳一点，但不如 list 稳
