deque是支持首尾高效增删的随机访问容器，与vector的关键区别在于：deque首尾操作为O(1)均摊复杂度且迭代器局部失效，而vector首部操作为O(n)、仅扩容时全局失效；deque不保证内存连续、无data()函数、缓存局部性更差。
deque 是什么，和 vector 有什么关键区别
std::deque（double-ended queue）是 C++ 标准库中支持在头尾两端高效插入/删除的序列容器。它不是“队列”语义上的 FIFO 结构，而是一种底层基于分段连续内存（通常为固定大小的缓冲区数组）实现的随机访问容器。
与 std::vector 最核心的区别在于：deque 在首部执行 push_front() 或 pop_front() 是 O(1) 均摊复杂度；而 vector 的同类操作是 O(n) —— 因为要整体移动元素。但代价是：deque 的迭代器、指针、引用在插入/删除后**可能失效**（特别是涉及内存段重分配时），而 vector 只有在扩容时才使全部迭代器失效。
-
deque不保证内存整体连续，因此不支持data()成员函数（C++11 起vector有） -
deque的随机访问虽为O(1)，但常数因子比vector大，缓存局部性更差 - 若只需尾部增删，优先用
vector；若明确需要高频首尾操作（如滑动窗口、任务队列头部插紧急任务），再选deque
常用操作：构造、增删、访问、遍历
所有操作都需包含头文件 <deque>，并使用 std::deque<T> 模板声明。
典型用法示例如下：
立即学习“C++免费学习笔记（深入）”；
#include <deque>
#include <iostream>
int main() {
std::deque<int> dq = {1, 2, 3}; // 初始化列表构造（C++11）
dq.push_back(4); // → [1,2,3,4]
dq.push_front(0); // → [0,1,2,3,4]
dq.pop_back(); // → [0,1,2,3]
dq.pop_front(); // → [1,2,3]
std::cout << dq.front() << " " << dq.back() << "\n"; // 输出: 1 3
for (auto x : dq) std::cout << x << " "; // 范围 for 遍历：1 2 3
return 0;
}
-
front()/back()返回首/尾元素的引用，容器为空时行为未定义（不检查） -
at(index)提供带边界检查的随机访问，越界抛std::out_of_range；operator[]不检查，更快但更危险 -
erase(iterator)或erase(first, last)可删除任意位置元素，但中间删除效率不如list（仍需搬移后续段） -
clear()清空所有元素，但**不保证释放内存**（capacity 可能不变）
迭代器失效规则：哪些操作会让 iterator 失效
这是 deque 最容易被忽略也最易出错的部分。和 vector 不同，deque 的失效规则更细粒度：
-
push_front()/push_back()：仅使指向被插入位置的迭代器失效（即新元素的begin()或end()-1）；其余迭代器、引用、指针**通常保持有效** -
pop_front()/pop_back()：仅使指向被删元素的迭代器失效；其余不受影响 -
insert()/erase()在中间：会使**所有迭代器、指针、引用失效**（C++11 起标准明确要求） -
resize()/assign()：若容量变化，可能触发重新分段，导致全部失效
所以，如果你在循环中一边遍历一边调用 erase(it++)，且 it 是中间位置的迭代器——这次 erase 后，it++ 就是野指针行为。务必改用返回值方式：it = dq.erase(it)。
性能敏感场景下的替代建议
当实测发现 deque 成为瓶颈（比如大量小对象频繁首尾操作 + 缓存 miss 严重），可考虑以下实际替代方案：
- 用两个
std::stack<T>模拟双端队列（一个存前半，一个存后半），适合只关心头尾、不需随机访问的场景 - 用
std::list<T>：插入/删除任意位置都是O(1)，但失去随机访问能力，且每个节点额外占用指针空间 - 手写环形缓冲区（
std::array<T, N>+size_t head, tail）：零分配、极致缓存友好，但容量固定，且需自行处理满/空判断 - 若只是偶尔首插，且数据量不大，直接用
vector.insert(vec.begin(), x)有时反而更简单、更不易出错
真正需要 deque 的时刻，往往是在你已经确认：必须动态容量 + 高频首尾操作 + 需要随机访问索引 —— 这三个条件同时成立。
