C++入门自学Day14-- deque类型使用和介绍（初识）
往期内容回顾
Queue介绍和使用
Stack介绍和使用
C++ STL 容器系列 —— 双端队列 std::deque
前言
在学习了 vector（连续动态数组）与 list（双向链表）之后，你会发现：如果既想要随机访问，又想要在两端高效插删，std::deque（double-ended queue）往往是更均衡的选择。它是 STL 中极具工程价值的顺序容器：支持随机访问、两端 O(1) 插删、良好的扩展性。同时，STL 的两个经典容器适配器——std::stack 与 std::queue——默认都以 deque 为底层实现，这并非偶然，而是性能与语义权衡的结果。
主要内容
-
1、deque 是什么：定位、特点、和 vector/list 的对比
-
2、deque 的内部模型：分段缓冲区 + 中央索引（block-map）
-
3、常用接口与用法清单（含代码示例）
-
4、复杂度与迭代器/引用失效规则（非常重要）
-
5、deque 与 stack/queue 适配器：为什么它是默认选择
-
6、常见坑位与工程实践建议
-
总结
一、deque是什么（与 vector / list 的对比）
-
定位：双端队列（Double-ended queue），支持随机访问（迭代器为随机访问迭代器），并在两端进行常数时间的插入/删除。
-
对比：
-
vs vector：vector 在尾部插入快，但头部插入/删除昂贵；deque 两端都快。vector 的内存完全连续，deque 逻辑上连续、物理上分段。
-
vs list：list 插删稳定、节点额外开销大，且不支持随机访问；deque 支持随机访问、整体吞吐更好，但中间插入/删除仍然不是强项（需要移动一段元素）。
-
典型使用场景
-
需要频繁 push_front/push_back，又要数组式访问：如任务队列、缓冲区、编辑器撤销栈等。
-
算法里“窗口两端弹入弹出”的模式：如 滑动窗口、BFS 的队列等。
二、内存布局：分段缓冲区 + 中央索引
deque 并非像 vector 一样是一整块连续内存，它通常由 若干定长“缓冲块” 组成，这些块的指针再由一张**中央索引表（map）**管理：
[ map: | *block0 | *block1 | *block2 | ... ]
| | |
v v v
[slot...] [slot...] [slot...]
-
逻辑连续：对用户来说 operator[] 像数组一样；内部通过“块索引 + 块内偏移”定位。
-
两端扩展：在前端或后端再挂一块新缓冲区即可，避免整体搬家，因此两端插删稳定且高效。
-
中间操作：在中部插/删需要移动一段元素跨块调整，成本较高。
简单示意图：
map 控制中心（指针数组）：
┌───────┬───────┬───────┬───────┐
│ p0 │ p1 │ p2 │ p3 │
└───────┴───────┴───────┴───────┘
↓ ↓ ↓p0 → ┌──────┬──────┬──────┬──────┐
│ 1 │ 2 │ 3 │ 4 │
└──────┴──────┴──────┴──────┘p1 → ┌──────┬──────┬──────┬──────┐
│ 5 │ 6 │ 7 │ 8 │
└──────┴──────┴──────┴──────┘p2 → ┌──────┬──────┬──────┬──────┐
│ 9 │ 10 │ │ │ ← 目前 end 在这里
└──────┴──────┴──────┴──────┘
begin → 指向 p0 的第一个元素 (1)
end → 指向 p2 的第三格（即 10 之后的位置）
这种设计解释了两个关键特性：
随机访问可用；2) push_front / push_back 对现有元素的引用通常更稳定（详见后文“失效规则”）。
三、常用接口与用法清单
#include <deque> #include <iostream> using namespace std;int main() {deque<int> dq = {1, 2, 3};// 1) 两端插入/构造dq.push_front(0); // [0,1,2,3]dq.push_back(4); // [0,1,2,3,4]dq.emplace_front(-1); // [-1,0,1,2,3,4]dq.emplace_back(5); // [-1,0,1,2,3,4,5]// 2) 访问cout << dq.front() << " " << dq.back() << "\n"; // -1 5cout << dq[2] << " " << dq.at(3) << "\n"; // 1 2（at 有越界检查）// 3) 删除（两端 O(1)）dq.pop_front(); // [0,1,2,3,4,5]dq.pop_back(); // [0,1,2,3,4]// 4) 中间操作（不建议频繁使用）dq.insert(dq.begin() + 2, 42); // [0,1,42,2,3,4]dq.erase(dq.begin() + 3); // [0,1,42,3,4]// 5) 其他cout << dq.size() << " " << boolalpha << dq.empty() << "\n";dq.clear(); // 清空 }
接口要点
-
构造/赋值：与其他序列容器类似（范围构造、拷贝、移动、assign）。
-
随机访问：operator[]、at()、迭代器为随机访问迭代器。
-
修改：push_front/back、emplace_front/back、insert、erase、clear、resize、shrink_to_fit()（非强制收缩）。
-
复杂度：两端插删均摊 O(1)，中间插删 O(n)。
四、复杂度与「迭代器/引用失效规则」
这是 deque 的高频考点与踩坑源头，务必搞清楚。
大结论（按标准描述）
-
在两端插入（push_front/back / emplace_front/back / insert at ends）：
-
迭代器：可能全部失效；
-
引用/指针：不失效（指向的元素地址不变，除非你引用的就是被插入/擦除的那个）。
-
-
在两端擦除（pop_front/back / erase at ends）：
-
被擦除元素的迭代器/引用/指针失效；其他元素的引用不失效，迭代器可能失效；
-
-
在中间插入/擦除（非两端）：
-
所有迭代器与引用通常都失效（需要移动跨块元素）。
-
这些规则与实现细节强相关，但在主流实现与资料上是一致结论；你在工程里应默认保守处理：对 deque，两端操作后不要继续使用旧迭代器；中间操作后不要继续使用旧迭代器和旧引用。
小贴士：为什么“引用不失效而迭代器会失效”？
迭代器内部还携带块/索引等元信息，map 重排会让旧迭代器语义不再成立；但元素本身仍在原内存块，所以指向它的原始引用/指针仍有效（两端插入/擦除时）。这一点在多篇权威材料中都有说明。
详细表（操作 / 复杂度 / 迭代器 & 引用失效规则）
下表中的“迭代器失效”指 iterator / const_iterator；“引用失效”包括 T& / T*（指针）等。
操作
时间复杂度（典型）
迭代器失效
引用/指针失效
operator[] / at / random access
O(1)
无
无。
push_back / emplace_back / push_front / emplace_front
常数（实现上通常为 O(1) / 摊销 O(1)）
所有迭代器（包括 end()）会被失效（标准页对这些成员的说明）。
引用/指针通常不失效（元素内存不被移动）。
pop_back / pop_front
常数
仅失效指向被删元素的迭代器；end()可能特殊（见下文）
非被删元素的引用不失效（通常）。
insert(pos, ...)（中间）
线性（取决于插入数量与距离两端的较小值）
失效所有迭代器；参见标准细则（在两端插入是例外，见下行）。
引用也失效（中间插入会使引用失效，除非插入点是 begin() 或 end()）。
insert 在两端（等同 push_xx）
同上（常数）
迭代器失效
引用/指针不失效（两端插入的特殊规则）。
erase(pos)（中间）
线性（被删元素数 + 最短搬移距离）
失效所有迭代器与引用（除当只删首或尾时的例外）。
同上。
erase 在两端（pop_front/pop_back）
常数（通常）
仅失效指向被删元素的迭代器；end()在某些情形下也被失效（例如删除最后一个元素会使 end() 失效）。
非被删元素的引用通常保持有效。
clear() / 析构整个容器
O(n)
失效所有迭代器与引用
失效所有引用/指针（元素被销毁/内存释放）。
shrink_to_fit()
实现相关（请求）
失效所有迭代器与引用（实现可能重新安排内存）。
swap(other)
常数
迭代器/引用保持有效（仍指向相同元素），但 end() 可能被视作变化/失效（标准对 end() 有特殊说明）。
典型代码示例（演示失效与不失效）
迭代器被失效（不要这么写）：
std::deque<int> d = {1,2,3}; auto it = d.begin(); d.push_back(4); // push_back 会失效迭代器（包括 it），因此下面是 UB int x = *it; // ❌ UB：it 已失效指针/引用在两端插入通常仍然有效（但不是绝对保证）：
std::deque<int> d = {1,2,3}; int* p = &d[0]; d.push_front(0); // 迭代器失效，但 p 指向的元素（值为 1）通常仍有效 std::cout << *p << '\n'; // 大多数实现下是安全的，输出 1中间插入会使引用失效：
std::deque<int> d = {1,2,3}; int* p = &d[1]; // 指向 2 d.insert(d.begin()+1, 99); // 在中间插入 -> 所有引用/迭代器失效 // *p 现在是悬挂指针，不能使用（上面行为依标准：中间插入会使引用失效）
五、为什么 stack / queue 默认用 deque作为底层？
-
std::stack（后进先出）只需要 push_back / pop_back / back / empty / size；
-
std::queue（先进先出）需要 push_back / pop_front / front / back / empty / size；
-
deque 对这两类操作天然友好（两端 O(1)），且保留了良好的整体吞吐与随机访问能力；
-
vector 没有 pop_front，不适合 queue；
-
list 支持，但局部性差、节点额外内存大，综合性能往往不如 deque。
因此标准库让 deque 成为二者的默认底层容器（你也可以自行指定 list 作为底层）。
六、常见坑位与工程实践
-
不要在中间频繁插删
deque 的强项是两端。如果你需要大量中间插删，考虑 list 或换数据结构/算法。
-
修改后谨慎使用旧迭代器/引用
-
两端插入/擦除后：迭代器作废，引用通常仍有效（非被删元素）。
-
中间插删后：迭代器与引用都作废。
建议局部使用、就近取值，不要长时间持有。
-
-
shrink_to_fit() 是“非强制性”
标准允许实现忽略收缩请求，不能依赖它做严格的内存回收。
-
性能认知
-
deque 随机访问是 O(1)，但相对 vector 多一次“块定位”的间接成本；
-
大量小对象、热点遍历场景，vector 的缓存局部性往往更优；
-
两端插删重度使用时，deque 明显占优。
-
-
线程安全
与大多数 STL 容器一样，非线程安全；多线程需外部同步或专用并发结构。
总结
-
std::deque = 随机访问 + 两端高效插删 + 分段存储；在“既要两端 O(1) 又要随机访问”的场景里，它是标准答案。
-
内部模型决定了：两端扩展通常只影响迭代器（可能全部失效），而不使现有元素引用失效；中间插删则可能全部失效。工程里务必保守处理迭代器/引用的生命周期。
-
stack / queue 适配器默认用 deque：它恰好提供了所需操作的常数时间语义，并兼顾整体吞吐与易用性。
-
选型口诀：
-
只尾插/随机访问强 → vector；
-
两端频繁插删 + 随机访问 → deque；
-
大量中间插删/稳定迭代器 → list（接受节点额外开销）。
-
-
把 deque 与适配器一起学习，可以更深刻地体会 STL 的设计哲学：以语义约束能力，用组合优于继承，在性能与正确性之间取得工程化的平衡。
进一步阅读（参考迭代器/引用失效细节与语义）：cppreference 对 deque 的页面与成员函数条目，对上文规则有准确描述与表格总结。