Chapter 12: Deque
核心问题与阅读主线
工程中常遇到一对双向需求:既要像 std::vector 那样以 O(1) 下标随机访问,又要在头尾两端高效增删而不搬迁已有元素。std::deque 通过“控制数组 + 分段连续 block”折中在 std::vector 与 std::list 之间,以多一次间接寻址和更严格的 iterator 失效规则换取双端扩展能力。
全章共用场景样本
全章贯穿同一个观察模型 std::deque<int> q:底层由多个固定大小的连续 block 承载元素,外层控制数组保存各 block 地址,begin 与 end 标定当前有效区间 [begin, end)。后续各节按此拆解每次操作修改哪一层状态、何时触发分配,以及引用与 iterator 的失效边界。
C++ 标准只规定 std::deque 为随机访问 sequence container,保证头尾 O(1)、中间线性增删(见 deque overview);工业实现普遍采用“控制数组 + 固定大小缓冲块”(见 cppreference 的 std::deque)。正文严格区分可移植的标准承诺与典型底层实现。
12.1 双端队列语义与分段连续内存
std::deque 对外呈现从 0 到 size() - 1 的线性序列,支持 front()、back()、operator[]、at()、push_front()、push_back()、pop_front() 与 pop_back()。
其底层采用分段连续存储:每个 block 内部地址连续,block 之间物理地址可分散。首尾增长优先复用端点 block 剩余槽位;端点 block 耗尽时,才分配新 block 并挂载到对应端。
#include <deque>
#include <iostream>
int main() {
std::deque<int> q;
q.push_back(10);
q.push_back(20);
q.push_front(5);
std::cout << q[0] << ' ' << q[1] << ' ' << q[2] << '\n';
}
输出为 5 10 20:调用方看到的是连续逻辑下标,而 5 与 10、20 完全可能落在不同的物理 block 中。
下面的模型图展示了这几层的指向关系;图中 map 是 deque 常见实现里的控制数组(block 指针表),与关联容器 std::map 无关。
除图中连接关系外,还需明确三点结构约束与复杂度后果:
deque容器对象本身不存放元素,仅保存控制数组地址、大小、起止 iterator 及 allocator 状态。- 序列有效元素落在
[begin, end)区间内;首尾 block 外侧的剩余槽位只是未构造对象的原始存储。 - 头尾增删仅改端点槽位或接入新 block(
O(1));下标按“block 编号 + 块内偏移”换算(O(1));中间增删向较近一端搬移元素(线性时间)。
核心判断
只需尾部增长或整段连续内存(如 C 接口 / SIMD)选 std::vector;只需稳定节点重连选 std::list;只有同时要求“头尾 O(1) 增删 + O(1) 下标访问”时,std::deque 的结构才成立。
12.2 map 控制结构、block / buffer 与 iterator 状态
常见 std::deque 实现由控制数组、block 与 iterator 协同支撑。阅读源码时遇到的 _M_map、__map_、_Map、_M_node、__block_size 等符号,均可归入以下四层角色:
| 内部角色 | 保存内容 | 直接服务的操作 | 工程后果 |
|---|---|---|---|
| 容器对象 | 控制数组、起止 iterator、大小与 allocator 状态 | 所有成员函数入口 | 对象体积小,不直接存元素数组 |
控制数组(map) | block 指针序列 | 两端扩展、随机定位 | 控制数组扩展会使现有 iterator 失效 |
block / buffer | 固定数量的元素槽位 | 构造、析构、局部遍历 | 块内局部性好,跨块需间接寻址 |
iterator | 当前元素、block 边界、block 槽位 | 遍历、跳转、距离计算 | 体积与维护成本高于 vector 裸指针 |
其中两项底层策略直接影响内存与源码阅读:
- 控制数组居中扩容:
map本身是动态指针数组。当头部或尾部控制槽位耗尽时,容器分配更大的新map,将现有 block 指针复制到新数组的中央区域,为两端继续增长预留对称余量。 - block 容量由实现决定:单块可容纳的元素个数通常依据
sizeof(T)选取(小对象每块较多,大对象每块较少),标准不固定该数值,不能将其视为可移植常量。
deque 的 iterator 比 vector 的元素指针更重。下面简化模型表达了它的典型状态(非特定标准库源码):
template <class T>
struct deque_iterator_shape {
T* current; // 当前元素位置
T* block_begin; // 当前 block 起点
T* block_end; // 当前 block 终点后一位
T** block_slot; // 控制数组中当前 block 指针的位置
};
该结构直接决定了 iterator 移动的两种开销来源:
- 自增(
++it):块内推进仅递增current;到达块尾时须读取block_slot + 1,再刷新block_begin、block_end与current。 - 随机跳转(
it + n):将块内偏移与n合并,算出目标控制槽位与目标块内偏移;虽属O(1),但比裸指针加法多出算术运算与控制数组间接访存。
边界与误区
end()指向尾元素后一槽位,既可能落在尾端 block 的空槽,也可能位于下一个 block 的起点;任何端点增删后都应重新获取end(),不可复用旧边界。- 评估操作影响时先判断是否触及
map或跨块边界:只要发生控制数组重排或边界迁移,旧 iterator 即失效。
12.3 push_front、push_back、pop_front 与 pop_back
两端操作将变更限制在序列首尾,按“查端点空槽 → 按需分配/处理 block → 提交 begin/end”三步推进,避免像 vector 那样迁移全部已有元素:
| 操作 | 端点 block 有空槽 | 端点 block 已满 / 变空 | 已有元素引用 | iterator 稳定性 |
|---|---|---|---|---|
push_back(x) | 在 end 槽位构造元素,推进 end | 扩展 map(若满)并挂尾块,首槽构造后更新 end | 保持有效 | 全部失效 |
push_front(x) | 先回退 begin,再于新位置构造元素 | 扩展 map(若满)并挂首块,末槽构造后更新 begin | 保持有效 | 全部失效 |
pop_back() | 析构尾元素,回退 end | 尾块变空时由实现释放或缓存该 block | 非被删元素有效 | 被删位置与 end() 失效 |
pop_front() | 析构首元素,推进 begin | 首块变空时由实现释放或缓存该 block | 非被删元素有效 | 被删位置失效;工程上应重取 begin()/end() |
下面的简化伪代码展示 push_back 的提交点(省略 allocator_traits、异常 guard 与控制数组增长细节):
template <class T>
void mini_deque_push_back_shape(T value) {
if (end_has_free_slot()) {
construct_at(end.current, std::move(value));
++end.current;
return;
}
ensure_map_slot_at_back();
T* new_block = allocate_block();
map[end.block_slot + 1] = new_block;
construct_at(new_block, std::move(value));
move_end_to_first_slot_after(new_block);
}
这里把“存储准备(申请 map 槽位与新 block)→ 对象生命周期开始(construct_at)→ 状态提交(更新 end)”严格拆开。push_front 与之对称,且两者都必须在分配与构造全部成功后才提交新边界,确保异常路径可恢复。
修改循环中应每次重新读取端点,切勿在循环外持有旧 begin() 或 end():
#include <deque>
void consume_edges(std::deque<int>& q) {
while (!q.empty()) {
int front_value = q.front();
q.pop_front();
if (!q.empty() && front_value % 2 == 0) {
q.push_back(front_value / 2);
}
}
}
front_value 按值保存元素内容,pop_front() 后与容器内部存储再无引用耦合;所有状态判定均在修改后重新通过 q.empty()、q.front() 获取。
12.4 扩容方式、allocator 参与与 O(1) 随机访问
std::deque 的存储扩展以单个 block 为单位,与 allocator 职责清晰分离:
- 扩容不搬迁对象:
vector扩容需整段迁移已有元素;deque通常只新申请一个 block 并写入map,即便map自身扩容也仅复制T*指针,已有元素始终留在原 block 中。 - allocator 的双层分工:allocator(或 rebound allocator)负责为 block 申请和释放原始存储;
allocator_traits负责在槽位上构造和销毁元素对象。map指针表的内存属于容器内部结构,与元素生命周期隔离。 - 单元素强异常安全:端点单元素插入依次经过
map扩展、block 分配、元素构造与边界提交;任一准备或构造步骤抛异常时,标准保证本次插入无效果,size()与旧边界不受影响。
下标访问 operator[] 通过两次寻址把逻辑下标映射到具体 block:
std::size_t absolute = start_offset + i;
std::size_t block_index = absolute / block_size;
std::size_t inner_index = absolute % block_size;
T& value = map[block_index][inner_index];
虽然渐近复杂度与 vector 同为 O(1),但 vector 只需单段指针偏移 *(data + i),而 deque 多出整除、取模与一次控制数组间接访问。热路径性能仍受指令数、分支、cache 命中与硬件预取影响。
关键事实
std::deque 没有 reserve():由于元素分散在多个独立 block 中,标准不暴露“预留 block 数”或“预分配 map 容量”的接口。若协议要求提前锁定一整段连续内存,应改用 std::vector、std::array 或通过 std::span 暴露连续视图。
排查顺序
- 看位置:操作发生在头尾端点还是序列中段?
- 看端点 block:对应端点 block 是否尚有未构造的空槽?
- 看控制数组:
map对应方向是否还有空槽,是否会引发map扩展重排? - 看提交点:元素构造/析构是否成功,边界是否已提交,异常回滚是否干净?
- 套失效规则:分别核对元素引用与 iterator,切勿把“元素未搬迁”误推为“iterator 可继续使用”。
12.5 iterator 失效、cache locality 与容器对比
deque 元素引用与 iterator 的稳定性不同,根源在于两者保存的信息粒度不同:引用直接指向未搬迁 block 中的对象,而 iterator 额外缓存了可能过期的 block_slot 与 block 边界。
| 修改操作 | 已有元素引用 | iterator 有效性 | 原因 |
|---|---|---|---|
头尾插入(push_front / push_back) | 保持有效 | 全部失效 | 元素留在原 block;但 map 可能重排且端点边界变化 |
头尾删除(pop_front / pop_back) | 仅被删元素失效 | 被删位置与 end() 失效(pop_front 后亦须重取 begin()/end()) | 被删对象生命周期结束,边界状态更新 |
| 中段插入 / 删除 | 失效 | 全部失效 | 需向较近一端搬移元素并调整分段边界 |
下面示例演示 push_front 后引用与 iterator 的行为分界:
#include <deque>
#include <iostream>
int main() {
std::deque<int> q = {1, 2, 3};
int& ref = q[1];
auto it = q.begin() + 1;
q.push_front(0);
std::cout << ref << '\n'; // ref 仍指向原来的元素 2
// std::cout << *it << '\n'; // 修改后继续使用旧 iterator 没有可移植保证
}
跨修改保留定位时,稳妥写法是记录逻辑索引并在修改后重新计算 q.begin() + new_index。
在访问局部性与容器选型上,deque 与 vector、list 的工程边界如下:
- cache locality:
deque同一 block 内顺序访问局部性好,但跨 block 须经map跳转,硬件预取弱于vector。大规模线性扫描、排序、二分及对接 SIMD / C 连续缓冲区时应优先选vector。 - 对比
list:deque省去每节点前后指针且支持O(1)随机访问;但中段增删仍要搬移元素,无法提供list那样恒定节点的指针重连与插入时 iterator 稳定性。
| 维度 | vector | deque | list |
|---|---|---|---|
| 物理存储 | 单段连续 | 多 block 分段连续 | 独立节点 |
| 随机访问 | O(1),路径最短 | O(1),多一次分段定位 | 无下标随机访问 |
| 头部插入删除 | 线性移动 | 常数时间端点操作 | 常数时间节点操作 |
| 尾部插入删除 | 摊还常数,扩容迁移元素 | 常数时间端点操作 | 常数时间节点操作 |
| 中间插入删除 | 线性移动 | 线性移动(通常选较近端) | 常数时间重连已定位节点 |
| iterator 稳定性 | 扩容和移动影响大 | 端点插入使 iterator 失效,引用较稳定 | 插入通常稳定,删除仅影响被删节点 |
| cache locality | 最好 | block 内较好,跨 block 较弱 | 通常较弱 |
| 典型用途 | 连续数据、热遍历、排序 | 双端队列、滑动窗口、queue 底层 | 稳定节点、频繁 splice |
核心判断
容器选型按三问收敛:必须连续 buffer 或极致热遍历选 vector;必须在已定位中段频繁插删、splice 且保持 iterator 稳定选 list;同时需要“两端增删 + 下标随机访问”且不要求单段连续内存时选 deque。
12.6 deque 复杂度来源与 mini deque 实现
mini_deque_shape 只聚焦四个核心部件:控制数组、固定大小 block、iterator 与端点操作。真实标准库还需补齐 allocator_traits 传播、完整异常安全、拷贝移动、范围插入、比较运算、shrink_to_fit 与 C++23 range 接口。
为保持示例紧凑,下面用 std::vector<T*> 暂代自管控制数组(真实标准库会自行管理 map 以精确控制两端居中预留),足以验证“控制数组管 block、block 存元素、绝对偏移定边界”的对象模型:
#include <cstddef>
#include <memory>
#include <vector>
template <class T, std::size_t BlockSize = 8>
class mini_deque_shape {
using alloc_traits = std::allocator_traits<std::allocator<T>>;
std::allocator<T> alloc_;
std::vector<T*> blocks_;
std::size_t first_ = 0; // 逻辑第一个元素的绝对偏移
std::size_t size_ = 0;
T* allocate_block() {
return alloc_traits::allocate(alloc_, BlockSize);
}
void ensure_back_block() {
std::size_t end_abs = first_ + size_;
std::size_t block_index = end_abs / BlockSize;
while (blocks_.size() <= block_index) {
T* new_block = allocate_block();
try {
blocks_.push_back(new_block);
} catch (...) {
alloc_traits::deallocate(alloc_, new_block, BlockSize);
throw;
}
}
}
public:
mini_deque_shape() = default;
mini_deque_shape(const mini_deque_shape&) = delete;
mini_deque_shape& operator=(const mini_deque_shape&) = delete;
~mini_deque_shape() {
for (std::size_t i = 0; i < size_; ++i) {
std::size_t abs = first_ + i;
T* ptr = blocks_[abs / BlockSize] + (abs % BlockSize);
alloc_traits::destroy(alloc_, ptr);
}
for (T* block : blocks_) {
alloc_traits::deallocate(alloc_, block, BlockSize);
}
}
void push_back(const T& value) {
ensure_back_block();
std::size_t abs = first_ + size_;
T* ptr = blocks_[abs / BlockSize] + (abs % BlockSize);
alloc_traits::construct(alloc_, ptr, value);
++size_;
}
T& operator[](std::size_t index) {
std::size_t abs = first_ + index;
return blocks_[abs / BlockSize][abs % BlockSize];
}
std::size_t size() const noexcept {
return size_;
}
};
上例只演示了单向尾增与随机访问,补全双向能力的关键路径如下:
push_back与operator[]:push_back先补齐尾端 block,再于first_ + size_构造对象并递增size_;operator[]将逻辑下标加first_拆为块号与块内偏移。- 扩展
push_front:初始化时预留前置控制槽位并把首块置于中央区域(或改用环形控制数组);当begin顶到当前 block 起点时,向前取槽位挂接前置 block,并将begin切至新 block 末尾。
补全 mini iterator 的四个核心支点:
- 保存当前绝对偏移,或保存当前元素指针与所在
block_slot。 ++it在 block 内递增指针,越过块尾时切换到下一 block。it + n按BlockSize换算目标控制槽位与块内偏移。- 两 iterator 之差由绝对偏移差或“槽位差 ×
BlockSize+ 块内偏移差”算出。
关键事实
验收 mini deque 实现须先核对以下不变量:
- 空容器
size() == 0,begin与end标定同一位置。 - 有效区间
[begin, end)内每个槽位均处于已构造生命周期;区间外已分配槽位仅是原始内存,析构时绝不能调用destroy。 push_front/push_back仅在构造成功后提交边界;pop_front/pop_back先销毁元素再移动边界。- 析构函数只销毁有效区间内的对象,再通过
deallocate释放全部已分配 block。
最小自检任务
阅读下面代码,判断三件事:ref 在 push_front 后是否还能使用,旧 it 在 push_front 后是否还能解引用,q[2] 的随机访问为什么仍是 O(1)。
#include <deque>
#include <iostream>
int main() {
std::deque<int> q = {10, 20, 30};
int& ref = q[1];
auto it = q.begin() + 1;
q.push_front(5);
std::cout << ref << '\n';
std::cout << q[2] << '\n';
// std::cout << *it << '\n';
}
本章知识点总结
- 分段连续模型
std::deque对外提供线性随机访问接口,底层由“控制数组(map)+ 多个固定大小 block”构成,块内连续而块间地址可分散。 - iterator 状态与成本
dequeiterator 持有当前元素、block 起止边界与map槽位指针;跨块推进与随机跳转均比vector裸指针多出控制数组间接寻址。 - 双端操作提交序
push_front/push_back遵循“存储准备 → 槽位构造 → 边界提交”以保障单元素强异常安全;pop_front/pop_back先析构再移动边界,空 block 可由实现释放或缓存。 - 扩容与 reserve 缺失
增长按单个 block 增量分配,即便
map重排也只复制指针而不搬迁已有元素;因存储非单段连续,标准不提供reserve()。 - 引用与 iterator 失效分界
头尾插入保持已有元素引用有效但使全部 iterator 失效;头尾删除使被删位置与
end()失效(工程上应重取首尾边界);中段修改大范围失效。 - 局部性与容器选型
deque块内局部性好而跨块硬件预取弱于vector;需连续 buffer 选vector,需稳定节点重连选list,仅“双端增删 + 下标访问”选deque。 - mini deque 不变量
最小实现聚焦
map、固定 block、iterator 与端点提交;有效区间[begin, end)外仅存原始内存,析构须严格隔离destroy与deallocate。