deque头部插入快于vector，因其分段缓冲区结构避免元素移动和频繁扩容；vector头插需O(n)平移元素且易触发全量拷贝，缓存不友好；但元素极少或混合随机访问时deque可能因map开销和指针跳转变慢。
deque 头部插入的底层机制
std::deque 不是单块连续内存，而是由多个固定大小的缓冲区（通常 512 字节或 4KB）组成的分段数组，通过中控 map（指针数组）索引。头部插入时，只要当前首段 buffer 有空余空间，就直接在 front() 位置前写入——不挪动任何已有元素，也不触发重新分配。
而 std::vector::insert(vec.begin(), x) 在头部插入必须把全部现有元素向后平移一位，时间复杂度 O(n)，且可能触发扩容：若容量不足，需分配新内存、memcpy 全量数据、销毁旧对象。
vector 头插慢的真正瓶颈在哪
性能差距不只来自“移动元素”，更关键的是内存行为：
- vector 频繁头插极易导致反复扩容——每次扩容都伴随一次全量拷贝 + 旧内存释放，缓存不友好
- 即使预留足够容量（
vec.reserve(N)），头插仍要移动所有已存在元素，CPU 指令数和 cache line 命中率都差 - deque 的分段结构天然避免大块 memcpy，各 buffer 内部局部性好，map 查找开销固定且极小（通常 ≤ 2 次指针跳转）
什么时候 deque 头插反而不快
不是所有场景 deque 都赢。以下情况要注意：
立即学习“C++免费学习笔记（深入）”；
- 元素类型很大但数量极少（比如只有 3–5 个
std::array<char></char>），deque 的 map 管理开销和跨 buffer 访问成本可能超过 vector 的简单移动 - 频繁混合头尾插入 + 随机访问 —— deque 的随机访问虽是 O(1)，但常数比 vector 高（两次指针解引用 + map 索引计算），尤其在 tight loop 中易被 profiler 捕捉到
- 使用
std::deque::emplace_front()时若构造函数抛异常，deque 的强异常安全保证会回滚部分操作，而 vector 头插失败时状态不可预测（C++11 起标准要求 deque 提供强保证，vector 不保证）
实测对比的关键控制点
想自己验证？避开常见干扰：
- 关闭 ASLR 和 malloc 调试（如
export MALLOC_CHECK_=0），否则 deque 的多段分配可能被误判为碎片化慢 - 用
std::deque::max_size()和std::vector::max_size()确认两者都未触达平台限制（尤其 32 位环境） - 测试时统一用
emplace_front()/emplace(vec.begin(), ...)，避免构造临时对象干扰计时 - 注意 allocator：默认
std::allocator下 deque 的 buffer 分配器实际是__gnu_cxx::__pool_alloc（libstdc++）或类似池式实现，它对小 buffer 复用高效；换成std::pmr::polymorphic_allocator可能改变结果
真正卡脖子的地方往往不在算法复杂度标称值里，而在 allocator 行为、cache line 对齐、以及你没意识到的 move 构造函数是否 noexcept。
