导言
deque（双端队列）是另一种常用的序列容器，与 vector 相比，它在两端的插入删除操作上有独特优势。以下是 deque 高效操作的策略和特性：
一、deque 的特性与优势
deque 与 vector 的核心区别在于内存布局：
- deque 采用分段连续内存结构，由多个固定大小的内存块组成
- 支持 O (1) 时间复杂度的两端插入和删除操作
- 不需要像 vector 那样在扩容时复制所有元素
二、高效插入元素
两端插入效率最高
deque 在头部和尾部的插入操作都是 O (1) 时间复杂度，这是它相比 vector 的主要优势：
1
2
3
4
5
6
7
8
9
| std::deque<int> dq;
dq.push_back(10);
dq.emplace_back(20);
dq.push_front(5);
dq.emplace_front(3);
|
中间插入的特点
与 vector 类似，deque 的中间插入仍需移动元素，时间复杂度为 O (n)，但实际性能可能略优于 vector，因为只需移动所在内存块的元素：
1
2
3
4
5
6
7
8
9
| std::deque<int> dq = {1,2,3,4,5};
auto it = dq.begin() + 2;
dq.insert(it, 100);
std::vector<int> temp = {200, 300};
dq.insert(dq.end(), temp.begin(), temp.end());
|
三、高效删除元素
两端删除同样高效
deque 的头部和尾部删除操作都是 O (1) 时间复杂度：
1
2
3
4
| std::deque<int> dq = {1,2,3,4,5};
dq.pop_back();
dq.pop_front();
|
范围删除与条件删除
deque 支持与 vector 类似的范围删除和 erase-remove 惯用法：
1
2
3
4
5
6
7
8
9
10
11
| #include <algorithm>
std::deque<int> dq = {1,2,3,4,5,6,7};
dq.erase(dq.begin()+1, dq.begin()+4);
dq.erase(std::remove_if(dq.begin(), dq.end(),
[](int x){ return x % 2 == 0; }),
dq.end());
|
四、deque的常用操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include <iostream>
#include <deque>
#include <algorithm>
int main() {
// 1. 多种构造方式
std::deque<int> dq1; // 空deque
std::deque<int> dq2(3, 10); // 3个元素，均为10
std::deque<int> dq3 = {1, 2, 3, 4, 5}; // 列表初始化
std::deque<int> dq4(dq3.begin() + 1, dq3.end() - 1); // 迭代器范围构造
std::deque<int> dq5(dq3); // 拷贝构造
// 2. 元素添加操作
dq1.push_back(20); // 尾部添加
dq1.push_back(30);
dq1.emplace_back(40); // 尾部直接构造（C++11）
dq1.push_front(10); // 头部添加（deque的特色操作）
dq1.emplace_front(5); // 头部直接构造
// 在中间位置插入
auto it = dq1.begin() + 2;
dq1.insert(it, 15); // 在位置2插入15
// 3. 元素访问操作
std::cout << "dq3第一个元素: " << dq3[0] << std::endl;
std::cout << "dq3第二个元素: " << dq3.at(1) << std::endl;
std::cout << "dq3最后一个元素: " << dq3.back() << std::endl;
std::cout << "dq3第一个元素: " << dq3.front() << std::endl; // 头部访问
// 4. 迭代器遍历
std::cout << "dq1所有元素: ";
for (std::deque<int>::iterator iter = dq1.begin(); iter != dq1.end(); ++iter) {
std::cout << *iter << " ";
}
std::cout << std::endl;
// 5. 反向遍历
std::cout << "dq3反向遍历: ";
for (auto iter = dq3.rbegin(); iter != dq3.rend(); ++iter) {
std::cout << *iter << " ";
}
std::cout << std::endl;
// 6. 范围for循环遍历（C++11）
std::cout << "dq2所有元素: ";
for (const auto& elem : dq2) {
std::cout << elem << " ";
}
std::cout << std::endl;
// 7. 元素修改操作
dq3[2] = 100; // 下标修改
dq3.at(3) = 200; // at()修改
// 8. 删除操作
dq3.pop_back(); // 删除尾部元素
dq1.pop_front(); // 删除头部元素（deque的特色操作）
// 范围删除
dq3.erase(dq3.begin() + 1); // 删除指定位置元素
// 条件删除（erase-remove惯用法）
dq3.erase(std::remove_if(dq3.begin(), dq3.end(),
[](int x) { return x > 50; }), // 删除所有大于50的元素
dq3.end());
// 9. 容器属性
std::cout << "dq1当前大小: " << dq1.size() << std::endl;
std::cout << "dq3是否为空: " << (dq3.empty() ? "是" : "否") << std::endl;
// 10. 交换与清空
dq4.swap(dq5); // 交换两个deque内容
dq5.clear(); // 清空所有元素
return 0;
}
|
代码输出结果
1
2
3
4
5
6
7
8
9
| dq3第一个元素: 1
dq3第二个元素: 2
dq3最后一个元素: 5
dq3第一个元素: 1
dq1所有元素: 5 10 15 20 30 40
dq3反向遍历: 5 4 3 2 1
dq2所有元素: 10 10 10
dq1当前大小: 5
dq3是否为空: 否
|
五、deque 使用注意事项
- deque 没有 reserve () 方法，无法预先分配容量
- 迭代器失效规则更复杂：
- 两端插入可能导致迭代器、指针和引用失效
- 中间插入总是导致所有迭代器、指针和引用失效
- 内存使用效率可能低于 vector，因为存在内存块管理开销
六、deque 与 vector 的选择策略
- 优先使用 deque 的场景：
- 需要频繁在容器两端进行插入删除操作
- 不确定元素数量上限，且希望避免 vector 的扩容开销
- 需要高效的头部操作
- 优先使用 vector 的场景：
- 需要频繁随机访问元素（vector 的缓存局部性更好）
- 主要在尾部进行操作
- 需要与 C 风格数组交互（vector 的数据是连续的）
