软件测试面试40问：从理论基础到实战应对，构建可迁移测试思维
2026/10/12 23:11:46
std::deque（double-ended queue，双端队列）是 C++ 标准库中的序列容器，定义在<deque>头文件中。它允许在两端高效地插入和删除，同时支持随机访问。可以把它看作一个“可以在头部和尾部快速操作的动态数组”。
1. 基本概念
模板声明：
cpp
template <class T, class Allocator = std::allocator<T>> class deque;
T：元素类型。Allocator：分配器，默认使用std::allocator<T>。
特点：
动态大小，无需提前指定容量。
在头部和尾部插入/删除元素的时间复杂度为O(1)（均摊）。
支持随机访问，
operator[]和at()时间复杂度O(1)。在中间插入/删除元素时间复杂度O(n)。
元素不是连续存储的，而是分段连续。
不提供
capacity()和reserve()（因为内存分段管理）。迭代器是随机访问迭代器，可用于
std::sort等算法。
2. 底层实现
典型实现方式：
将元素存储在多个固定大小的连续内存块中。
使用一个“中控数组”（map）来管理这些块的指针。
当在头部或尾部插入元素时，如果当前块已满，就分配一个新块，并更新中控数组。
中控数组本身也可能需要重新分配，但已有的元素块不会被移动，因此指向元素的引用和指针通常不会失效（除非在中间插入/删除）。
这种设计使得deque在两端操作非常高效，同时又不像std::list那样每个元素都有额外的指针开销。
3. 与 vector、list 的对比
| 特性 | std::vector | std::deque | std::list |
|---|---|---|---|
| 内存布局 | 单块连续 | 分段连续 | 双向链表，非连续 |
| 随机访问 | O(1) | O(1) | O(n) |
| 尾部插入/删除 | 均摊 O(1) | 均摊 O(1) | O(1) |
| 头部插入/删除 | O(n) | 均摊 O(1) | O(1) |
| 中间插入/删除 | O(n) | O(n) | O(1) |
| 迭代器类型 | 随机访问 | 随机访问 | 双向 |
| 引用/指针稳定性 | 重新分配时失效 | 两端操作不失效，中间操作失效 | 插入/删除不失效 |
| 内存开销 | 低 | 中等（中控数组+块） | 高（每元素两个指针） |
是否支持sort | 是 | 是 | 否（需用list::sort） |
4. 常用成员函数
| 函数 | 说明 |
|---|---|
push_back(val)/emplace_back(args...) | 在尾部插入元素 |
push_front(val)/emplace_front(args...) | 在头部插入元素 |
pop_back() | 删除尾部元素 |
pop_front() | 删除头部元素 |
at(pos) | 带边界检查的访问，越界抛std::out_of_range |
operator[](pos) | 无边界检查的访问 |
front()/back() | 返回首/尾元素的引用 |
size()/empty() | 元素个数 / 是否为空 |
clear() | 清空所有元素 |
insert(pos, val) | 在指定位置插入元素 |
erase(pos) | 删除指定位置元素 |
begin()/end() | 迭代器 |
rbegin()/rend() | 反向迭代器 |
shrink_to_fit() | 请求释放未使用的内存（C++11） |
5. 迭代器失效规则
在两端插入元素：所有迭代器失效，但引用和指针不失效。
在两端删除元素：只有指向被删除元素的迭代器、引用、指针失效。
在中间插入/删除元素：所有迭代器、引用、指针都失效。
重新分配中控数组：可能使迭代器失效，但元素本身不移动，引用仍有效。
因此，如果需要长期持有指向deque元素的引用，应避免在中间进行插入/删除。
#include <deque> #include <iostream> #include <algorithm> // std::sort int main() { std::deque<int> dq; // 1. 从两端插入元素 dq.push_back(10); dq.push_back(20); dq.push_front(5); dq.push_front(1); std::cout << "初始 deque: "; for (int x : dq) std::cout << x << " "; std::cout << "\n大小: " << dq.size() << "\n"; // 2. 随机访问 std::cout << "d[0] = " << dq[0] << ", d.at(2) = " << dq.at(2) << "\n"; // 3. 修改元素 dq[1] = 100; dq.at(2) = 200; std::cout << "修改后: "; for (int x : dq) std::cout << x << " "; std::cout << "\n"; // 4. 从两端删除 dq.pop_front(); dq.pop_back(); std::cout << "pop后: "; for (int x : dq) std::cout << x << " "; std::cout << "\n"; // 5. 排序（deque 支持随机访问迭代器） std::sort(dq.begin(), dq.end()); std::cout << "排序后: "; for (int x : dq) std::cout << x << " "; std::cout << "\n"; // 6. 在中间插入和删除 auto it = dq.begin(); ++it; // 指向第二个元素 dq.insert(it, 99); // 在第二个元素前插入99 std::cout << "插入99后: "; for (int x : dq) std::cout << x << " "; std::cout << "\n"; dq.erase(dq.begin()); // 删除第一个元素 std::cout << "删除第一个后: "; for (int x : dq) std::cout << x << " "; std::cout << "\n"; return 0; }