104 std::deque（双端队列）
作者Lou Xiao, deepseek创建时间2025-04-02 17:27:28更新时间2025-04-02 17:27:28
1. 基本概念
1.1 定义
std::deque（双端队列，double-ended queue）是C++标准模板库(STL)中的一个容器适配器，它允许在两端高效地插入和删除元素。
1.2 特点
- 动态数组实现，但不像
vector那样所有元素存储在连续内存中 - 支持随机访问（通过下标）
- 在头部和尾部插入/删除操作都是O(1)时间复杂度
- 在中间插入/删除操作是O(n)时间复杂度
- 比
vector占用更多内存，因为需要维护内部结构
2. 底层实现原理
2.1 数据结构
- 通常实现为多个固定大小的数组块（称为"块"或"页"）
- 这些块通过某种索引结构（如指针数组）连接
- 维护指向第一个和最后一个元素的指针
2.2 内存分配
- 非连续内存存储
- 按需分配新块，不需要像
vector那样重新分配和复制所有元素 - 每个新块独立分配，可以分散在内存的不同位置
3. 基本操作
3.1 创建和初始化
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <deque>
2
3
// 空deque
4
std::deque<int> dq1;
5
6
// 带初始大小的deque
7
std::deque<int> dq2(10); // 10个元素，默认初始化为0
8
9
// 带初始值和大小的deque
10
std::deque<int> dq3(5, 100); // 5个元素，每个初始化为100
11
12
// 通过迭代器初始化
13
std::vector<int> vec = {1,2,3,4,5};
14
std::deque<int> dq4(vec.begin(), vec.end());
15
16
// 列表初始化(C++11)
17
std::deque<int> dq5 = {1,2,3,4,5};
3.2 元素访问
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
std::deque<int> dq = {1,2,3,4,5};
2
3
// 使用下标
4
int a = dq[2]; // 无边界检查
5
int b = dq.at(2); // 有边界检查，越界抛出std::out_of_range异常
6
7
// 访问首尾元素
8
int front = dq.front();
9
int back = dq.back();
3.3 修改操作
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
std::deque<int> dq;
2
3
// 在尾部添加元素
4
dq.push_back(10);
5
dq.emplace_back(20); // C++11, 避免临时对象构造
6
7
// 在头部添加元素
8
dq.push_front(5);
9
dq.emplace_front(0); // C++11
10
11
// 删除尾部元素
12
dq.pop_back();
13
14
// 删除头部元素
15
dq.pop_front();
16
17
// 插入元素
18
auto it = dq.begin() + 2;
19
dq.insert(it, 15); // 在第三个位置插入15
20
21
// 删除元素
22
it = dq.begin() + 1;
23
dq.erase(it); // 删除第二个元素
24
25
// 清空deque
26
dq.clear();
4. 容量操作
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
std::deque<int> dq = {1,2,3};
2
3
// 获取元素数量
4
size_t size = dq.size();
5
6
// 检查是否为空
7
bool empty = dq.empty();
8
9
// 改变大小
10
dq.resize(5); // 扩展到5个元素，新增元素默认初始化为0
11
dq.resize(8, 100); // 扩展到8个元素，新增元素初始化为100
12
dq.resize(2); // 缩小到2个元素
5. 迭代器
5.1 基本迭代器
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
std::deque<int> dq = {1,2,3,4,5};
2
3
// 正向迭代
4
for(auto it = dq.begin(); it != dq.end(); ++it) {
5
std::cout << *it << " ";
6
}
7
8
// 反向迭代
9
for(auto rit = dq.rbegin(); rit != dq.rend(); ++rit) {
10
std::cout << *rit << " ";
11
}
12
13
// C++11范围for循环
14
for(int num : dq) {
15
std::cout << num << " ";
16
}
5.2 迭代器失效
- 在头部或尾部插入元素：所有迭代器失效，但指针/引用仍有效
- 在中间插入/删除元素：所有迭代器、指针和引用都失效
- 删除元素：被删除元素的迭代器、指针和引用失效
6. 性能分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| push_back | O(1) | 在尾部插入 |
| push_front | O(1) | 在头部插入 |
| pop_back | O(1) | 删除尾部元素 |
| pop_front | O(1) | 删除头部元素 |
| insert/erase | O(n) | 在中间位置插入/删除 |
| operator[] | O(1) | 随机访问 |
| at() | O(1) | 带边界检查的随机访问 |
| front()/back() | O(1) | 访问首尾元素 |
| size() | O(1) | 获取元素数量 |
7. 与其它容器的比较
7.1 deque vs vector
vector在尾部操作高效，但头部操作低效deque在头部和尾部操作都高效vector内存连续，deque内存不连续vector随机访问稍快（缓存友好）vector更适合需要频繁随机访问的场景deque更适合需要频繁在两端操作的场景
7.2 deque vs list
list在任何位置插入/删除都是O(1)，但需要遍历才能访问元素deque支持随机访问，list不支持list每个元素需要额外存储前后指针，内存开销更大deque更适合需要随机访问和两端操作的场景list更适合需要频繁在中间位置插入/删除的场景
8. 使用场景
- 实现队列和双端队列：
deque是标准库中std::queue和std::stack的默认底层容器 - 滑动窗口算法：需要频繁在两端操作数据
- 撤销操作：维护操作历史，支持从两端添加/移除
- 数据流处理：需要同时从头部消费数据，从尾部添加新数据
9. 高级用法
9.1 与算法结合
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <algorithm>
2
3
std::deque<int> dq = {5,3,1,4,2};
4
5
// 排序
6
std::sort(dq.begin(), dq.end());
7
8
// 查找
9
auto it = std::find(dq.begin(), dq.end(), 3);
10
11
// 反转
12
std::reverse(dq.begin(), dq.end());
9.2 自定义分配器
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <memory>
2
3
// 使用自定义分配器
4
std::deque<int, std::allocator<int>> dq;
9.3 交换操作
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
std::deque<int> dq1 = {1,2,3};
2
std::deque<int> dq2 = {4,5,6};
3
4
dq1.swap(dq2); // 高效交换内容
10. 注意事项
- 内存使用：
deque通常比vector占用更多内存 - 迭代器失效：注意操作导致的迭代器失效问题
- 中间操作：避免频繁在中间位置插入/删除，性能较差
- 缓存不友好：随机访问性能可能不如
vector，因为内存不连续
11. 示例代码
11.1 基本使用示例
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <iostream>
2
#include <deque>
3
4
int main() {
5
std::deque<int> dq;
6
7
// 添加元素
8
dq.push_back(10);
9
dq.push_front(5);
10
dq.push_back(20);
11
dq.push_front(1);
12
13
// 遍历
14
std::cout << "Deque elements: ";
15
for(int num : dq) {
16
std::cout << num << " ";
17
}
18
std::cout << std::endl;
19
20
// 删除元素
21
dq.pop_front();
22
dq.pop_back();
23
24
// 插入元素
25
auto it = dq.begin() + 1;
26
dq.insert(it, 15);
27
28
// 输出修改后的deque
29
std::cout << "Modified deque: ";
30
for(int num : dq) {
31
std::cout << num << " ";
32
}
33
34
return 0;
35
}
11.2 性能测试示例
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <iostream>
2
#include <deque>
3
#include <vector>
4
#include <chrono>
5
6
void testDequePerformance() {
7
std::deque<int> dq;
8
std::vector<int> vec;
9
10
const int N = 100000;
11
12
// 测试头部插入
13
auto start = std::chrono::high_resolution_clock::now();
14
for(int i = 0; i < N; ++i) {
15
dq.push_front(i);
16
}
17
auto end = std::chrono::high_resolution_clock::now();
18
std::cout << "Deque push_front: "
19
<< std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
20
<< " ms" << std::endl;
21
22
start = std::chrono::high_resolution_clock::now();
23
for(int i = 0; i < N; ++i) {
24
vec.insert(vec.begin(), i);
25
}
26
end = std::chrono::high_resolution_clock::now();
27
std::cout << "Vector insert at begin: "
28
<< std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
29
<< " ms" << std::endl;
30
}
31
32
int main() {
33
testDequePerformance();
34
return 0;
35
}
12. 总结
std::deque是一个功能强大的容器，特别适合需要在两端高效操作的场景。虽然它在随机访问性能上略逊于vector，但在头部操作上远优于vector。选择使用deque还是其他容器应根据具体的使用场景和性能需求来决定。
std::deque 常用 API 的整理表格
| 名称 | 用途 | 原型 | 代码示例 | 注释 |
|---|---|---|---|---|
push_back | 在尾部插入元素 | void push_back(const T& value); | deque<int> d; d.push_back(10); | 时间复杂度为 O(1)，可能触发内存重新分配。 |
push_front | 在头部插入元素 | void push_front(const T& value); | deque<int> d; d.push_front(5); | 时间复杂度为 O(1)，与 push_back 类似。 |
pop_back | 删除尾部元素 | void pop_back(); | deque<int> d{1, 2}; d.pop_back(); | 容器必须非空，否则行为未定义。 |
pop_front | 删除头部元素 | void pop_front(); | deque<int> d{1, 2}; d.pop_front(); | 同 pop_back，但操作头部。 |
emplace_back | 在尾部就地构造元素 | template<class... Args> void emplace_back(Args&&... args); | deque<std::string> d; d.emplace_back("hello"); | 避免临时对象拷贝，C++11 引入。 |
emplace_front | 在头部就地构造元素 | template<class... Args> void emplace_front(Args&&... args); | deque<std::string> d; d.emplace_front("world"); | 同 emplace_back，操作头部。 |
size | 返回元素数量 | size_type size() const noexcept; | deque<int> d{1, 2}; cout << d.size(); // 输出 2 | 时间复杂度为 O(1)。 |
empty | 检查容器是否为空 | bool empty() const noexcept; | if (d.empty()) { /* ... */ } | 等价于 size() == 0。 |
operator[] | 通过下标访问元素（无边界检查） | reference operator[](size_type pos); | deque<int> d{10, 20}; cout << d[1]; // 输出 20 | 快速访问，但需确保索引有效。 |
at | 通过下标访问元素（有边界检查） | reference at(size_type pos); | try { cout << d.at(2); } catch(...) { /* 处理越界 */ } | 越界时抛出 std::out_of_range 异常。 |
front | 访问首元素 | reference front(); | deque<int> d{1, 2}; cout << d.front(); // 输出 1 | 容器必须非空，否则行为未定义。 |
back | 访问尾元素 | reference back(); | deque<int> d{1, 2}; cout << d.back(); // 输出 2 | 同 front，但操作尾部。 |
clear | 清空所有元素 | void clear() noexcept; | d.clear(); | 保留容器的内存（可能不释放）。 |
insert | 在指定位置插入元素 | iterator insert(iterator pos, const T& value); | d.insert(d.begin() + 1, 99); | 返回指向插入元素的迭代器，可能使其他迭代器失效。 |
erase | 删除指定位置的元素 | iterator erase(iterator pos); | d.erase(d.begin()); | 返回指向被删除元素之后的迭代器。 |
resize | 调整容器大小 | void resize(size_type count, const T& value = T()); | d.resize(5, 0); // 扩容至5，新增元素初始化为0 | 若缩小容器，多余元素被销毁。 |
关键特性总结：
- 双端操作：支持 O(1) 复杂度的头部和尾部插入/删除。
- 随机访问：支持通过
operator[]或at访问元素（类似std::vector）。 - 迭代器失效：插入/删除操作可能导致迭代器失效（除首尾操作外）。
- 内存管理：数据分块存储，扩容时无需移动全部元素。
文章目录