麦地

Back

一、核心特性与底层模型#

特性 说明
双端操作 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();   // 9
cpp

注意: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;
cpp

3. 中间操作(存在但慎用)#

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) 完成。

要点:

  • 队列里存下标而不是值,方便判断是否滑出窗口;
  • 队首始终是当前窗口最大值的下标;
  • 每个下标最多入队、出队一次,总复杂度 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);
        }
    }
}
cpp

3. 模拟双端行为:回文构造、翻转调度#

// 按规则交替从两端取数
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;
}
cpp

4. 作为 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] 看任意位置)。

八、高频错误清单#

  1. 空容器调用 front/back/pop_front/pop_back → 未定义行为,先 empty() 判断。
  2. 以为 pop_front 返回元素 → 和 queue::pop 一样不返回,先读再删。
  3. 把 &d[0] 当连续数组传给 C API → deque 内存分段,错误;用 vector。
  4. 以为存在 reserve → deque 没有这个接口。
  5. 中间插入删除当 O(1) 用 → 是 O(n),循环中反复中间操作会退化到 O(n²)。
  6. 插入后继续用旧迭代器 → push_front/push_back 会使迭代器失效。
  7. size() 返回无符号类型,d.size() - 1 下溢 → 与 vector 相同的坑,强转 int 或判空。
  8. 单调队列里存值不存下标 → 无法判断元素是否滑出窗口。

九、一页速记#

五句口诀:

  1. deque = 双端 O(1) + 下标访问,是”双端版 vector”。
  2. 分段存储,头尾扩展不搬移元素,但不能用 &d[0] 当数组。
  3. 中间插入删除是 O(n),别在循环里用。
  4. 单调队列存下标,每个元素进出各一次,总 O(n)。
  5. 纯尾部操作用 vector,头尾都要才用 deque。
Comment seems to stuck. Try to refresh?✨