Skip to main content

Chapter 52: Mini Deque

核心问题与阅读主线

本章导读8 个核心小节 · 附自检与总结

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 原始存储槽承载块内连续对象;边界块满时按需申请新块
iteratorcur、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,按三步准备新前端块后再提交边界:

  1. 检查或扩展 map_:调用 reserve_map_at_front();若 begin_.node == map_,分配更大 map_ 并居中搬移 block 指针(不移动元素)。
  2. 分配并挂载新块:申请 new_block 写入 *(begin_.node - 1),定位目标槽 new_block + (BLOCK_SIZE - 1)。
  3. 构造后提交:在目标槽构造元素,成功后才更新 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_frontpush_back
快路径判定begin_.cur != begin_.firstend_.cur != end_.last
构造目标槽begin_.cur - 1end_.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_frontpop_back
执行顺序先缓存旧块边界并 destroy(begin_.cur),再 ++begin_先从 end_ 回退到末元素,再 destroy(end_.cur)
跨块判定old + 1 == old_last && begin_.node != old_nodeend_.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 即失效。