什么是 deque？
deque（double-ended queue，双端队列）是 C++ STL 中一个非常实用的序列容器。它的名字就说明了核心特性：可以在两端高效地进行插入和删除操作。
与 vector 只能在尾部高效操作不同，deque 在头部和尾部都能做到 O(1) 的插入和删除，这让它在很多场景下比 vector 更加灵活。
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
| #include <iostream>
#include <deque>
int main() {
std::deque<int> dq;
dq.push_back(1);
dq.push_back(2);
dq.push_back(3);
dq.push_front(0);
dq.push_front(-1);
for (int x : dq) {
std::cout << x << " ";
}
std::cout << std::endl;
dq.pop_front();
dq.pop_back();
for (int x : dq) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
|
deque 的内部实现原理
deque 的底层结构比 vector 复杂得多，这也是它功能更强大的原因。
分段连续空间
vector 是一块连续的内存，deque 则是多块连续内存的组合。它使用一个中控数组（map）来管理这些内存块：
1
2
3
| map指针数组: [block1_ptr] [block2_ptr] [block3_ptr] ...
↓ ↓ ↓
内存块: [ | | | ] [ | | | ] [ | | | ]
|
每个 block（通常 512 字节）存储多个元素，map 数组记录每个 block 的地址。当需要扩容时，只需要在 map 数组两端添加新的 block 指针，无需像 vector 那样整体搬迁数据。
迭代器的复杂性
正因为内存是分段的，deque 的迭代器比 vector 复杂。迭代器需要维护：
- 当前元素指针
- 当前所在 buffer 的首尾指针
- 中控 map 的指针
这也意味着 deque 的迭代器比 vector 的指针迭代器更”重”，在某些场景下可能影响性能。
常用操作全览
构造与初始化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include <deque>
#include <vector>
std::deque<int> d1;
std::deque<int> d2(10);
std::deque<int> d3(10, 42);
std::deque<int> d4(d3);
std::vector<int> v = {1, 2, 3, 4, 5};
std::deque<int> d5(v.begin(), v.end());
std::deque<int> d6 = {10, 20, 30, 40, 50};
|
元素访问
1
2
3
4
5
6
7
8
9
10
11
12
| std::deque<int> dq = {10, 20, 30, 40, 50};
std::cout << dq[0] << std::endl;
std::cout << dq[4] << std::endl;
std::cout << dq.at(2) << std::endl;
std::cout << dq.front() << std::endl;
std::cout << dq.back() << std::endl;
|
插入和删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| std::deque<int> dq = {2, 3, 4};
dq.push_front(1);
dq.push_back(5);
dq.pop_front();
dq.pop_back();
auto it = dq.begin() + 1;
dq.insert(it, 99);
it = dq.begin() + 1;
dq.erase(it);
dq.erase(dq.begin(), dq.begin() + 2);
dq.clear();
|
大小操作
1
2
3
4
5
6
7
8
9
10
11
12
| std::deque<int> dq = {1, 2, 3, 4, 5};
std::cout << dq.size() << std::endl;
std::cout << dq.max_size() << std::endl;
std::cout << dq.empty() << std::endl;
dq.resize(3);
dq.resize(5, 0);
dq.shrink_to_fit();
|
deque vs vector vs list 对比
这是面试高频题，也是实际选型时的关键考量：
| 特性 |
deque |
vector |
list |
| 随机访问 |
O(1) |
O(1) |
O(n) |
| 头部插入/删除 |
O(1) |
O(n) |
O(1) |
| 尾部插入/删除 |
O(1) |
O(1) 均摊 |
O(1) |
| 中间插入/删除 |
O(n) |
O(n) |
O(1)* |
| 内存连续性 |
分段连续 |
完全连续 |
不连续 |
| 迭代器失效 |
插入时部分失效 |
插入时全部失效 |
不失效 |
| 缓存友好性 |
较好 |
最好 |
差 |
*list 的中间插入/删除找到位置后是 O(1)，但找到位置本身是 O(n)。
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
| #include <iostream>
#include <deque>
#include <vector>
#include <list>
#include <chrono>
void benchmark_push_front() {
const int N = 1000000;
auto start = std::chrono::high_resolution_clock::now();
std::vector<int> vec;
for (int i = 0; i < N; i++) {
vec.insert(vec.begin(), i);
}
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> vec_time = end - start;
std::cout << "vector push_front " << N << " times: "
<< vec_time.count() << "s" << std::endl;
start = std::chrono::high_resolution_clock::now();
std::deque<int> dq;
for (int i = 0; i < N; i++) {
dq.push_front(i);
}
end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> dq_time = end - start;
std::cout << "deque push_front " << N << " times: "
<< dq_time.count() << "s" << std::endl;
start = std::chrono::high_resolution_clock::now();
std::list<int> lst;
for (int i = 0; i < N; i++) {
lst.push_front(i);
}
end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> list_time = end - start;
std::cout << "list push_front " << N << " times: "
<< list_time.count() << "s" << std::endl;
}
|
在我的机器上，vector 头部插入 100 万次需要好几秒，而 deque 和 list 几乎瞬间完成。
实际使用场景
1. 滑动窗口
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
| #include <iostream>
#include <deque>
std::vector<int> maxSlidingWindow(const std::vector<int>& nums, int k) {
std::deque<int> dq;
std::vector<int> result;
for (int i = 0; i < (int)nums.size(); i++) {
while (!dq.empty() && dq.front() <= i - k) {
dq.pop_front();
}
while (!dq.empty() && nums[dq.back()] < nums[i]) {
dq.pop_back();
}
dq.push_back(i);
if (i >= k - 1) {
result.push_back(nums[dq.front()]);
}
}
return result;
}
int main() {
std::vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
auto result = maxSlidingWindow(nums, 3);
for (int x : result) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
|
2. BFS 队列
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
| #include <iostream>
#include <deque>
#include <vector>
void bfs(const std::vector<std::vector<int>>& graph, int start) {
int n = graph.size();
std::vector<bool> visited(n, false);
std::deque<int> dq;
dq.push_back(start);
visited[start] = true;
while (!dq.empty()) {
int node = dq.front();
dq.pop_front();
std::cout << node << " ";
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
dq.push_back(neighbor);
}
}
}
}
int main() {
std::vector<std::vector<int>> graph = {
{1, 2},
{0, 3, 4},
{0, 4},
{1},
{1, 2}
};
std::cout << "BFS from node 0: ";
bfs(graph, 0);
std::cout << std::endl;
return 0;
}
|
3. 双端 BFS（0-1 BFS）
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
| #include <iostream>
#include <deque>
#include <vector>
int bfs01(int n, const std::vector<std::vector<std::pair<int, int>>>& graph,
int start, int end) {
const int INF = 1e9;
std::vector<int> dist(n, INF);
std::deque<int> dq;
dist[start] = 0;
dq.push_front(start);
while (!dq.empty()) {
int u = dq.front();
dq.pop_front();
if (u == end) return dist[u];
for (auto& [v, w] : graph[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (w == 0) {
dq.push_front(v);
} else {
dq.push_back(v);
}
}
}
}
return -1;
}
|
常见陷阱与注意事项
1. 中间插入/删除效率不高
虽然 deque 支持中间插入删除，但实际效率并不高——需要移动元素到相邻的 block。如果需要频繁在中间操作，考虑 list。
2. 迭代器失效规则复杂
1
2
3
4
5
6
7
8
9
10
| std::deque<int> dq = {1, 2, 3, 4, 5};
auto it = dq.begin() + 2;
dq.push_front(0);
dq.push_back(6);
|
规则：
- 在头部或尾部插入不会使任何迭代器失效
- 在中间插入会使所有迭代器失效
- 删除操作使被删元素及之后的迭代器失效
3. 不要用 deque 存储需要内存连续性的数据
1
2
3
4
5
6
7
8
9
| std::deque<int> dq = {1, 2, 3, 4, 5};
std::vector<int> vec = {1, 2, 3, 4, 5};
int* p = vec.data();
|
4. reserve() 不存在
deque 没有 reserve() 方法。因为它是分段存储的，内存分配策略与 vector 不同。如果需要预留空间，只能在构造时指定大小。
总结
| 场景 |
推荐容器 |
| 主要尾部操作，需要连续内存 |
vector |
| 需要频繁头部操作 |
deque |
| 频繁中间插入删除，不需要随机访问 |
list |
| 滑动窗口、双端 BFS |
deque |
| 需要与 C API 交互 |
vector |
deque 是 STL 中被低估的容器之一。很多人只用 vector，但在需要双端操作的场景下，deque 往往是更好的选择。理解它的底层实现和迭代器失效规则，能帮助你在实际项目中做出正确的选型。
