std::deque两端插入删除比vector快，因其分段连续存储，首尾操作不触发整体搬移；但中间操作仍为O(n)且缓存不友好，仅适用于频繁首尾增删+随机访问场景。
std::deque 的插入和删除为什么比 vector 快？
因为 std::deque 内部是分段连续存储（通常为固定大小的缓冲区数组），两端插入/删除只需操作首尾缓冲区，不触发整体内存搬移。而 std::vector 在头部插入（insert(begin(), x)）会平移全部元素，O(n) 开销。
但注意：中间位置操作（如 insert(iterator, x) 或 erase(iterator)）在 std::deque 中仍是 O(n)，且常数因子比 vector 更大——它要定位缓冲区、处理跨段指针，实际性能可能更差。
- 只在真正需要「频繁首尾增删」时用
deque，别因为它“支持随机访问”就替代vector -
push_front()/pop_front()是安全且高效的；push_back()/pop_back()效率与vector相当 - 避免对非首尾迭代器调用
erase()，尤其在循环中——容易误判时间复杂度
迭代器失效规则和 vector 有什么不同？
std::deque 迭代器在「首尾插入/删除」时不会失效，这是关键优势；但中间插入或删除仍会使所有迭代器失效（C++11 起标准明确要求）。而 vector 只要容量不变，push_back() 不会让已有迭代器失效。
常见踩坑：for (auto it = dq.begin(); it != dq.end(); ++it) 中调用 dq.pop_front() —— 表面看没改 it，但 pop_front() 后 begin() 已变，it 可能指向已释放缓冲区，UB（未定义行为）。
立即学习“C++免费学习笔记（深入）”；
- 首尾操作后，原有
begin()/end()迭代器失效，但其他有效迭代器（如指向中间元素的）通常仍可用 - 用范围 for 循环时，禁止在循环体内修改容器大小（包括
push_front/pop_front） - 需要边遍历边删首尾？改用
while (!dq.empty()) { auto x = dq.front(); dq.pop_front(); ... }
内存布局导致的 cache 友好性问题
std::deque 每个缓冲区内部连续，但缓冲区之间不连续，CPU 缓存预取难以覆盖跨段访问。顺序遍历 deque 的性能通常弱于 vector，尤其在数据量大、访问密集时。
典型现象：把原本用 vector 的队列逻辑换成 deque 后，吞吐没提升，反而 L1/L2 cache miss 上升 20%+。
- 如果主要操作是「顺序读 + 尾插」，
vector几乎总是更快；deque的价值仅在「头插/头删 + 随机访问」共存场景 - 缓冲区大小由实现决定（libstdc++ 默认 512 字节，MSVC 约 16 个元素），无法配置，别试图“优化”它
- 用
valgrind --tool=cachegrind或 perf 实测cache-misses，别凭直觉选容器
和 std::list 对比：什么时候该选 deque？
std::list 是真正的链表，任意位置插入/删除都是 O(1)，但不支持随机访问（operator[] 或 at() 是 O(n)）；deque 支持 O(1) 随机访问，但中间操作是 O(n)。两者不是替代关系，而是需求错位。
错误选择示例：想实现一个“可快速删中间元素的队列”，直接换 list —— 结果后续代码大量用 [i] 索引，性能崩盘。
- 需要
front()/back()+[i]+size()→ 用deque - 需要频繁
erase(iterator)且位置不固定，又不依赖下标 → 用list（但先确认是否真需要双向链表语义） - 现代 C++ 中，
std::vector配合erase-remove惯用法，往往比list更快——别迷信“链表一定适合删中间”
std::deque 时，最易被忽略的是它对「缓存局部性」和「迭代器稳定性」的隐含权衡——不是语法会写就能避开陷阱，得看清楚你到底在优化哪条路径。 
