一、核心特性与底层模型#
| 特性 | 说明 |
|---|---|
| 双端操作 | push_front / pop_front / push_back / pop_back 都是均摊 O(1) |
| 随机访问 | 支持 d[i],O(1),但常数比 vector 大 |
| 底层结构 | 分段连续:多个固定大小的缓冲区,由一个”中控 map”指针数组索引 |
| 头部插入高效 | 头部空位不够时只需新分配一个分段,不需要整体搬移 |
| 内存不整体连续 | 不能像 vector 那样用 &d[0] 当 C 数组用 |
无 capacity/reserve |
接口里没有容量管理 |
vector: [________________] 一整段连续内存,头部插入 O(n)
deque: [分段1][分段2][分段3] 逻辑连续,物理分段,头尾扩展都只动一个分段plaintext与 vector 的本质差异:
vector扩容 = 整段重新分配 + 全部拷贝;deque头尾扩展 = 最多新分配一个分段,已有元素不搬移。
二、头文件与初始化#
#include <deque>
#include <iostream>
using namespace std;
int main() {
deque<int> d1; // 空
deque<int> d2(5); // 5 个 0
deque<int> d3(5, 7); // 7 7 7 7 7
deque<int> d4 = {1, 2, 3, 4}; // 列表初始化
deque<int> d5(d4.begin(), d4.end()); // 区间拷贝
deque<int> d6(d4); // 拷贝构造
}cpp三、核心接口#
1. 双端增删(灵魂接口)#
deque<int> d = {3, 5, 7};
d.push_front(1); // 1 3 5 7
d.push_back(9); // 1 3 5 7 9
d.emplace_front(0); // 0 1 3 5 7 9
d.emplace_back(11); // 0 1 3 5 7 9 11
d.pop_front(); // 1 3 5 7 9 11
d.pop_back(); // 1 3 5 7 9
int f = d.front(); // 1
int b = d.back(); // 9cpp注意:pop_front / pop_back 不返回元素,且空容器上调用是未定义行为。先判空!
2. 随机访问与遍历#
deque<int> d = {10, 20, 30, 40, 50};
d[2]; // 30,不检查越界
d.at(2); // 30,越界抛 out_of_range
// 三种遍历
for (int i = 0; i < (int)d.size(); i++) cout << d[i];
for (int x : d) cout << x;
for (auto it = d.begin(); it != d.end(); ++it) cout << *it;
// 反向
for (auto it = d.rbegin(); it != d.rend(); ++it) cout << *it;cpp3. 中间操作(存在但慎用)#
auto it = d.insert(d.begin() + 2, 99); // 中间插入 O(n)
d.erase(d.begin() + 2); // 中间删除 O(n)
d.erase(d.begin() + 1, d.begin() + 3); // 删区间cpp中间插入删除需要移动元素,O(n),且 deque 的迭代器是随机访问迭代器,可以 it + k。
4. 其他#
d.size();
d.empty();
d.clear();
d.resize(10); // 调整元素个数
d.assign(5, 0); // 替换为 5 个 0
d.swap(d2); // O(1) 交换内容cpp四、复杂度表#
| 操作 | 复杂度 |
|---|---|
push_front / push_back |
均摊 O(1) |
pop_front / pop_back |
O(1) |
d[i] / at |
O(1)(常数大于 vector) |
front / back |
O(1) |
中间 insert / erase |
O(n) |
| 遍历 | O(n) |
与 vector 的完整对比:
| 操作 | vector |
deque |
|---|---|---|
| 尾部 push/pop | 均摊 O(1) |
均摊 O(1) |
| 头部 push/pop | O(n) |
O(1) |
| 下标访问 | O(1),快 |
O(1),略慢(多一层分段定位) |
| 内存连续性 | 整体连续 | 分段连续 |
| 迭代器失效 | 扩容全失效 | 头尾插入通常不移动元素,但迭代器仍会失效(见下) |
data() / 当 C 数组 |
支持 | 不支持 |
五、迭代器失效规则(比 vector 复杂,竞赛记住结论即可)#
| 操作 | 影响 |
|---|---|
push_back / push_front |
所有迭代器失效,但已有元素的引用和指针保持有效 |
pop_back / pop_front |
仅被删端点的迭代器/引用失效 |
中间 insert / erase |
全部迭代器、引用失效 |
resize 缩小 |
被删部分失效 |
clear |
全部失效 |
竞赛简化记忆:deque 做任何插入删除后,都不要继续使用旧迭代器,重新 begin()。
六、竞赛应用模板#
1. 单调队列:滑动窗口最值(最经典)#
对每个长度为 k 的窗口,求最大值。
O(n)完成。
#include <deque>
#include <vector>
using namespace std;
vector<int> maxSlidingWindow(vector<int>& a, int k) {
deque<int> dq; // 存下标,对应值单调递减
vector<int> ans;
for (int i = 0; i < (int)a.size(); i++) {
// 1. 弹出队首中滑出窗口的下标
while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
// 2. 维护单调性:弹出所有 <= a[i] 的队尾
while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
// 3. 入队
dq.push_back(i);
// 4. 窗口形成后记录答案
if (i >= k - 1) ans.push_back(a[dq.front()]);
}
return ans;
}cpp要点:
- 队列里存下标而不是值,方便判断是否滑出窗口;
- 队首始终是当前窗口最大值的下标;
- 每个下标最多入队、出队一次,总复杂度
O(n)。
2. 0-1 BFS#
边权只有 0 和 1 的最短路:权 0 的边放队首,权 1 的边放队尾,代替 Dijkstra。
deque<int> dq;
vector<int> dist(n, INF);
dist[s] = 0;
dq.push_front(s);
while (!dq.empty()) {
int u = dq.front(); dq.pop_front();
for (auto [v, w] : g[u]) { // w ∈ {0, 1}
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (w == 0) dq.push_front(v);
else dq.push_back(v);
}
}
}cpp3. 模拟双端行为:回文构造、翻转调度#
// 按规则交替从两端取数
deque<int> d(a.begin(), a.end());
bool left = true;
while (!d.empty()) {
if (left) { use(d.front()); d.pop_front(); }
else { use(d.back()); d.pop_back(); }
left = !left;
}cpp4. 作为 queue / stack 的底层容器#
queue<int> q; // 默认底层就是 deque
stack<int> st; // 默认底层也是 deque
queue<int, deque<int>> q2; // 显式指定cpp七、容器选型#
| 需求 | 选择 |
|---|---|
| 只在尾部操作 | vector(缓存友好,最快) |
| 头尾都要操作 + 下标访问 | deque |
| 头尾操作 + 中间频繁插入删除 | list(链表,但无随机访问) |
| 只要 FIFO | queue(接口更干净) |
| 只要 LIFO | stack 或 vector |
| 滑动窗口最值、0-1 BFS | deque(直接操作) |
竞赛经验:
deque的下标访问比vector慢,纯尾部场景仍用vector;- 单调队列几乎总是用
deque<int>存下标实现; - 头删频繁的队列模拟,
deque优于queue(可以d[i]看任意位置)。
八、高频错误清单#
- 空容器调用
front/back/pop_front/pop_back→ 未定义行为,先empty()判断。 - 以为
pop_front返回元素 → 和queue::pop一样不返回,先读再删。 - 把
&d[0]当连续数组传给 C API → deque 内存分段,错误;用vector。 - 以为存在
reserve→ deque 没有这个接口。 - 中间插入删除当
O(1)用 → 是O(n),循环中反复中间操作会退化到O(n²)。 - 插入后继续用旧迭代器 → push_front/push_back 会使迭代器失效。
size()返回无符号类型,d.size() - 1下溢 → 与 vector 相同的坑,强转int或判空。- 单调队列里存值不存下标 → 无法判断元素是否滑出窗口。
九、一页速记#
deque<int> d;
// 双端增删:O(1)
d.push_front(x); d.push_back(x);
d.pop_front(); d.pop_back(); // 不返回值,先判空
d.front(); d.back();
// 随机访问:O(1),常数比 vector 大
d[i]; d.at(i);
// 中间操作:O(n),慎用
d.insert(d.begin() + k, x);
d.erase(d.begin() + k);
// 单调队列(滑动窗口最值)
deque<int> dq; // 存下标
while (!dq.empty() && dq.front() <= i - k) dq.pop_front(); // 出窗口
while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back(); // 维护单调
dq.push_back(i);
// 答案 = a[dq.front()]cpp五句口诀:
deque= 双端O(1)+ 下标访问,是”双端版 vector”。- 分段存储,头尾扩展不搬移元素,但不能用
&d[0]当数组。 - 中间插入删除是
O(n),别在循环里用。 - 单调队列存下标,每个元素进出各一次,总
O(n)。 - 纯尾部操作用
vector,头尾都要才用deque。