Chapter 52: Mini Deque
核心问题与阅读主线
deque 必须在不搬迁已有元素的前提下,同时满足头尾 O(1) 增删与 O(1) 随机访问。本章实现的 MiniDeque 采用“一级控制数组 map_ + 固定大小缓冲块 block + 四字段 iterator”结构,围绕两端 push/pop 的提交顺序与下标定位公式拆解最小实现。
全章共用代码样本(下文各节持续拆解)
贯穿本章的操作序列如下,后续各节按此追踪状态演进(教学模型固定 BLOCK_SIZE = 4,真实标准库按元素大小、ABI、调试模式与 allocator 策略选择块容量):
MiniDeque<int> d;
d.push_back(10);
d.push_back(20);
d.push_front(5);
d.push_back(30);
d.pop_front();
int x = d[1]; // 期望读到 20
标准语义上,std::deque 属于 indexed sequence container,保证两端插入删除与随机访问均为常数复杂度,常见实现采用分段固定大小数组加外层控制结构(见 std::deque 概览)。本章严格区分标准接口契约与教学代码的简化布局。
52.1 map 结构
map_ 是 MiniDeque 的一级索引控制数组(与关联容器 std::map 无关),第 i 个控制槽保存第 i 个缓冲块 block 的起始地址,本身不存放元素对象。容器通过四层角色协同支撑双向增长与随机定位:
| 层级 | 保存状态 | 核心职责与增长触发条件 |
|---|---|---|
| 容器对象 | map_、map_size_、size_、begin_、end_、alloc_ | 管理控制数组与 [begin_, end_) 半开区间 |
控制数组(map_) | Pointer* 槽位数组 | 索引各 block;端部无空槽时才重新分配更大 map_ |
缓冲块(block) | BLOCK_SIZE 个 T 原始存储槽 | 承载块内连续对象;边界块满时按需申请新块 |
iterator | cur、first、last、node | 回指控制槽与块边界,支撑跨块常数步跳转 |
下面展示教学版 MiniDeque 的最小状态(省略完整拷贝、移动与 allocator propagation):
template<class T, class Alloc = std::allocator<T>>
class MiniDeque {
static constexpr std::size_t BLOCK_SIZE = 4;
using Traits = std::allocator_traits<Alloc>;
using Pointer = typename Traits::pointer;
Alloc alloc_{};
Pointer* map_ = nullptr; // 控制数组,元素是 block 指针
std::size_t map_size_ = 0; // 控制槽数量
std::size_t size_ = 0; // 已构造元素数量
struct iterator;
iterator begin_{}; // 指向第一个元素
iterator end_{}; // 指向末尾后一格
};
当 BLOCK_SIZE = 4 时,教学实现通常将首个 block 置于 map_[middle],并令 begin_.cur == end_.cur == block + 2,让初始连续 push_front 与 push_back 都具备块内余量(居中布置属实现策略,非标准强制要求):
关键事实
begin_.node到end_.node覆盖当前序列可能占用的map_控制槽。begin_指向首个有效元素,end_指向末尾后一格,已构造对象仅存于半开区间[begin_, end_),边界外槽位只是原始存储。begin_与end_不存逻辑整数下标,而是直接保存指针与控制槽地址以保证自增、自减与随机跳转均为常数步。
边界与误区
map_ 扩展时只重新分配更大的 Pointer* 数组,将已有 block 指针搬到新数组中央并更新 begin_.node 与 end_.node。元素对象留在原 block 内不搬迁,因此已有元素引用保持有效;但持有旧 node 地址的外部 iterator 会全部失效。
核心判断
后续两端操作统一按四步判定:1. 检查边界 iterator 块内是否有空槽;2. 跨块前检查 map_ 端部是否有控制槽;3. 按需分配 block 并写入控制槽;4. 构造或析构成功后提交 begin_ 或 end_。
52.2 block 结构
block 是 MiniDeque 的二级存储单位,本质是一段容纳 BLOCK_SIZE 个 T 的原始存储。根据 C++ 对象生命周期规则,分配 block 仅获得内存地址,元素必须在 push/emplace 时经 allocator_traits 构造才成为有效对象,且在释放 block 前必须先销毁其中全部已构造对象:
template<class T, class Alloc>
class MiniDequeStorage {
static constexpr std::size_t BLOCK_SIZE = 4;
using Traits = std::allocator_traits<Alloc>;
using Pointer = typename Traits::pointer;
Alloc alloc_{};
Pointer allocate_block() {
return Traits::allocate(alloc_, BLOCK_SIZE);
}
void deallocate_block(Pointer block) noexcept {
Traits::deallocate(alloc_, block, BLOCK_SIZE);
}
};
固定大小 block 提供了块内局部性:push_back(10) 与 push_back(20) 沿 end_.cur 连续构造,push_front(5) 在 begin_.cur - 1 构造,均无需搬迁已有元素。与整段连续的 vector 相比,MiniDeque 的工程取舍如下:
| 对比维度 | MiniDeque(分段 block) | vector(单段连续存储) |
|---|---|---|
| 扩容行为 | 仅新增 block 并写入 map_,已有元素不动 | 整段重分配并迁移全部已有元素 |
| 局部性与预取 | 块内连续较好,跨块跨越不同分配块 | 全程单段连续,cache locality 与硬件预取最优 |
| 随机访问常数因子 | 需做整除、取模与两次指针间接寻址 | 仅基址加偏移,路径最短 |
当头尾元素弹出导致某块变空且仍有后续(或前驱)块时,实现应释放该空块并将边界 iterator 切到邻块;若容器整体变空,可按策略二选一:
- 保留单个空
block:作为下次重新增长的起点,省去一次分配。 - 释放全部
block:归还全部存储,下次push时重新初始化首块。
两种策略都必须保证 empty() 为真时 [begin_, end_) 为空区间,任何解引用均无有效对象支撑。
关键事实
block 生命周期遵循四步:allocate 只获取原始存储 → construct 后槽位进入有效生命周期 → destroy 后退回原始存储 → 整块无有效对象且不再作为边界缓冲时才 deallocate。有效对象范围由 [begin_, end_) 完整界定,无需为每个槽位额外记录构造标记。
52.3 iterator
由于逻辑序列跨越多个独立 block,MiniDequeIterator 不能只保存单个指针,而需保存四个字段:cur(当前元素槽)、first(当前块首)、last(当前块尾后一格)与 node(指向 map_ 中的控制槽)。其中 first 与 last 可由 *node 推导,缓存在 iterator 内可直接加速边界判定:
template<class T>
struct MiniDequeIterator {
static constexpr std::ptrdiff_t BLOCK_SIZE = 4;
T* cur = nullptr;
T* first = nullptr;
T* last = nullptr;
T** node = nullptr;
void set_node(T** new_node) {
node = new_node;
first = *new_node;
last = first + BLOCK_SIZE;
}
T& operator*() const {
return *cur;
}
MiniDequeIterator& operator++() {
++cur;
if (cur == last) {
set_node(node + 1);
cur = first;
}
return *this;
}
MiniDequeIterator& operator--() {
if (cur == first) {
set_node(node - 1);
cur = last;
}
--cur;
return *this;
}
};
跨块边界的自增、自减与尾哨兵规则如下:
operator++:块内直接++cur;若抵达last,调用set_node(node + 1)并把cur置于下一块first。operator--:若cur == first,先调用set_node(node - 1)并把cur置于前一块last,再执行--cur。end_语义:与普通iterator共用同构状态,既可位于尾块中间,也可位于末块last或下一块first;push_back先在end_.cur构造再推进end_,pop_back先回退end_再销毁。
随机访问 operator+= 将当前块内偏移与步长 n 合并,块内直接加减,跨块则按整除与余数定位目标控制槽与块内槽位:
MiniDequeIterator& operator+=(std::ptrdiff_t n) {
std::ptrdiff_t offset = (cur - first) + n;
if (0 <= offset && offset < BLOCK_SIZE) {
cur += n;
return *this;
}
std::ptrdiff_t node_offset =
offset >= 0 ? offset / BLOCK_SIZE
: -((-offset - 1) / BLOCK_SIZE) - 1;
set_node(node + node_offset);
cur = first + (offset - node_offset * BLOCK_SIZE);
return *this;
}
边界与误区
C++ 整数除法默认向零截断,因此负偏移 offset < 0 必须通过 -((-offset - 1) / BLOCK_SIZE) - 1 向下取整;若直接写 offset / BLOCK_SIZE,向前回退跨块时 node_offset 与 cur 槽位都会错算。
operator+= 的计算步骤不随元素规模增长,故渐近复杂度仍为 O(1),但除法、取余与二级 node 寻址带来了高于裸指针的常数因子:热路径大量连续下标访问优先选 vector,两端增长与随机访问并存时才选 deque。
52.4 push_front
push_front 在当前首个元素之前构造新元素并将 begin_ 前移。标准保证其具有常数复杂度且已有元素引用不失效(见 push_front 说明)。
当 begin_.cur != begin_.first 时,前端 block 仍有前置空槽:先在 begin_.cur - 1 构造对象,成功后再提交 begin_.cur 与 size_;若构造抛异常,旧序列与边界毫发无伤:
void push_front(const T& value) {
if (begin_.cur != begin_.first) {
T* target = begin_.cur - 1;
Traits::construct(alloc_, target, value);
begin_.cur = target;
++size_;
return;
}
push_front_slow(value);
}
当 begin_.cur == begin_.first 时进入慢路径 push_front_slow,按三步准备新前端块后再提交边界:
- 检查或扩展
map_:调用reserve_map_at_front();若begin_.node == map_,分配更大map_并居中搬移block指针(不移动元素)。 - 分配并挂载新块:申请
new_block写入*(begin_.node - 1),定位目标槽new_block + (BLOCK_SIZE - 1)。 - 构造后提交:在目标槽构造元素,成功后才更新
begin_与size_。
void push_front_slow(const T& value) {
reserve_map_at_front();
T* new_block = Traits::allocate(alloc_, BLOCK_SIZE);
T** new_node = begin_.node - 1;
*new_node = new_block;
T* target = new_block + (BLOCK_SIZE - 1);
try {
Traits::construct(alloc_, target, value);
} catch (...) {
*new_node = nullptr;
Traits::deallocate(alloc_, new_block, BLOCK_SIZE);
throw;
}
begin_.set_node(new_node);
begin_.cur = target;
++size_;
}
慢路径以 begin_.set_node(new_node) 和 begin_.cur = target 为提交点:在此之前构造若抛异常,catch 块会清空 *new_node 并释放 new_block。
代入贯穿序列:初始 push_back(10)、push_back(20) 后 begin_ 仍在块中部(第 2 格),因此 push_front(5) 直接命中快路径写入第 1 格;仅当连续前插把 begin_ 推至 first 时才会进入慢路径。
核心判断
阅读 deque 两端插入源码时,务必分开判断两类稳定性:push_front 不移动已有元素,故元素引用稳定;但慢路径可能触发 map_ 扩展从而改变控制槽地址,故旧 iterator 可能失效。
52.5 push_back
push_back 在 end_ 指向的末尾后一格构造新元素并推进 end_。标准同样保证其为常数复杂度,插入会使 iterator 失效而已有元素引用保持有效(见 push_back 说明)。
当 end_.cur != end_.last 时,直接于 end_.cur 构造对象后再推进 end_.cur 与 size_;当 end_.cur == end_.last 时,进入 push_back_slow 申请后继控制槽与新 block,并在新块首格构造完成后再切换 end_:
void push_back(const T& value) {
if (end_.cur != end_.last) {
T* target = end_.cur;
Traits::construct(alloc_, target, value);
++end_.cur;
++size_;
return;
}
push_back_slow(value);
}
void push_back_slow(const T& value) {
reserve_map_at_back();
T* new_block = Traits::allocate(alloc_, BLOCK_SIZE);
T** new_node = end_.node + 1;
*new_node = new_block;
try {
Traits::construct(alloc_, new_block, value);
} catch (...) {
*new_node = nullptr;
Traits::deallocate(alloc_, new_block, BLOCK_SIZE);
throw;
}
end_.set_node(new_node);
end_.cur = end_.first + 1;
++size_;
}
由于 end_ 表示“末尾后一格”,push_back 与 push_front 在边界与提交位置上呈镜像对称:
| 对比维度 | push_front | push_back |
|---|---|---|
| 快路径判定 | begin_.cur != begin_.first | end_.cur != end_.last |
| 构造目标槽 | begin_.cur - 1 | end_.cur |
| 慢路径新块写入 | *(begin_.node - 1) 的末格 new_block + (BLOCK_SIZE - 1) | *(end_.node + 1) 的首格 new_block |
| 提交后边界 | begin_ 指向新块最后一格 | end_ 指向新块第二格(end_.first + 1) |
在贯穿序列中,BLOCK_SIZE = 4 且初始位置在第 2 格时,push_back(10)(第 2 格)与 push_back(20)(第 3 格,使 end_.cur == end_.last)走快路径;随后 push_back(30) 进入 push_back_slow 分配后继 block 并在首格构造 30,中间 block 与元素位置全程保持不变。
关键事实
push_back 的三个异常风险点均位于边界提交之前:1. reserve_map_at_back() 失败时旧 map_ 仍完好;2. allocate 失败时未改动新块或元素;3. construct 失败时 catch 释放 new_block 并清空 *new_node。仅当全部准备步骤完成后才提交 end_ 与 size_,从而维持序列可回滚性。
52.6 pop_front
pop_front 销毁首个有效元素并将 begin_ 推进至下一元素。该操作为常数复杂度,仅使被删元素的 iterator 与引用失效(见 pop_front 说明)。
容器必须非空(空容器调用在 C++26 前属未定义行为,C++26 hardened implementation 可能触发 contract violation),且按容器约定元素析构函数不应抛出异常:
void pop_front() {
assert(size_ > 0);
T* old = begin_.cur;
T* old_first = begin_.first;
T* old_last = begin_.last;
T** old_node = begin_.node;
Traits::destroy(alloc_, old);
--size_;
if (size_ == 0) {
begin_ = end_;
return;
}
++begin_;
if (old + 1 == old_last && begin_.node != old_node) {
Traits::deallocate(alloc_, old_first, BLOCK_SIZE);
*old_node = nullptr;
}
}
实现在推进 begin_ 前先缓存 old_first、old_last 与 old_node,因为 ++begin_ 可能已将 begin_ 切往下一 block。关键边界分支有两处:
- 容器归零(
size_ == 0):将begin_设为end_恢复空区间不变量;教学代码保留当前单个空block供复用(若选择全部释放,则下次push需重建首块)。 - 跨块释放条件:仅当
old + 1 == old_last && begin_.node != old_node时,说明旧首块已无任何有效元素且剩余元素位于后续block,方可deallocate旧块并清空*old_node = nullptr。
在贯穿例子中,执行 pop_front() 后序列从 [5, 10, 20, 30] 变为 [10, 20, 30]:5 位于第 1 格,begin_ 向后移动一格指向 10 且不触发块释放;若首元素恰好位于某块最后一格,++begin_ 会跨越到下一块首格并同步回收旧首块。
52.7 pop_back
pop_back 销毁最后一个有效元素并将 end_ 回退到新的末尾后一格。该操作为常数复杂度,使被删元素的 iterator、引用及 end() iterator 失效(见 pop_back 说明)。
容器必须非空(空容器调用在 C++26 前属未定义行为,C++26 hardened implementation 可能触发 contract violation)。由于 end_ 指向末尾后一格,pop_back 必须先回退再析构:快路径(end_.cur != end_.first)在同一块内前移并销毁;慢路径(end_.cur == end_.first)则切回前一块末格销毁并释放空尾块:
void pop_back() {
assert(size_ > 0);
if (end_.cur != end_.first) {
--end_.cur;
Traits::destroy(alloc_, end_.cur);
--size_;
if (size_ == 0) {
begin_ = end_;
}
return;
}
pop_back_slow();
}
void pop_back_slow() {
T** empty_tail_node = end_.node;
T* empty_tail_block = *empty_tail_node;
end_.set_node(end_.node - 1);
end_.cur = end_.last - 1;
Traits::destroy(alloc_, end_.cur);
--size_;
if (empty_tail_block != nullptr) {
Traits::deallocate(alloc_, empty_tail_block, BLOCK_SIZE);
*empty_tail_node = nullptr;
}
if (size_ == 0) {
begin_ = end_;
}
}
慢路径中 empty_tail_block 不含任何有效元素(因旧 end_ 位于其首格);若实现未为 end_ 预先保留空块,则 empty_tail_block == nullptr,释放分支自然跳过。两种尾块管理策略只要共同守住 [begin_, end_) 与对象生命周期不变量即可。
| 对比维度 | pop_front | pop_back |
|---|---|---|
| 执行顺序 | 先缓存旧块边界并 destroy(begin_.cur),再 ++begin_ | 先从 end_ 回退到末元素,再 destroy(end_.cur) |
| 跨块判定 | old + 1 == old_last && begin_.node != old_node | end_.cur == end_.first |
| 空块回收 | 释放 old_first 并置 *old_node = nullptr | 释放非空 empty_tail_block 并置 *empty_tail_node = nullptr |
| 失效范围 | 被删元素引用与 iterator | 被删元素引用、被删位置 iterator 与 end() |
边界与误区
pop_back 最常见错误是直接对 end_.cur 调用 destroy。end_.cur 是末尾后一格的未构造槽位;正确路径必须与 push_back 互补:push_back 先在 end_.cur 构造再推进 end_,pop_back 先回退 end_ 再析构。
在贯穿序列里,int x = d[1] 之前未调用 pop_back(),尾元素仍为 30;若紧接着执行 pop_back(),将销毁 30 并回收尾端独立块(或当 30 与 20 同块时仅把 end_.cur 回退一格)。
52.8 random access
deque 的随机访问把逻辑下标换算为“目标 block 编号 + 块内槽位偏移”。标准保证 operator[] 为常数复杂度,普通语义下越界访问无定义行为保障,C++26 hardened implementation 增加了 contract violation 的实现空间(见 operator[] 说明)。
T& operator[](std::size_t index) {
assert(index < size_);
std::size_t begin_offset =
static_cast<std::size_t>(begin_.cur - begin_.first);
std::size_t total = begin_offset + index;
std::size_t node_offset = total / BLOCK_SIZE;
std::size_t slot_offset = total % BLOCK_SIZE;
T* block = *(begin_.node + node_offset);
return block[slot_offset];
}
代入贯穿序列(pop_front() 后为 [10, 20, 30],设 begin_ 指向首块第 2 格,即 begin_offset = 2):
- 访问
d[1]:total = 2 + 1 = 3→node_offset = 0、slot_offset = 3,直接返回同块的20。 - 访问
d[2]:total = 2 + 2 = 4→node_offset = 1、slot_offset = 0,跨到下一块读取30。
iterator::operator+ 与容器 operator[] 共用同一换算公式,二者均依赖两点结构前提:map_ 控制槽连续可寻址,且每个 block 容量固定为 BLOCK_SIZE(若块大小不固定,除法取余失效,必须引入额外前缀长度表)。
边界与误区
下标访问须守住三道边界:1. operator[] 不做运行时越界检查,调用方须保证 index < size_;2. 返回的 T& 仅对 [begin_, end_) 内的有效对象成立;3. map_ 扩展后通过 d[index] 重新计算依然有效,但继续使用此前保留的旧 iterator 会失效。
排查顺序
阅读或调试真实 std::deque 源码时按四步收束:1. 由 map_ 定位控制槽序列,由 block 确认块内连续槽;2. 核对两端修改是否在资源备齐与构造/析构完成后才提交 begin_ / end_;3. 检查下标与跳转是否用“块内偏移 + 逻辑位移”对块容量做整除与取模;4. 将教学常量 BLOCK_SIZE 替换为实现按 sizeof(T) 决定的块大小策略。
最小自检任务
给定教学 MiniDeque<int>(BLOCK_SIZE = 4),初始已分配一个 block,begin_ 与 end_ 均指向该 block 第 2 格。按顺序执行下列代码:
MiniDeque<int> d;
d.push_back(10);
d.push_back(20);
d.push_front(5);
d.push_back(30);
d.pop_front();
int x = d[1];
请判断:哪些操作只修改块内边界、哪些操作会分配新 block;pop_front() 后 begin_ 如何变化;d[1] 为何能在常数时间内返回 20;两端插入触发 map_ 扩展时,旧 iterator 与元素引用各如何变化。
本章知识点总结
- 控制数组与分段存储
map_保存固定大小block指针,实现块内连续、块间分段连接,兼顾双向扩展与随机访问。 - 半开区间与原始存储
分配
block只获原始存储,有效对象仅存在于[begin_, end_),区间外槽位不可解引用或析构。 - 四字段 iterator
通过
cur、first、last与node支撑跨块自增自减,但体积与跳转开销高于vector裸指针。 - 两端提交顺序与异常安全
push_front/push_back慢路径严格按“备控制槽 → 分配block→ 构造元素 → 提交边界”执行,构造失败可干净回滚。 - 两端弹出与空块回收
pop_front先销毁后推进begin_,pop_back先从end_回退再销毁;空出的边界块可按策略释放或保留单块复用。 - 常数时间随机访问
operator[]与operator+=以begin_块内偏移加逻辑位移对BLOCK_SIZE整除取模(负偏移需向下取整),常数因子来自二次寻址。 - 引用稳定与 iterator 失效
两端插入不搬迁元素,已有元素引用保持有效;一旦
map_扩展,保存旧node地址的iterator即失效。