第3章 deque容器

课程目录第3章 deque容器

deque容器：双端队列的全面解析

deque，全称 double-ended queue，中文叫双端队列。说实话，我第一次看到这个名字时，以为它就是个能在两头操作的 vector。后来在项目中真正用起来才发现——这玩意儿的设计哲学，跟 vector 完全不是一回事。

我个人习惯把 deque 理解为「分段连续」的容器。它不像 vector 那样要求一整块连续内存，而是由多个固定大小的缓冲区拼接而成。这种结构带来了一个巨大的好处：在头部和尾部插入元素都非常快，不像 vector 只能在尾部高效操作。

核心要点：deque 是 STL 中唯一一个支持双端高效插入/删除的序列容器。它结合了 vector 的随机访问能力和 list 的部分两端操作优势。

deque 的底层原理

deque 的内部结构，说白了就是「中控器 + 缓冲区」的组合。中控器是一个指针数组，每个指针指向一块固定大小的内存块（通常是 512 字节）。

我画了一张图，帮你理解这个结构：

你看，中控器里的每个指针都指向一个独立的缓冲区。当你在头部插入元素时，deque 会检查头部缓冲区是否还有空间。如果有，直接插入；如果没有，就新分配一个缓冲区，然后更新中控器。整个过程不需要像 vector 那样搬动已有元素。

我的经验：deque 的随机访问虽然也是 O(1)，但比 vector 稍慢一点。因为需要先通过中控器找到对应的缓冲区，再在缓冲区内定位。不过这个差异通常可以忽略不计。

deque 构造函数

deque 的构造函数跟 vector 几乎一模一样。常用的有这么几种：

#include <deque>

std::deque<int> d1;                    // 空deque
std::deque<int> d2(5);                 // 5个元素，默认初始化为0
std::deque<int> d3(5, 10);             // 5个元素，每个都是10
std::deque<int> d4(d3.begin(), d3.end()); // 用迭代器范围构造
std::deque<int> d5(d4);                // 拷贝构造
std::deque<int> d6 = {1, 2, 3, 4, 5};  // 初始化列表（C++11起）

嗯，这里要注意一点：std::deque<int> d2(5) 这种写法，对于内置类型会进行值初始化，int 就是 0。但对于自定义类型，会调用默认构造函数。我曾经在项目里看到有人用这个方式初始化了一个 deque 存对象，结果对象的构造函数里有个文件打开操作——5 个对象就开了 5 个文件句柄，差点把系统资源耗光。

deque 赋值操作

赋值这块，deque 提供了几种方式：

std::deque<int> d1 = {1, 2, 3};
std::deque<int> d2;

d2 = d1;                    // operator= 赋值
d2.assign(5, 100);          // 赋5个100
d2.assign(d1.begin(), d1.end()); // 用迭代器范围赋值
d2.assign({10, 20, 30});    // 用初始化列表赋值（C++11起）

我个人建议尽量用 assign 而不是先 clear 再 push_back。因为 assign 内部做了优化，可能会复用已有的缓冲区，减少内存分配次数。

deque 大小操作

大小相关的成员函数，跟 vector 基本一致：

函数	说明	示例
`size()`	返回元素个数	`d.size()`
`empty()`	判断是否为空	`d.empty()`
`resize(n)`	调整大小为 n	`d.resize(10)`
`resize(n, val)`	调整大小为 n，新元素用 val 填充	`d.resize(10, 5)`
`shrink_to_fit()`	释放未使用的内存（C++11起）	`d.shrink_to_fit()`

注意：deque 没有 capacity() 和 reserve() 函数。因为 deque 的内存是分段管理的，不存在「总容量」这个概念。你想想看，每个缓冲区独立管理，怎么算总容量？

deque 插入与删除

这才是 deque 的重头戏。两端操作是它的强项：

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

d.push_front(1);   // 头部插入：{1, 2, 3, 4}
d.push_back(5);    // 尾部插入：{1, 2, 3, 4, 5}
d.pop_front();     // 删除头部：{2, 3, 4, 5}
d.pop_back();      // 删除尾部：{2, 3, 4}

// 中间插入（效率较低）
auto it = d.begin() + 1;
d.insert(it, 99);  // {2, 99, 3, 4}

// 删除
it = d.begin() + 2;
d.erase(it);       // {2, 99, 4}
d.clear();         // 清空所有元素

我曾经在做一个消息队列时，用了 deque 来存储待处理的消息。新消息从尾部加入，优先级高的消息从头部插入。这种场景下 deque 简直是完美选择——两端操作都是 O(1)，而且还能随机访问中间的消息做批量处理。

但要注意，中间插入和删除是 O(n) 的。因为 deque 需要移动元素来保持连续性。如果你需要在中间频繁操作，建议改用 list。

deque 数据存取

deque 支持随机访问，用法跟 vector 一样：

std::deque<int> d = {10, 20, 30, 40, 50};

// 使用下标操作符
int val1 = d[2];      // 30，不进行边界检查
int val2 = d.at(2);   // 30，进行边界检查，越界抛异常

// 获取首尾元素
int front = d.front(); // 10
int back = d.back();   // 50

这里我建议：如果你确定下标不会越界，用 operator[] 效率更高。如果代码要处理用户输入或不可控的数据，用 at() 更安全。我自己写工具类时习惯用 at()，写性能敏感的模块时用 operator[]。

deque 排序

deque 没有自己的排序算法，但我们可以用 STL 的 std::sort：

#include <algorithm>

std::deque<int> d = {5, 2, 8, 1, 9, 3};

// 升序排序
std::sort(d.begin(), d.end());

// 降序排序
std::sort(d.begin(), d.end(), std::greater<int>());

// 自定义排序规则
std::sort(d.begin(), d.end(), [](int a, int b) {
    return a % 10 < b % 10;  // 按个位数排序
});

为什么 deque 可以用 std::sort？因为 std::sort 要求随机访问迭代器，而 deque 正好提供了这个。list 就不行，它只能用 list::sort。

性能提示：对 deque 排序时，如果元素数量很大（比如超过 10 万），可以考虑先把数据拷贝到 vector 里排序，再拷回来。因为 vector 的内存连续性更好，CPU 缓存命中率更高。我在处理日志数据时做过测试，这种方式能快 20%-30%。

实战建议

说了这么多，到底什么时候用 deque？我总结了几条：

需要双端操作：比如任务队列、消息缓冲，用 deque 准没错
需要随机访问：但两端操作也频繁，vector 不适合，deque 是唯一选择
数据量不确定：deque 的分段内存管理比 vector 的连续内存更灵活，不容易出现大块内存分配失败
避免使用场景：中间插入/删除频繁，或者对内存占用极度敏感（deque 的缓冲区可能有少量浪费）

最后说一句，deque 在 STL 里其实是个被低估的容器。很多人一上来就用 vector，遇到头部插入就改用 list，却忘了中间还有个 deque。你想想看，如果你的需求是「两端操作 + 随机访问」，deque 就是那个最合适的工具。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录

deque容器：双端队列的全面解析

deque 的底层原理

deque 构造函数

deque 赋值操作

deque 大小操作

deque 插入与删除

deque 数据存取

deque 排序

实战建议