Chapter 52: Mini Deque
deque 的核心工程问题是：如何在支持两端常数时间增长的同时，仍然提供常数时间随机访问。vector 依赖一整段连续存储，扩容时可能迁移全部元素；list 通过节点链接获得局部插入能力，但失去随机访问。本章实现的 mini_deque 选择第三条路径：用一个控制数组保存多个固定大小缓冲块指针，让元素在块内连续、块间分段连接。
标准库层面的 std::deque 是 indexed sequence container，支持两端插入删除和随机访问；常见实现使用一组独立分配的固定大小数组以及额外控制结构，随机访问需要经过控制结构和块内偏移两层定位。这个语义边界可以从 std::deque 概览 中看到：两端插入删除和随机访问都具有常数复杂度，典型存储形状是分段数组。
本章的目标是把 deque 的实现拆成可检查的最小结构：map_ 控制数组、固定大小 block、保存四个位置状态的 iterator、两端 push/pop 的提交顺序，以及下标访问的块定位公式。读完本章后，读者应能画出一个 mini_deque 的状态图，判断一次两端操作会不会分配新 block，会不会扩展控制数组，以及为什么随机访问仍能保持常数时间。
贯穿本章的操作序列如下，后续每节都会回到这组状态变化：
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
为了让实现路径可读，本章使用 BLOCK_SIZE = 4 的教学简化模型。真实标准库实现会根据元素大小、ABI、调试模式和 allocator 策略选择不同块大小；本章只固定一个小块尺寸，用它暴露控制数组、块边界和 iterator 跳转的必要状态。标准语义、常见实现形状和教学简化代码在本章中分开处理：标准规定接口行为和复杂度，常见实现说明分段存储的工程形状，教学代码只承担最小可理解实现。
52.1 map 结构
map_ 是 mini_deque 的一级索引结构。它保存 block 指针，本身不保存元素对象。这个命名容易和 std::map 混淆，在 deque 实现语境里，map 表示“控制数组”：第 i 个控制槽保存第 i 个缓冲块的起始地址。
一个最小 deque 可以抽象成三层对象：容器对象保存 map_、begin_、end_ 和 size_；map_ 的每个有效槽指向一块固定大小原始存储；iterator 通过 node 指回当前控制槽，再通过 cur 指向当前元素位置。这个层级决定了 deque 的扩展方式：增加元素时优先在已有 block 内移动边界；当前端或后端 block 没有空位时，才申请新 block；控制数组端部没有空槽时，才重新分配更大的控制数组。
下面的结构展示了本章采用的最小状态。代码是教学简化代码，省略了完整拷贝、移动和 allocator propagation，只保留 deque 分段存储所需的成员。
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_{}; // 指向末尾后一格
};
map_ 的关键不变量有三条。第一，begin_.node 到 end_.node 之间覆盖当前序列可能使用的 block 槽。第二，begin_ 指向第一个已构造元素，end_ 指向末尾后一格。第三，已构造元素只存在于 [begin_, end_) 这个半开范围内，block 中其他槽只是原始存储。这个半开范围模型让 deque 和 STL 算法保持一致，也让 push/pop 可以用“先准备资源，再构造或析构，最后提交边界”的顺序维护异常安全。
初始状态通常会把第一个 block 放在控制数组中间。这样容器刚开始既能向前增长，也能向后增长。用 BLOCK_SIZE = 4 表示时，可以把空容器布置成：map_[middle] 指向一个 block，begin_.cur == end_.cur == block + 2。中间位置属于教学实现策略，标准只约束接口语义和复杂度；这个布局减少一开始连续 push_front 或连续 push_back 触发控制数组扩展的次数。
这张图的重点是 map_ 与 block 的责任分离。map_ 承担“第几个块”的定位，block 承担“块内第几个槽”的定位。begin_ 和 end_ 不直接保存下标，它们保存足够多的位置状态，让自增、自减和随机跳转都能在常数步内完成。
控制数组扩展时，元素对象通常不移动。实现会申请一个更大的 Pointer* 数组，把已有 block 指针复制到新数组中间，然后更新 begin_.node 和 end_.node 指向新的控制槽地址。旧元素仍在原 block 中，因此元素引用可以保持指向原对象；保存旧 node 地址的 iterator 会失效，因为它的 node 指向旧控制数组。这个现象解释了 deque 的一个工程边界：分段存储降低了元素整体迁移成本，但控制结构迁移会影响 iterator 状态。
本章后续所有操作都按这组判断顺序分析：先看边界 iterator 是否还有块内空位，再看 map_ 端部是否有控制槽，再决定是否分配 block，最后提交 begin_ 或 end_。这个顺序比直接记接口复杂度更可靠，因为它把每次操作的对象状态、内存分配和失败恢复点都固定下来。
52.2 block 结构
block 是 mini_deque 的二级存储单位。它是一段能容纳 BLOCK_SIZE 个 T 对象的原始存储，申请 block 时只获得内存，具体元素对象在 push/emplace 时通过 allocator 构造。这个区分来自 C++ 对象生命周期规则：有存储地址不等于已有有效对象，只有构造完成的槽才能被解引用、析构或作为元素参与算法。
在教学实现中，block 可以直接用 allocator_traits<Alloc>::allocate 申请 BLOCK_SIZE 个 T 的存储。释放 block 之前，必须确保其中所有已构造元素已经销毁。这个责任边界会贯穿 push_front、push_back、pop_front 和 pop_back：push 负责在原始槽上构造对象，pop 负责对有效对象执行 destroy，然后在 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) 在当前 block 的 end_.cur 位置构造元素，然后把 end_.cur 推进一步；push_back(20) 继续使用同一块；push_front(5) 在 begin_.cur - 1 位置构造元素，然后把 begin_.cur 向前移动。只要边界 block 还有空槽，这些操作都不需要移动已有元素。
block 的局部连续性也解释了 deque 和 vector 的性能差异。块内连续访问通常具有较好的 cache locality；跨 block 访问需要多一次控制数组定位，并且相邻逻辑元素可能落在不同分配块。deque 的随机访问仍是常数复杂度，因为定位公式只做除法、取余和两次指针访问；它的常数因子通常高于 vector，因为 vector 的下标访问只需要基址加偏移。
block 的释放策略需要服务迭代器边界。当前端元素全部弹出后，前端 block 可能已经没有有效对象；如果容器还有后续 block，可以释放这个空 block，并把 begin_ 切到下一个 block 的起始位置。尾端同理。如果容器变空，教学实现可以保留一个空 block 作为重新增长的起点，也可以释放所有 block 后在下一次 push 时重新初始化。两种策略都要保持同一个对外结论：empty() 为真时 [begin_, end_) 为空区间，任何解引用都没有有效对象支撑。
block 的最小判断顺序是：申请阶段只获得原始存储；构造成功后槽进入有效对象生命周期；析构后槽回到原始存储；整块没有有效对象且不再作为边界缓冲时，才能释放 block。这个顺序让 mini_deque 不需要在每个槽上额外保存“是否构造”的标记，因为 [begin_, end_) 已经完整描述了有效元素范围。
52.3 iterator
deque iterator 的核心状态是一组位置描述。一个普通指针只能在一段连续数组中自增自减；deque 的逻辑序列跨越多个 block，iterator 必须知道当前元素地址、当前 block 的首尾边界，以及当前 block 在控制数组中的位置。
本章的 iterator 保存四个字段：cur 指向当前槽；first 指向当前 block 的第一格；last 指向当前 block 的末尾后一格；node 指向 map_ 中保存当前 block 指针的控制槽。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++ 的边界处理说明了 iterator 为什么需要 block 边界。当前元素位于 block 中间时，自增只是 ++cur。当前元素是 block 最后一格时，++cur 会到达 last，iterator 需要切到下一个控制槽，并把 cur 放到下一个 block 的第一格。operator-- 是对称动作：如果当前 cur 已在 block 第一格，先切到前一个 block 的末尾后一格，再回退到最后一个元素槽。
end_ 也使用同一套 iterator 状态。它指向末尾后一格，因此可能位于某个 block 中间，也可能位于一个新 block 的起始位置。push_back 构造元素时通常使用 end_.cur 作为目标槽；构造成功后再推进 end_。pop_back 销毁末尾元素时要先从 end_ 回退到最后一个有效元素，再 destroy 该槽。
随机访问 iterator 还需要 operator+= 和两个 iterator 的距离计算。跨 block 跳转的关键是把当前位置转成“相对当前 block 起点的偏移”，再用整除定位目标 block，用余数定位 block 内槽。负数偏移需要向下取整，C++ 整数除法默认向零截断，所以教学代码里要显式处理负值。
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;
}
这个实现暴露了 deque 随机访问的真正成本：一次跳转需要计算目标控制槽和块内位置，然后通过 node 找到目标 block。复杂度仍是常数，因为计算量不随元素数量增长；常数因子来自除法、余数和二级寻址。工程判断上，热路径大量连续下标访问通常优先考虑 vector；两端增长和随机访问同时存在时，deque 才具有结构优势。
52.4 push_front
push_front 要在当前第一个元素之前构造新元素，并把 begin_ 指向新元素。它的提交顺序需要保护两个状态：已有元素保持原地址，构造失败时用户可见序列保持原样。标准接口层面，deque::push_front 具有常数复杂度，并且元素引用不因两端插入失效；这个行为可以从 push_front 说明 中看到。
在块内仍有前置空槽时，push_front 的路径最短。目标位置是 begin_.cur - 1。实现先在这个槽上构造元素，构造成功后再提交 begin_.cur = begin_.cur - 1，最后增加 size_。如果构造函数抛出异常，begin_ 没有改变，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 时，前端 block 已经没有前置空槽。慢路径要先确认控制数组前方有控制槽；如果 begin_.node == map_，需要扩展控制数组并把已有 block 指针搬到新控制数组中间。扩展控制数组只搬 block 指针，不搬元素对象。接着申请一个新 block，把它写入 *(begin_.node - 1)，在新 block 的最后一格构造元素，构造成功后才把 begin_ 切到新 block。
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。在提交之前，新 block 和新对象只属于准备状态；构造失败时，代码销毁准备阶段产生的资源，并把控制槽恢复为空。构造成功后，新元素进入 [begin_, end_)，容器大小加一。
把贯穿例子代入这条路径可以看到两种情况。空容器初始化后，push_back(10) 和 push_back(20) 可能让 begin_ 仍位于 block 中部；这时 push_front(5) 直接使用块内前置空槽。若前面已经连续执行多次 push_front，begin_ 到达 first，下一次 push_front 才进入慢路径并申请前一个 block。
push_front 的工程结论是：两端增长的常数复杂度来自“按块申请”和“只更新边界 iterator”。它不需要移动已有元素；它可能分配新 block，也可能扩展控制数组；一旦控制数组扩展，旧 iterator 中保存的 node 地址失效。元素引用稳定性和 iterator 稳定性要分开判断，这也是阅读真实 deque 源码时最容易混在一起的边界。
52.5 push_back
push_back 要在 end_ 指向的末尾后一格构造新元素，并把 end_ 推进到新的末尾后一格。它和 push_front 对称，但 end iterator 的“后一格”语义让边界处理略有差异。标准接口层面，deque::push_back 也是常数复杂度；插入会使 iterator 失效，但不会使已有元素引用失效，具体接口边界可见 push_back 说明。
当 end_.cur != end_.last 时，尾端当前 block 仍有空槽。实现直接在 end_.cur 构造元素，然后推进 end_.cur。构造成功前不改变 end，是为了让异常路径保持旧区间 [begin_, 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);
}
当前 end_.cur == end_.last 时，尾端 block 已满，慢路径需要准备后一个 block。实现先确认 end_.node + 1 在控制数组范围内；空间不足时扩展 map_。然后申请新 block，把新 block 指针写入后一个控制槽，在新 block 第一格构造元素。构造成功后，end_ 切换到新 block，并指向第一格之后的位置。
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_;
}
这段代码中，新 block 的第一格构造完成后，end_ 才切换过去。这个顺序让最后一个有效元素的位置始终可解释：慢路径提交前，旧 end_ 仍指向旧 block 末尾后一格；提交后，新 end_ 指向新 block 的第二格，新 block 第一格成为序列末尾元素。
贯穿例子里的 push_back(10)、push_back(20) 和 push_back(30) 通常都走快路径。若 BLOCK_SIZE = 4 且初始位置在中间，连续两次尾部插入可能填满后半块；第三次尾部插入就会进入慢路径，分配后一个 block。这个行为是 deque 的典型形状：容器长度增长时，只有边界 block 发生变化，中间 block 指针保持稳定。
异常安全上，push_back 的风险点有三个：控制数组扩展、block 分配和元素构造。控制数组扩展失败时，旧结构仍由旧 map_ 表示；block 分配失败时，还没有写入新元素；元素构造失败时，释放新 block 并清空控制槽。实现只在所有准备步骤成功后推进 end_ 和 size_，这样用户可见的序列状态保持可回滚。
52.6 pop_front
pop_front 销毁第一个元素，并把 begin_ 推进到下一个元素。它的前置条件是容器非空；对空容器调用 pop_front 在 C++26 之前属于未定义行为，C++26 hardened implementation 语境中可能触发 contract violation。标准接口层面还要求该操作为常数复杂度，擦除的元素对应 iterator 和 reference 失效，其余元素不受影响，这些边界可见 pop_front 说明。
快路径发生在前端元素后面仍位于同一个 block 内。实现先 destroy begin_.cur 指向的有效对象，再推进 begin_.cur，最后减少 size_。析构函数按标准库容器要求通常不应抛出；一旦析构抛出，容器很难恢复稳定状态，工程代码会把元素类型的析构异常作为严重设计问题处理。
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;
}
}
这段代码把销毁前的 old_first、old_last 和 old_node 缓存下来，因为推进 begin_ 后，iterator 的 first/last/node 可能已经指向下一个 block。最后一个元素被销毁后，容器的有效范围为空；把 begin_ 设置为 end_ 可以恢复空区间不变量。教学实现可以保留当前 block 供后续增长使用；如果实现选择释放到零 block，则下一次 push 需要重新初始化第一个 block。
释放前端 block 的条件要精确。销毁元素后，如果旧元素所在 block 已经没有任何有效元素，并且序列剩余元素位于后续 block，才释放旧 block。判断上可以利用销毁前的位置：若 old + 1 == old_last，并且推进后的 begin_.node 已经离开 old_node，旧 block 成为空块，可以释放并清空对应控制槽。
写 pop_front 时最稳妥的判断顺序是：确认非空，缓存旧 block 边界，销毁当前元素，计算新 begin，减少 size，按旧 block 是否成为空块决定是否释放。
贯穿例子执行到 pop_front() 时，序列从 [5, 10, 20, 30] 变成 [10, 20, 30]。如果 5 位于前端 block 的中间，begin_ 只需向后移动一格；如果 5 位于某个前端 block 的最后一格，begin_ 会跨到下一个 block 的第一格，并且旧 block 可以释放。两个路径对外都只表现为第一个元素被移除，复杂度仍是常数。
52.7 pop_back
pop_back 销毁最后一个元素，并把 end_ 回退到新的末尾后一格。它的前置条件同样是容器非空；标准接口层面，空容器调用 pop_back 在 C++26 之前属于未定义行为，C++26 hardened implementation 可能触发 contract violation。pop_back 使被删除元素的 iterator 和 reference 失效，并使 end() iterator 失效；常数复杂度边界可见 pop_back 说明。
由于 end_ 指向末尾后一格，pop_back 的第一步是定位最后一个有效元素。若 end_.cur != end_.first，最后一个元素就在同一 block 的 end_.cur - 1。实现先回退 end_.cur，再 destroy 回退后的位置。
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();
}
慢路径发生在 end_.cur == end_.first 时。此时 end_ 位于某个 block 的起始位置，最后一个有效元素在前一个 block 的最后一格。实现需要先记录当前空尾 block，切回前一个 block，销毁前一个 block 的最后元素，然后根据空尾 block 是否仍需要作为缓冲决定释放。
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_ 预先分配空 block，则 empty_tail_block 可能为空，释放分支自然跳过。不同教学实现在“是否提前准备尾端空 block”上可以选择不同策略，只要维护 [begin_, end_) 和 block 生命周期不变量即可。
pop_back 的常见错误是直接 destroy end_.cur。end_.cur 是末尾后一格，通常没有有效对象。正确路径必须先回退，再析构。这个动作和 push_back 正好互补：push 在 end_.cur 构造后推进 end；pop 回退 end 后析构当前位置。
在贯穿例子里，int x = d[1] 之前没有执行 pop_back，所以末尾元素仍是 30。如果随后执行 pop_back()，最后一个有效元素 30 被销毁，end_ 回到 20 之后的位置。若 30 是某个尾端 block 的唯一元素，旧尾端 block 可以释放；若它和 20 位于同一 block，end_.cur 只回退一格。
52.8 random access
deque 的随机访问要把逻辑下标转换成两个坐标：目标 block 编号和 block 内偏移。这个转换是 deque 能同时保持分段存储和常数时间下标访问的核心。标准接口层面，operator[] 返回指定位置的引用，复杂度为常数；越界访问在普通语义下没有定义行为保障，C++26 hardened implementation 增加了 contract violation 的实现空间，具体边界可见 operator[] 说明。
最小实现可以从 begin_ 出发计算第 index 个元素。先取 begin_ 在当前 block 内的偏移 begin_.cur - begin_.first，再加上 index 得到从 begin block 起点算起的总偏移。总偏移除以 BLOCK_SIZE 得到目标控制槽偏移，取余得到目标 block 内位置。
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];
}
这段代码解释了 d[1] 的定位过程。贯穿例子执行到 pop_front() 后，逻辑序列是 [10, 20, 30]。若 begin_ 指向某个 block 的第 2 格，访问 d[1] 时 begin_offset + 1 指向同一 block 的第 3 格，返回 20。若 begin_ 已经接近 block 尾部，total / BLOCK_SIZE 会跨到后一个控制槽，total % BLOCK_SIZE 给出新 block 内的位置。
随机访问 iterator 的 operator+ 和容器的 operator[] 本质上使用同一个公式。差别只在输入来源：operator[] 从容器的 begin_ 和下标出发，iterator 跳转从当前 iterator 和距离出发。二者都依赖 map_ 的控制槽连续可寻址，以及每个 block 的大小固定。如果 block 大小不固定，常数时间下标访问就需要额外索引或前缀长度结构，简单除法取余不再成立。
下标访问的边界有三类。第一，index < size_ 是调用前提；operator[] 不做边界检查，调试实现可以用断言辅助。第二，返回的是元素引用，元素生命周期必须位于 [begin_, end_) 内。第三，控制数组扩展后，旧 iterator 可能失效，但元素引用通常仍指向原 block 中的对象。写代码时应把“下标重新计算”和“保留 iterator 继续使用”区分为两个风险点。
到这里，mini_deque 的完整判断顺序已经形成：先用 map_ 判断块序列，使用 block 判断局部连续存储，通过 iterator 维护边界状态；两端修改先准备控制槽和 block，再构造或析构元素，最后提交 begin_ / end_；随机访问用 begin 的块内偏移加下标，拆成控制槽偏移和块内偏移。这个顺序可以迁移到真实 std::deque 源码阅读中，只需把教学常量 BLOCK_SIZE 替换成实现选择的 block sizing 策略。
最小自检任务
给定一个教学 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。同时说明旧 iterator 和元素引用在两端插入时应如何分别判断。
答案要点
在给定初始布局中，push_back(10) 在第 2 格构造，end_ 前进到第 3 格；push_back(20) 在第 3 格构造，end_ 到达当前 block 的 last。push_front(5) 使用第 1 格，begin_ 回退到第 1 格。push_back(30) 此时尾端 block 没有后置空槽，需要准备后一个控制槽和新 block，在新 block 第一格构造 30，再把 end_ 指向新 block 第二格。
pop_front() 销毁第 1 格的 5，然后把 begin_ 推进到第 2 格，此时逻辑序列变成 [10, 20, 30]。访问 d[1] 时，计算 begin_offset + 1，再用除以 BLOCK_SIZE 得到目标控制槽，用取余得到 block 内偏移；这个计算步骤数量固定，因此是常数时间。若两端插入触发控制数组扩展，保存旧控制槽地址的 iterator 会失效；已有元素对象仍在原 block 中，指向这些元素的引用通常保持有效。
本章知识点总结
- 控制数组：
map_保存 block 指针，负责把逻辑块编号映射到实际缓冲块。 - 分段存储：
deque用多个固定大小 block 表达逻辑连续序列，块内连续，块间通过控制数组连接。 - 半开范围：
begin_指向第一个有效元素，end_指向末尾后一格，已构造元素只存在于[begin_, end_)。 - 原始存储：block 分配只获得存储，元素必须通过 allocator construct 进入有效生命周期。
- 前端插入：
push_front优先使用前端 block 空槽，空间不足时准备前一个控制槽和新 block。 - 尾端插入：
push_back在end_.cur构造元素，成功后推进end_。 - 前端弹出：
pop_front先销毁begin_.cur，再推进begin_，旧 block 空闲时可以释放。 - 尾端弹出：
pop_back先从end_回退到最后一个有效元素，再销毁该元素。 - Iterator 状态：
dequeiterator 需要保存cur、first、last和node，才能跨 block 移动。 - 随机访问：下标访问通过
begin块内偏移加下标，拆成控制槽偏移和块内偏移。 - 引用稳定：两端插入通常不移动已有元素，已有元素引用可保持指向原对象。
- Iterator 失效：控制数组扩展会改变控制槽地址，保存旧
node的 iterator 会失效。 - 异常提交：push 慢路径应先准备控制槽、block 和元素构造，成功后再提交边界 iterator。
- 选型判断：需要两端增长和随机访问时，分段数组结构具备优势；大量连续热访问时，
vector的单段连续存储常数因子更低。