一、std::deque
（1）deque与其适用场景
std::deque（双端队列，double-ended queue）是 C++ STL（标准模板库）中的序列容器，类似于 std::vector，但支持在两端高效地插入和删除元素。
适用场景：
- 需要高效的头部和尾部插入/删除（比
vector头部插入快）。 - 仍然需要 O(1) 随机访问（比
list访问速度快）。 - 适用于队列和缓存管理（如
std::queue底层实现）。
包含头文件
#include <deque>
（2）std::deque vs std::vector
| 特性 | std::deque | std::vector |
|---|---|---|
| 随机访问 | O(1) | O(1) |
| 动态扩展 | 前后两端扩展 | 只能尾部扩展 |
| 插入/删除 | 两端插入/删除 O(1) | 头部/中间插入 O(n) |
| 内存管理 | 多块内存块 | 连续内存 |
std::deque 适用于：
- 频繁在头部和尾部插入/删除元素
- 仍然需要支持随机访问
std::vector 适用于：
- 只在尾部插入/删除
- 需要连续存储，提高访问性能
二、std::deque 的创建
| 函数 | 作用 |
|---|---|
deque<T> dq; | 默认构造一个空deque |
deque<T> dq(n, val); | 创建一个大小为n，值为val的deque |
deque<T> dq = {val1, val2, ...}; | 使用列表初始化 |
deque<T> dq2(dq1); | 拷贝构造 |
deque<T> dq2(dq1.begin(), dq1.end()); | 迭代器范围构造 |
(1) 定义 deque
示例：
#include <iostream>
using namespace std;
#include <deque>void printDeque(deque<int> d)
{for (auto it = d.begin(); it != d.end(); ++it){cout << *it << " ";}cout << endl;
}int main() {deque<int> d1; // 空双端队列deque<int> d2(5, 100); // 5 个 100deque<int> d3 = {1, 2, 3}; // 直接初始化deque<int> d4(d3); // 复制 d3printDeque(d1);printDeque(d2);printDeque(d3);printDeque(d4);system("pause");return 0;
}
(2) 向 deque 添加元素
示例：
#include <iostream>
using namespace std;
#include <deque>void printDeque(deque<int> d)
{for (auto it = d.begin(); it != d.end(); ++it){cout << *it << " ";}cout << endl;
}int main() {deque<int> dq;dq.push_back(10); // 在尾部添加 10dq.push_back(20);dq.push_back(30);dq.push_front(40); // 在头部添加 40printDeque(dq);system("pause");return 0;
}
注意：
push_back：在容器尾部添加元素。push_front：在容器头部添加元素。
(3) 访问元素
| 函数 | 作用 |
|---|---|
operator[] | 随机访问（deque[i]） |
at(index) | 访问指定索引（带边界检查） |
front() | 返回首元素 |
back() | 返回尾元素 |
示例：
#include <iostream>
using namespace std;
#include <deque>int main() {deque<int> dq;dq.push_back(10); // 在尾部添加 10dq.push_back(20);dq.push_back(30);dq.push_back(40); cout << dq[0] << endl; // 直接访问（不安全）cout << dq.at(1) << endl; // 安全访问（越界会抛异常）cout << dq.front() << endl; // 获取第一个元素cout << dq.back() << endl; // 获取最后一个元素system("pause");return 0;
}
三、遍历 deque
(1) 使用 for 循环
示例：
#include <iostream>
using namespace std;
#include <deque>int main() {deque<int> dq = {10, 20, 30, 40};for (int i = 0; i < dq.size(); i++){cout << dq[i] << " ";}cout << endl;system("pause");return 0;
}
(2) 使用范围 for
示例：
#include <iostream>
using namespace std;
#include <deque>int main() {deque<int> dq = {10, 20, 30, 40};for (int x : dq){cout << x << " ";}cout << endl;system("pause");return 0;
}
注意：
- 使用范围基 for 循环（range-based for loop），可以简洁、直观地遍历deque容器。
(3) 使用迭代器
| 函数 | 返回类型 | 作用 |
|---|---|---|
begin() | iterator / const_iterator | 指向首元素 |
end() | iterator / const_iterator | 指向尾后位置 |
rbegin() | reverse_iterator / const_reverse_iterator | 指向末元素（反向遍历） |
rend() | reverse_iterator / const_reverse_iterator | 指向首元素前的位置（反向遍历） |
cbegin() | const_iterator | 返回只读迭代器，指向首元素 |
cend() | const_iterator | 返回只读迭代器，指向尾后 |
crbegin() | const_reverse_iterator | 返回只读反向迭代器，指向末元素 |
crend() | const_reverse_iterator | 返回只读反向迭代器，指向首元素前 |
示例：
#include <iostream>
using namespace std;
#include <deque>int main() {deque<int> dq = {10, 20, 30, 40};for (auto it = dq.begin(); it != dq.end(); ++it){cout << *it << " ";}cout << endl;system("pause");return 0;
}
四、std::deque 的常用操作
(1) 插入和删除
| 函数 | 作用 |
|---|---|
push_back(value) | 在尾部插入元素 |
push_front(value) | 在头部插入元素 |
pop_back() | 删除尾部元素 |
pop_front() | 删除头部元素 |
insert(pos, value) | 在指定位置插入 |
erase(pos) | 删除指定位置的元素 |
示例：
#include <iostream>
using namespace std;
#include <deque>void printDeque(deque<int> d)
{for (auto it = d.begin(); it != d.end(); ++it){cout << *it << " ";}cout << endl;
}int main() {deque<int> dq = {1, 2, 3, 4};// 在指定位置插入dq.insert(dq.begin() + 2, 100); // 在索引 2 位置插入 100, {1,2,100,3,4}printDeque(dq);// 删除元素dq.erase(dq.begin()); // 删除第一个元素,{2,100,3,4}printDeque(dq);dq.erase(dq.begin() + 2); // 删除索引 2 处的元素,{2,100,4}printDeque(dq);// 清空 dequedq.clear();printDeque(dq);system("pause");return 0;
}
(2) deque 的大小
| 函数 | 作用 |
|---|---|
size() | 返回元素个数 |
empty() | 判断是否为空 |
resize(n, value) | 调整大小，超过填充value |
shrink_to_fit() | 减少内存占用 |
示例：
#include <iostream>
using namespace std;
#include <deque>void printDeque(deque<int> d)
{for (auto it = d.begin(); it != d.end(); ++it){cout << *it << " ";}cout << endl;
}int main() {deque<int> dq = {1, 2, 3, 4};cout << dq.size() << endl; // 获取元素个数cout << dq.empty() << endl; // 是否为空dq.resize(10);printDeque(dq);dq = {1, 2, 3, 4};dq.resize(10, 1000);printDeque(dq);system("pause");return 0;
}
(3) 交换 deque
示例：
#include <iostream>
using namespace std;
#include <deque>void printDeque(deque<int> d)
{for (auto it = d.begin(); it != d.end(); ++it){cout << *it << " ";}cout << endl;
}int main() {deque<int> a = {1, 2, 3};deque<int> b = {4, 5, 6};cout << "交换前：" << endl;printDeque(a);printDeque(b);a.swap(b); // 交换 a 和 b 的内容cout << "交换后：" << endl;printDeque(a);printDeque(b);system("pause");return 0;
}
注意：
a.swap(b); 交换 a 和 b 的所有元素，避免数据拷贝，提高性能。
(4) deque 排序
| 函数 | 作用 |
|---|---|
sort(dq.begin(), dq.end()) | 排序 |
reverse(dq.begin(), dq.end()) | 逆序 |
find(dq.begin(), dq.end(), val) | 查找元素 |
binary_search(dq.begin(), dq.end(), val) | 二分查找（需排序） |
示例：
#include <iostream>
using namespace std;
#include <deque>
#include <algorithm>void printDeque(deque<int> d)
{for (auto it = d.begin(); it != d.end(); ++it){cout << *it << " ";}cout << endl;
}int main() {deque<int> dq = {3, 1, 4, 5, 2};printDeque(dq);sort(dq.begin(), dq.end()); // 升序排序printDeque(dq);reverse(dq.begin(), dq.end()); // 逆序printDeque(dq);system("pause");return 0;
}
