Skip to main content

Chapter 12: Deque

核心问题与阅读主线

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

工程中常遇到一对双向需求:既要像 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 暴露连续视图。

排查顺序

  1. 看位置:操作发生在头尾端点还是序列中段?
  2. 看端点 block:对应端点 block 是否尚有未构造的空槽?
  3. 看控制数组:map 对应方向是否还有空槽,是否会引发 map 扩展重排?
  4. 看提交点:元素构造/析构是否成功,边界是否已提交,异常回滚是否干净?
  5. 套失效规则:分别核对元素引用与 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 稳定性。
维度vectordequelist
物理存储单段连续多 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 的四个核心支点:

  1. 保存当前绝对偏移,或保存当前元素指针与所在 block_slot。
  2. ++it 在 block 内递增指针,越过块尾时切换到下一 block。
  3. it + n 按 BlockSize 换算目标控制槽位与块内偏移。
  4. 两 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 状态与成本

    deque iterator 持有当前元素、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。