deque 是什么，和 vector 有什么本质区别
deque 不是 vector 的“加强版”，也不是“带头尾插入的 vector”。它的内存布局是分段连续的：由多个固定大小的缓冲区（通常为 512 字节或按元素大小对齐）组成，通过中控数组（map）索引。这决定了它支持 O(1) 头尾插入/删除，但不保证整体内存连续——所以 &v[0] 不能安全转成原生指针数组，std::sort 也不能直接用于整个 deque（会编译失败或行为未定义）。
常见误用场景：
- 把
deque当作vector用，频繁调用operator[]并期望缓存友好 —— 实际跳转开销比 vector 高 - 传
deque::data()给 C 接口 ——deque没有data()成员函数（C++11 起只有vector和string有） - 假设
push_back后所有迭代器永不失效 —— 实际上头尾插入只使对应端的迭代器失效，中间迭代器仍有效，这点比 vector 更宽松
哪些操作是真正 O(1)，哪些是假的 O(1)
标准明确保证头尾插入/删除、随机访问（operator[]、at()）、front()/back() 是常数时间。但“常数”不等于“快”：每次 operator[] 需要两次指针运算（查中控数组 + 偏移计算），而 vector 是一次地址加法。
容易被忽略的非 O(1) 操作：
立即学习“C++免费学习笔记（深入）”；
-
insert(pos, value)或erase(pos)在中间位置 —— 时间复杂度是O(min(pos, size() - pos))，因为 deque 会选择从头还是从尾搬运元素 -
resize(n)当n > size()时，可能触发多次缓冲区分配；当n 时，若缩容跨缓冲区边界，需逐个析构元素 -
assign(first, last)若范围很大，内部可能反复调用push_back或push_front，实际性能不如先 clear 再 reserve（但 deque 不支持 reserve）
迭代器失效规则和真实使用建议
deque 迭代器失效比 vector 更复杂，但规律清晰：仅当操作影响到该迭代器所处的缓冲区时才失效。例如：
-
push_back()：仅使end()迭代器失效；其他所有迭代器（包括指向末元素的--end()）保持有效 -
push_front()：仅使begin()失效；begin()+1及之后全部有效 -
pop_back()：仅使指向原末元素的迭代器失效；end()自动更新，不额外失效 -
clear()：所有迭代器、引用、指针全部失效（因为所有缓冲区都被释放）
实操建议：
- 避免在循环中边遍历边
erase中间元素 —— 改用remove_if+erase(remove_if(...), end())惯用法 - 若需频繁中间插入且在意性能，考虑改用
list（但失去随机访问）或vector（配合erase后shrink_to_fit） - 多线程下，即使只读访问也要注意：
size()不是原子操作，某些实现中可能因缓冲区扩展导致临时重算
内存占用与跨平台兼容性陷阱
deque 的内存开销远大于 vector：除元素本身外，还需中控数组（通常 8~64 个指针）+ 每个缓冲区的管理头（如容量/使用长度）。32 位系统上一个空 deque 可能占 40~80 字节，而 vector 仅 12 字节。
更隐蔽的问题是 allocator 行为差异：
- libstdc++（GCC）默认使用
__gnu_cxx::__pool_alloc管理缓冲区，可能复用已释放的缓冲区，导致观察不到内存立即释放 - libc++（Clang）使用
std::allocator直接分配，更可预测但无池化优化 - Windows MSVC 的 deque 实现在 VS2015 前有严重迭代器调试检查开销，开启
_ITERATOR_DEBUG_LEVEL=2时性能暴跌
如果你看到：
- valgrind 报告 deque 析构后仍有内存未释放 —— 很可能是分配器池未清空，不是泄漏
- 不同编译器下
sizeof(deque差异很大 —— 这是正常实现差异，不要硬编码偏移) - 用
std::deque替代std::string做缓冲区 —— 别这么做，string有 SSO 优化，deque 没有
std::dequed = {1, 2, 3}; d.push_front(0); // OK: d == {0,1,2,3} auto it = d.begin(); // it points to 0 d.pop_front(); // it is now invalid // 使用 it 将导致未定义行为 —— 即使它看起来还能解引用
最常被低估的是缓冲区大小策略：不同标准库实现对“缓冲区长度”的选择逻辑不同（有的按元素大小动态算，有的固定 512 字节），这意味着相同代码在 GCC 和 Clang 下，capacity()（如果 deque 提供该接口，注意：标准并未要求）或实际内存占用可能差数倍。真正在意内存时，别只看 size()。
