一、deque容器的定义
1.什么是deque容器
deque容器时 是 “double-ended queue” 的缩写，翻译为“双端队列”。它是一种可以在容器头部和尾部快速进行插入和删除操作的顺序容器。
2.deque容器与vector容器的联系
deque容器和上一篇学习的vector容器有很多相似点，如：
- deque 容器也擅长在序列尾部添加或删除元素（时间复杂度为O(1)），而不擅长在序列中间添加或删除元素。
- deque 容器也可以根据需要修改自身的容量和大小。
当然，和 vector 不同的是，deque 还擅长在序列头部添加或删除元素，所耗费的时间复杂度也为常数阶O(1)。并且更重要的一点是，deque 容器中存储元素并不能保证所有元素都存储到连续的内存空间中。
给出deque容器和vector容器的对比表方便大家直白理解：
| 特性 | deque容器 | vector容器 |
|---|---|---|
| 内存结构 | 分段连续（块+映射表） | 完全连续 |
| 头部插入/删除 | O(1) | O(n)(需要移动所有元素) |
| 尾部插入/删除 | O(1) | O(1)(均摊) |
| 中间插入/删除 | O(n) | O(n) |
| 随机访问性能 | O(1)，（先找到块，再在块内偏移）稍慢于vector | O(1),最优 |
| 内存稳定性 | 高：元素地址稳定 | 低：扩容时所有元素都会移动地址 |
| 迭代器失效 | 头尾操作：通常不失效 中间操作：局部失效 控制块重分配：全部失效 | 扩容时：全部失效 尾部操作：end()失效 中间操作：之后的所有失效 |
因此，
- deque容器适合高频头尾操作（如任务队列、滑动窗口）。
- vector容器适合尾部操作+随机访问（如动态数组、数据缓存）。
二、deque容器的使用
1.deque容器的创建
- 创建一个没有任何元素的空 deque 容器：
deque<int> d; //最常见的构造，空的 deque 容器在创建之后可以做添加或删除元素的操作- 创建一个具有 n 个元素的 deque 容器，其中每个元素都采用对应类型的默认值：
deque<int> d(10); //此行代码创建一个具有 10 个元素（默认都为 0）的 deque 容器。- 创建一个具有 n 个元素的 deque 容器，并为每个元素都指定初始值，例如：
deque<int> d(10, 5); //如此就创建了一个包含 10 个元素（值都为 5）的 deque 容器。- 在已有 deque 容器的情况下，可以通过拷贝该容器创建一个新的 deque 容器，例如：
deque<int> d1(5);
deque<int> d2(d1); //采用此方式，必须保证新旧容器存储的元素类型一致。- 通过拷贝其他类型容器中指定区域内的元素（也可以是普通数组），可以创建一个新容器，例如：
//拷贝普通数组，创建deque容器
int a[] = { 1,2,3,4,5 };
std::deque<int>d(begin(a), end(a));
//适用于所有类型的容器
vector<int> v { 11,12,13,14,15 };
deque<int> d (v.begin()+2, v.end());//拷贝vector容器中的{13,14,15}2.deque容器内置函数方法
2.1 Iterators（迭代器）
| 函数名 | 描述 | 示例 |
|---|---|---|
| begin | 返回指向第一个元素的迭代器 | auto it = d.begin(); |
| end | 返回指向最后一个元素之后位置的迭代器 | auto end = d.end(); |
| cbegin | 返回指向第一个元素的const迭代器 | auto it = d.cbegin(); |
| cend | 返回指向末尾之后位置的const迭代器 | auto end = d.cend(); |
| rbegin | 返回指向最后一个元素的反向迭代器 | auto rit = d.rbegin(); |
| rend | 返回指向第一个元素之前位置的反向迭代器 | auto rend = d.rend(); |
| crbegin | 返回const反向迭代器 | auto rit = d.crbegin(); |
| crend | 返回const反向迭代器末尾 | auto crend = d.crend(); |
2.2 Capacity（容量）
| 函数名 | 描述 | 时间复杂度 | 示例 |
|---|---|---|---|
| empty | 检查容器是否为空 | O(1) | if(d.empty()) |
| size | 返回容器中元素的个数 | O(1) | int n = d.size(); |
| max_size | 返回容器可容纳的最大元素数 | O(1) | size_t max = d.max_size(); |
| resize | 调整容器大小 | O(N) | d.resize(10); |
| shrink_to_fit | 请求移除未使用的容量（非强制） | O(N) | d.shrink_to_fit(); |
2.3 Element access（元素访问）
| 函数名 | 描述 | 时间复杂度 | 示例 |
|---|---|---|---|
| operator[] | 下标访问（不检查边界） | O(1) | int val = d[2]; |
| at | 带边界检查的元素访问 | O(1) | int val = d.at(2); |
| front | 访问第一个元素 | O(1) | int first = d.front(); |
| back | 访问最后一个元素 | O(1) | int last = d.back(); |
2.4 Modifiers（修改器）
| 函数名 | 描述 | 时间复杂度 | 示例 |
|---|---|---|---|
| push_back | 尾部插入一个元素 | O(1) | d.push_back(10); |
| push_front | 头部插入一个元素 | O(1) | d.push_front(10); |
| pop_back | 删除尾部元素 | O(1) | d.pop_back(); |
| pop_front | 删除头部元素 | O(1) | d.pop_front(); |
| emplace_back | 尾部原位构造元素 | O(1) | d.emplace_back(10, 20); |
| emplace_front | 头部原位构造元素 | O(1) | d.emplace_front(10, 20); |
| insert | 在指定位置插入元素/范围 | O(N) | d.insert(it, 99); |
| emplace | 在指定位置原位构造 | O(N) | d.emplace(it, 99); |
| erase | 删除指定位置/范围的元素 | O(N) | d.erase(it); |
| clear | 清空所有元素 | O(N) | d.clear(); |
| assign | 替换容器内容 | O(N) | d.assign({1,2,3}); |
| swap | 交换两个容器的内容 | O(1) | d1.swap(d2); |
2.5 核心部分总结
必须掌握
| 函数 | 类别 | 说明 |
|---|---|---|
| push_back() | 修改器 | 尾部插入元素 |
| push_front() | 修改器 | 头部插入元素 |
| pop_back() | 修改器 | 尾部删除元素 |
| pop_front() | 修改器 | 头部删除元素 |
| operator[] | 元素访问 | 随机访问元素 |
| front() | 元素访问 | 获取第一个元素 |
| back() | 元素访问 | 获取最后一个元素 |
| empty() | 容量 | 判断是否为空 |
| size() | 容量 | 获取元素数量 |
| begin()/end() | 迭代器 | 遍历容器 |
建议掌握
| 函数 | 类别 | 说明 |
|---|---|---|
| insert() | 修改器 | 中间插入元素 |
| erase() | 修改器 | 删除元素 |
| clear() | 修改器 | 清空容器 |
| at() | 元素访问 | 带边界检查的访问 |
| resize() | 容量 | 调整大小 |
| assign() | 修改器 | 重新赋值 |
了解
| 函数 | 类别 | 说明 |
|---|---|---|
| emplace_back() | 修改器 | 原位构造（避免拷贝） |
| emplace_front() | 修改器 | 头部原位构造 |
| emplace() | 修改器 | 中间原位构造 |
| rbegin()/rend() | 迭代器 | 反向遍历 |
| shrink_to_fit() | 容量 | 请求压缩内存 |
| max_size() | 容量 | 最大可能大小 |
3. 样例代码及分析
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
int main() {
/******************** 1. 基本创建和初始化 ********************/
// 创建空deque
deque<int> d1;
// 创建并初始化
deque<int> d2 = {1, 2, 3, 4, 5};
// 创建指定大小
deque<int> d3(3); // 3个0
deque<int> d4(3, 100); // 3个100
/******************** 2. 两端操作（核心优势） ********************/
deque<int> d;
// 尾部插入
d.push_back(10); // [10]
d.push_back(20); // [10, 20]
d.push_back(30); // [10, 20, 30]
// 头部插入（vector做不到高效！）
d.push_front(0); // [0, 10, 20, 30]
d.push_front(-10); // [-10, 0, 10, 20, 30]
// 头部删除
d.pop_front(); // [0, 10, 20, 30]
// 尾部删除
d.pop_back(); // [0, 10, 20]
/******************** 3. 元素访问 ********************/
// 随机访问
cout << "第一个元素: " << d.front() << endl; // 0
cout << "最后一个元素: " << d.back() << endl; // 20
cout << "第二个元素: " << d[1] << endl; // 10
cout << "第二个元素(安全): " << d.at(1) << endl; // 10
/******************** 4. 容量查询 ********************/
cout << "大小: " << d.size() << endl; // 3
cout << "是否为空: " << (d.empty() ? "是" : "否") << endl; // 否
/******************** 5. 遍历方法 ********************/
cout << "遍历结果: ";
// 方法1：范围for循环（最常用）
for (int num : d) {
cout << num << " "; // 0 10 20
}
cout << endl;
// 方法2：使用迭代器
for (auto it = d.begin(); it != d.end(); ++it) {
cout << *it << " ";
}
cout << endl;
// 方法3：使用下标
for (int i = 0; i < d.size(); i++) {
cout << d[i] << " ";
}
cout << endl;
/******************** 6. 中间操作 ********************/
// 在指定位置插入
d.insert(d.begin() + 1, 99); // [0, 99, 10, 20]
// 删除指定位置
d.erase(d.begin() + 2); // [0, 99, 20]
/******************** 7. 清空容器 ********************/
d.clear();
cout << "清空后大小: " << d.size() << endl; // 0
/******************** 8. 实用场景示例 ********************/
// 场景1：deque作为队列（FIFO）
cout << "\n作为队列使用：" << endl;
deque<int> queue;
queue.push_back(1); // 入队
queue.push_back(2);
queue.push_back(3);
while (!queue.empty()) {
cout << queue.front() << " "; // 出队顺序：1 2 3
queue.pop_front();
}
cout << endl;
// 场景2：deque作为栈（LIFO）
cout << "\n作为栈使用：" << endl;
deque<int> stack;
stack.push_back(10); // 压栈
stack.push_back(20);
stack.push_back(30);
while (!stack.empty()) {
cout << stack.back() << " "; // 弹栈顺序：30 20 10
stack.pop_back();
}
cout << endl;
// 场景3：与算法结合
cout << "\n与算法结合：" << endl;
deque<int> nums = {5, 3, 8, 1, 9, 2};
// 排序
sort(nums.begin(), nums.end());
cout << "排序后: ";
for (int n : nums) cout << n << " ";
cout << endl;
// 查找
auto it = find(nums.begin(), nums.end(), 8);
if (it != nums.end()) {
cout << "找到8，位置索引: " << distance(nums.begin(), it) << endl;
}
return 0;
}下一篇我考虑给大家总结出竞赛中常用的一些stl算法函数，本篇还请大家一定要掌握，打好基础。
