【信奥业余科普】C++ 的奇妙之旅 | 24：拆解 deque——分段连续的双端队列

上一篇文章介绍了 stack 和 queue，它们本质上是容器适配器，底层默认使用的容器就是 deque。我们提到 deque 能同时做到头尾操作 $O(1)$ 和下标随机访问 $O(1)$，比 vector 灵活得多。

这篇文章就来拆解 deque 的内部结构，看看它是怎么做到这些的。

往期回顾：

• 第一部分【计算机历史】系列文章合集（共8篇）
• 第二部分【C++的奇妙之旅】前23篇合集

---

一、 为什么需要 deque？

先回顾 vector 的两个限制：

1. 头部插入删除效率低。vector 的底层是一段连续内存，在头部插入一个元素，后面的所有元素都要往后挪一位，时间复杂度 $O(n)$。
2. 扩容需要整体搬迁。当容量不够时，vector 要申请一块更大的新内存，把所有数据拷贝过去，再释放旧内存。数据量大时，这次搬迁的开销不可忽视。

deque（全称 double-ended queue，双端队列）正是为解决这两个问题而设计的。它可以在头部和尾部都进行 $O(1)$ 的插入和删除，扩容时也不需要搬迁已有数据。

---

二、 底层结构：分段连续存储

deque 没有像 vector 那样把所有元素放在一整块连续内存中，而是采用了分段连续的设计：将数据分散存储在多个固定大小的小数组中（称为缓冲区或块），再用一个中央的 指针数组（map） 来管理这些块。

2.1 三层结构

deque 的内部可以拆分为三层：

1. 缓冲区（buffer）：每个缓冲区是一个固定大小的小数组，存放实际的元素。大小由实现决定，例如一个缓冲区可以存放 8 个 int。
2. 中控数组（map）：一个指针数组，每个元素是一个指针，指向一个缓冲区。通过这个数组可以找到任意一个缓冲区的位置。
3. 迭代器：deque 维护两个特殊的迭代器——start 和 finish，分别指向第一个元素和最后一个元素的下一个位置。每个迭代器内部记录了四个信息：
   • cur：指向当前元素在缓冲区内的位置。
   • first：当前缓冲区的起始地址。
   • last：当前缓冲区的末尾地址（即 first + 缓冲区大小）。
   • node：指向中控数组中对应的指针，通过它可以跳转到相邻的缓冲区。

用一个示意图来理解：

中控数组 (map)
┌──────┐
│  *───┼──→ [缓冲区0: _, _, 1, 2]   ← start.cur 指向元素1
│  *───┼──→ [缓冲区1: 3, 4, 5, 6]
│  *───┼──→ [缓冲区2: 7, 8, _, _]   ← finish.cur 指向元素8之后
│  *   │    (预留空位)
└──────┘

每个缓冲区内部是连续的，但不同缓冲区之间在物理内存中可以不相邻。中控数组把它们逻辑上串联在一起，对外表现得像一个连续的大数组。

2.2 头尾操作为什么是 $O(1)$

尾部追加（push_back）： finish 迭代器记录了当前尾部的位置。如果当前缓冲区还有空位，直接写入即可。如果当前缓冲区满了，就新分配一个缓冲区，在中控数组中添加一个指针指向它，然后把新元素写入新缓冲区的第一个位置。

头部插入（push_front）： 与尾部类似。start 迭代器记录了头部位置。如果当前缓冲区前面还有空位，直接往前写入。如果已经到了缓冲区的起始位置，就新分配一个缓冲区，放在中控数组的前面，然后把新元素写入新缓冲区的最后一个位置。

无论哪种情况，都不需要移动已有元素，所以是 $O(1)$。

2.3 随机访问为什么是 $O(1)$

访问 d[i] 时，deque 不需要遍历，而是通过计算直接定位：

1. 先算出第一个缓冲区中还剩多少元素（因为第一个缓冲区可能只用了后半部分）。
2. 减去这部分后，用除法确定目标元素在第几个缓冲区：缓冲区编号 = 偏移量 / 缓冲区大小。
3. 用取余确定它在缓冲区内的位置：缓冲区内偏移 = 偏移量 % 缓冲区大小。

整个过程只涉及加减乘除，不涉及循环或遍历，所以是 $O(1)$。

但需要注意：虽然理论复杂度与 vector 相同，但 deque 的每次下标访问多了一次间接寻址（先查中控数组，再跳到缓冲区），常数因子比 vector 大。

2.4 扩容不搬迁

