std::deque 的随机访问为什么比 vector 慢但仍是 O(1)
因为 std::deque 不是连续内存块，而是分段连续的缓冲区（通常为固定大小的数组）组成的链表结构。索引访问需先计算段号和段内偏移，涉及两次指针解引用和除法取模运算，而 std::vector 直接 base + i 即可。实测在大量随机读写时，deque 的访存延迟通常高出 2–3 倍。
典型使用场景：需要频繁在首尾插入/删除，且偶尔按索引读取（如实现滑动窗口、撤销栈、BFS 队列中需回溯中间元素）。
- 不要用
deque替代vector仅为了“支持 push_front”——若无首部修改需求，vector更快更省内存 - 默认缓冲区大小由标准库实现决定（libstdc++ 通常为 512 字节，MSVC 约 16 个元素），不可配置；不要假设其值
- 迭代器失效规则宽松：仅首尾插入不使其他迭代器失效，但
erase中间元素仍会使所有迭代器失效（与vector一致）
如何安全地在 deque 开头插入并避免意外拷贝
push_front() 和 emplace_front() 行为差异关键在于构造方式：push_front 先构造临时对象再移动/拷贝入容器；emplace_front 直接在容器内部内存原位构造。对自定义类型尤其重要。
以下示例中，MyClass 的移动构造函数会被 emplace_front 调用，而 push_front 可能触发额外拷贝（取决于编译器优化）：
立即学习“C++免费学习笔记（深入）”；
struct MyClass {
MyClass(int x) : val(x) { std::cout << "ctor\n"; }
MyClass(const MyClass& other) : val(other.val) { std::cout << "copy ctor\n"; }
MyClass(MyClass&& other) noexcept : val(other.val) { std::cout << "move ctor\n"; }
int val;
};
std::deque dq;
dq.emplace_front(42); // 输出: ctor
dq.push_front(MyClass(99)); // 输出: ctor → move ctor（或 copy ctor，若未启用 RVO）
- 始终优先用
emplace_front/emplace_back，尤其参数复杂或类型昂贵时 -
push_front({a, b, c})是合法的，但会调用初始化列表构造函数；确认类是否支持 - 注意：
deque不提供reserve()，无法预分配首尾空间，频繁小量push_front可能引发多次缓冲区分配
迭代 deque 时哪些操作会导致未定义行为
最常见误用是边遍历边修改首尾以外的位置。例如在 for-range 循环中调用 erase(iterator) 后继续用原迭代器 ++ —— 这在 deque 中是未定义行为，因为 erase 可能使后续迭代器失效（即使只删一个元素）。
正确做法是使用返回的迭代器（C++11 起 erase 返回下一个有效位置）：
std::dequedq = {1, 2, 3, 4, 5}; for (auto it = dq.begin(); it != dq.end(); ) { if (*it % 2 == 0) { it = dq.erase(it); // ✅ 安全 } else { ++it; } }
-
pop_front()和pop_back()不影响其他迭代器，可安全混用遍历 - 但
insert(pos, ...)或erase(pos)在非端点位置操作后，所有现存迭代器、指针、引用均可能失效（标准未保证，各实现通常全部失效） - 不要依赖
deque[0]和&deque[0]获取首元素地址来模拟 C 数组——该地址不指向连续数据起点，且不能用于std::sort等算法
deque 与 list、vector 在典型操作下的性能对比
选择依据不是“功能覆盖”，而是具体操作频次与数据规模。以下是常见操作的渐进复杂度与实际倾向：
-
push_front/push_back：三者都是摊还 O(1)，但deque实际常数最小（无需重新分配+拷贝整个块，只需新增/复用缓冲区） -
random access（如dq[i]）：vector 最快，deque 次之（缓存局部性差），list 是 O(n) -
insert/erase at middle：list 是 O(1)（给定迭代器），deque 和 vector 都是 O(n)；但 deque 的移动开销远小于 vector（只挪本缓冲区内元素，而非整块内存） - 内存占用：deque > vector（多出指针数组和缓冲区管理开销），deque ≈ list（但 list 每节点额外两个指针）
真正容易被忽略的是：当元素类型很大（如 std::array）且只做首尾操作时，deque 的缓存友好性反而可能优于 vector——因为 vector 每次 push_back 触发扩容时要 memcpy 几 KB 数据，而 deque 只复制指针和少量元数据。