vector 扩容时，必须申请一块更大的连续内存，把所有元素拷贝过去。而 deque 扩容时只需要新分配一个缓冲区，在中控数组中记录它的地址即可。已有缓冲区中的数据一个都不用动。

如果中控数组本身也满了怎么办？此时只需要重新分配中控数组（一个指针数组），拷贝的只是若干个指针（每个 8 字节），而不是实际数据。代价远小于 vector 的整体搬迁。

---

三、 基本操作

使用 deque 需要引入头文件 <deque>。它的大部分接口与 vector 相同，额外多了头部操作。

3.1 创建与初始化

#include <deque>

std::deque<int> d1;              // 空
std::deque<int> d2(5, 0);        // 5 个 0
std::deque<int> d3 = {1, 2, 3};  // 初始化列表

3.2 头尾操作

std::deque<int> d = {2, 3, 4};

d.push_back(5);     // 尾部追加  → {2, 3, 4, 5}
d.push_front(1);    // 头部插入  → {1, 2, 3, 4, 5}

d.pop_back();       // 删除尾部  → {1, 2, 3, 4}
d.pop_front();      // 删除头部  → {2, 3, 4}

这是 deque 相比 vector 最大的优势：push_front 和 pop_front 都是 $O(1)$，而 vector 做这些操作是 $O(n)$。

3.3 随机访问

d[0];       // 下标访问
d.at(1);    // 带越界检查的访问
d.front();  // 第一个元素
d.back();   // 最后一个元素

用法与 vector 完全一致。

3.4 大小相关

d.size();    // 元素个数
d.empty();   // 是否为空
d.clear();   // 清空

注意：deque 没有 capacity() 和 reserve()。因为它不需要像 vector 那样预分配一整块连续空间，所以”容量”这个概念对 deque 没有实际意义。

---

四、 deque vs vector：如何选择？

对比维度	vector	deque
底层结构	一整块连续内存	多个固定大小的缓冲区 + 中控数组
尾部插入/删除	均摊 $O(1)$	$O(1)$
头部插入/删除	$O(n)$（需要移动所有元素）	$O(1)$
下标访问	$O(1)$，直接定位	$O(1)$，需要一次间接寻址
扩容	整体搬迁，拷贝所有元素	新增一个缓冲区，已有数据不动
内存连续性	完全连续	段内连续，段间不保证
capacity/reserve	支持	不支持

选择建议：

• 默认用 vector。大多数场景下，vector 的连续内存对 CPU 缓存更友好，实际运行速度更快。
• 需要频繁头部操作时用 deque。如果你的场景需要在队列两端都做插入删除，deque 是更好的选择。
• stack 和 queue 默认底层就是 deque，在使用它们时，你已经间接在使用 deque 了。

---

五、 deque 在竞赛中的使用场景

在信奥竞赛中，deque 最常见的用途是作为 stack 和 queue 的底层容器（由适配器自动完成，不需要手动操作）。直接使用 deque 的场景相对较少，但以下情况会用到：

• 滑动窗口最值问题：用 deque 实现单调队列，从头部弹出过期元素，从尾部维护单调性。这类题目中需要同时操作两端，deque 是最直接的选择。
• 需要双端操作的模拟题：例如模拟排队、洗牌等，需要在两端插入或删除。

// 单调队列示例：维护一个从头到尾递减的队列
#include <deque>

std::deque<int> dq;

// 插入新元素时，从尾部弹出所有比它小的元素
void insert(int val) {
    while (!dq.empty() && dq.back() < val) {
        dq.pop_back();
    }
    dq.push_back(val);
}

// 队头始终是当前窗口的最大值
int getMax() {
    return dq.front();
}

---

结语与下期预告

deque 通过”分段连续存储 + 中控数组”的设计，在不牺牲随机访问能力的前提下，实现了头尾两端的 $O(1)$ 操作。这也解释了为什么 STL 选择它作为 stack 和 queue 的默认底层容器——它同时满足了两者的需求。

不过在实际竞赛中，deque 更多是在幕后工作。日常做题时，vector 仍然是最常用的容器。

到目前为止，我们介绍的容器（vector、stack、queue、deque）都属于序列容器——元素按照插入的顺序排列。下一篇文章，我们将进入关联容器的世界，介绍 set 和 map。它们的特点是：元素不再按插入顺序存储，而是按照值自动排序，查找效率可以达到 $O(\log n)$。

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

"luogu-"系列题目可在洛谷题库进行在线评测。

"bcqm-"系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号