Chapter 12: Deque

std::deque 解决的是一个具体容器矛盾：序列需要支持下标访问，同时又需要在头尾两端稳定增长。std::vector 把元素放在一整段连续内存里，随机访问路径最短；代价是头部插入需要搬动大量元素，尾部扩容也可能迁移全部元素。std::list 通过节点链接获得局部插入能力；代价是随机访问退化成遍历，并且每个节点都有额外指针和独立分配成本。std::deque 站在两者之间，用分段连续内存维持随机访问和两端增长。

本章围绕一个贯穿材料展开：把 std::deque<int> q 看成由多个固定大小 block 组成的序列，外层有一个控制数组记录每个 block 的地址，begin 和 end 指向当前有效区间的两端。读完本章，应能根据一次 push_front、push_back、pop_front、pop_back、下标访问或迭代器保存行为，判断它会修改哪一层状态、是否分配内存、会使哪些位置对象失效，以及它相对 vector、list 的工程取舍。

标准层面只规定 deque 是支持随机访问迭代器的 sequence container，支持头尾常数时间插入和删除，中间插入删除为线性时间；存储管理由容器自动完成。这个语义可以在 C++ working draft 的 deque overview 中定位。常见实现形状通常使用“控制数组 + 多个固定大小缓冲块”，这一点在 cppreference 的 std::deque 页面也以典型实现方式描述。正文会把标准语义和常见实现分开：标准承诺决定可移植代码能依赖什么，常见实现形状帮助解释这些承诺通常怎样落到对象、内存和 iterator 上。

本章的判断顺序先固定四层对象：容器对象保存边界状态，控制数组保存 block 指针，block 保存元素存储，iterator 保存当前位置和 block 边界。随后看操作发生在头尾还是中间，再看是否需要新 block 或控制数组重排，最后判断元素引用、iterator、复杂度和局部性。

12.1 双端队列语义与分段连续内存

std::deque 的接口语义是“可下标访问的双端序列”。它支持 front()、back()、operator[]、at()、push_front()、push_back()、pop_front() 和 pop_back()，所以调用者看到的是一个从第 0 个元素到第 size() - 1 个元素的线性序列。线性序列这个抽象保持稳定，底层存储却分成多个小段。

分段连续内存的工作定义是：每个 block 内部连续，block 与 block 之间地址可以分散，容器额外维护从逻辑下标到 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。调用者通过 q[1] 访问到 10，说明 deque 提供随机访问接口；调用者通过 push_front(5) 在头部增加元素，说明它把头端增长纳入主能力。这个现象背后的关键点是：deque 维持的是逻辑连续序列，物理地址只在每个 block 内部连续。

可以把当前贯穿材料想成下面的结构。图中 map 是 deque 常见实现里的控制数组名称，含义是 block 指针表，与有序关联容器 std::map 无关。

图里的 deque object 本身通常只保存少量状态，例如控制数组地址、控制数组大小、起始 iterator、结束 iterator 和 allocator 相关状态。元素对象位于 block 中。begin 指向第一个有效元素，end 指向最后一个有效元素之后的位置。序列的逻辑长度来自 begin 到 end 的距离，物理存储由多个 block 拼接出来。

这一结构解释了 deque 的三条主要语义。第一，头尾插入删除可以常数时间完成，因为端点附近通常只改一个元素槽和一个边界 iterator；端点 block 用完时只接入一个新 block。第二，随机访问仍是常数时间，因为下标可以被换算成 block 编号和 block 内偏移。第三，中间插入删除需要移动更靠近一端的那部分元素，复杂度和移动元素数量相关。

使用 deque 时应先判断需求是否同时包含“两端增长”和“按下标访问”。只需要尾部增长和高密度线性扫描时，vector 的连续内存通常更直接。只需要稳定节点位置和局部重连时，list 的节点结构更匹配。需要把新元素频繁放到队首和队尾，同时还要访问 q[i] 时，deque 的结构开始成立。

12.2 map 控制结构、block / buffer 与 iterator 状态

常见 deque 实现由三种状态共同支撑：控制数组、block、iterator。控制数组保存 block 指针，block 提供一段元素存储，iterator 把当前位置、当前 block 边界和控制数组槽位连起来。读源码时看到 _M_map、__map_、_Map、_M_node、__block_size 这类内部命名，应把它们还原到这三种角色上。

控制数组负责把“逻辑上相邻的 block”组织起来。它自己也是一段动态分配的数组，数组里的每个元素是指向某个 block 的指针。deque 在头部增长时需要在控制数组的前侧拥有可用槽位，在尾部增长时需要在后侧拥有可用槽位。控制数组槽位不足时，容器会分配更大的控制数组，并把现有 block 指针复制到新控制数组的中间区域，为两端继续增长留下空间。

block 或 buffer 负责保存真正的元素存储。block 大小是实现策略，通常根据元素类型大小选择一个元素个数。小对象可能让一个 block 容纳较多元素，大对象可能让一个 block 只容纳少量元素。标准没有规定 block 大小，因此源码阅读时不能把某个实现的 block 容量当成通用语义。

iterator 的状态比 vector iterator 更重。vector 的 iterator 可以近似理解为一个元素指针；deque iterator 通常需要知道当前元素指针、当前 block 的起始地址、当前 block 的结束地址，以及控制数组中当前 block 指针所在的位置。这样，++it 在 block 内部只移动当前元素指针，到达 block 末尾时再切换到下一个 block。

下面的简化结构表达了这种 iterator 状态。它不是任何标准库的真实源码，只用于固定阅读模型：

template <class T>
struct deque_iterator_shape {
    T* current;       // 当前元素位置
    T* block_begin;   // 当前 block 起点
    T* block_end;     // 当前 block 终点后一位
    T** block_slot;   // 控制数组中当前 block 指针的位置
};

这个结构能解释 deque iterator 的两个成本来源。普通自增在 block 内只改 current；跨 block 自增需要读 block_slot + 1，再刷新 block_begin、block_end 和 current。随机跳转 it + n 需要把当前 block 内偏移和 n 合并，计算目标 block 槽位与目标 block 内偏移。它仍然是常数时间，但比单个指针加法多几步算术和一次控制数组间接访问。

deque 的 end() 也值得单独看。end() 指向最后一个有效元素之后的位置，这个位置可能位于尾端 block 的空槽，也可能正好位于下一个 block 的起点。端点操作经常改变这个过去末尾位置，所以保存 end() 后再执行 push_back、push_front、pop_back、pop_front，需要重新获取 end() 来做后续判断。

源码阅读时，先把内部字段归入这张表，再继续读具体函数，会比逐行记内部变量名更稳定。

内部角色	保存内容	直接服务的操作	工程后果
容器对象	控制数组、起止 iterator、大小相关状态、allocator	所有成员函数入口	小对象本身不保存元素数组
控制数组	block 指针序列	两端扩展、随机访问定位	扩展控制数组会影响 iterator 状态
block / buffer	若干个元素槽位	构造、析构、局部遍历	block 内局部性好，跨 block 有间接访问
iterator	当前元素、block 边界、block 槽位	遍历、下标跳转、距离计算	比裸指针更重，失效规则也更细

这张表也给出本章的第一个可迁移判断：看 deque 操作时，先问它只改变端点元素槽，还是还要改变 block 指针表。只改变端点元素槽时，元素引用通常稳定；控制数组扩展或中间移动发生时，iterator 稳定性需要按标准规则重新判断。

12.3 push_front、push_back、pop_front 与 pop_back

两端操作是 deque 的核心路径。它们把容器修改限制在逻辑序列的开头或末尾，通常不搬动已有元素。为了看清对象状态，可以把每次操作拆成三层：是否有可用槽位，是否需要分配或释放 block，最后如何更新 begin 或 end。

push_back(x) 的普通路径最短。尾端 block 还有空槽时，容器在 end 所指的位置用 allocator 构造一个新元素，然后把 end 推进一位。已有元素对象的地址和引用保持有效，因为它们所在 block 没有被搬迁。标准承诺中，端点插入会使 deque 的 iterator 失效，但不会影响已有元素引用的有效性。

当尾端 block 没有空槽时，push_back(x) 进入扩展路径。容器先保证控制数组尾侧有可用槽位；如果控制数组也满了，就分配更大的控制数组并复制 block 指针。随后容器分配新的 block，把新 block 指针写入控制数组尾侧槽位，再在新 block 的第一个槽位构造元素，最后更新 end。这个路径仍然不需要把已有元素对象搬到新地址，所以它比 vector 尾部扩容少了“迁移全部元素”这一步。

push_front(x) 与 push_back(x) 对称。头端 block 前方还有空槽时，容器先把 begin 回退一位，再在新的 begin 位置构造元素。头端 block 没有空槽时，容器在控制数组前侧接入新 block，把 begin 切换到新 block 的最后一个可用槽位，再构造元素。这里的顺序要保证异常路径可恢复：分配和构造成功之前，旧序列边界不能被提交成新状态。

下面的简化伪代码展示 push_back 的提交点。它省略了 allocator traits、异常处理、block 大小策略和控制数组增长细节，只保留状态改变顺序：

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);
}

这段伪代码要证明的点是：deque 的尾部增长把“给元素找存储”和“提交新边界”分开。分配新 block 与写控制数组属于存储准备，构造元素属于对象生命周期开始，更新 end 属于容器状态提交。读真实源码时，异常安全相关 guard、临时 block 指针和提交函数通常围绕这三个动作出现。

pop_back() 的状态路径反过来。容器定位最后一个有效元素，调用析构函数结束它的生命周期，然后把 end 回退一位。如果尾端 block 在删除后变成空 block，实现可以释放这个 block 或保留它作为后续增长缓存；标准语义只要求元素数量和序列状态正确。pop_front() 同理，销毁第一个有效元素，推进 begin，在端点 block 变空时处理 block 资源。

端点删除的失效规则要按“被删除元素”和“过去末尾位置”分开判断。被删除元素的 iterator 和引用失效，这是对象生命周期结束的直接结果。非删除元素的引用在端点删除后保持有效。end() 属于边界位置，pop_back() 改变最后元素之后的位置，pop_front() 在某些情况下也会影响实现中的过去末尾 iterator，因此工程代码应把端点删除后的 begin()、end() 都当作需要重新获取的位置。

下面的代码展示一个安全的循环形状。每次修改后重新读取端点，不保存跨修改的 iterator：

#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);
        }
    }
}

这段代码里没有把旧 begin() 或旧 end() 留到修改之后使用。front_value 是按值保存的元素内容，pop_front() 之后它与 deque 内部对象没有引用关系。若把 auto it = q.begin(); 放在循环外，再在 push_back 或 pop_front 后继续用旧 it，代码就把 iterator 稳定性建立在错误前提上。

12.4 扩容方式、allocator 参与与 O(1) 随机访问

deque 的扩容方式以 block 为单位。vector 扩容需要申请一整段更大的连续内存，然后把已有元素迁移过去；deque 增长时通常只申请一个新 block，再把 block 指针接入控制数组。控制数组自身扩展时也只复制 block 指针，已有元素对象仍留在原 block 中。

allocator 在这个路径里承担两类责任。第一类是为元素存储申请和释放原始内存，常见实现会通过 allocator 或 rebound allocator 获取 block 存储。第二类是通过 allocator_traits 构造和销毁元素对象。控制数组本身的指针存储也需要内存管理，但它服务实现结构，和元素生命周期要分开看。

这种分离让异常安全路径更清楚。一次端点插入可能经历控制数组扩展、block 分配、元素构造和边界提交。若控制数组扩展失败，旧 deque 没有变化。若 block 分配失败，旧 deque 没有变化。若单个端点元素构造失败，标准要求这次单元素端点插入没有效果。只有元素构造成功并且边界提交完成后，size() 和端点访问才反映新元素。

随机访问的常数时间来自固定公式。假设 block 容量是 block_size，逻辑序列从某个 start_offset 开始，访问下标 i 时可以计算总偏移 start_offset + i，再得到 block 编号和 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];

这个代码形状解释了 deque 的 operator[]。它进行常数次整数运算和常数次间接访问，所以复杂度是 O(1)。同样是 O(1)，它和 vector 的 *(data + i) 仍有差异：vector 只需要一段连续内存上的指针偏移，deque 需要先定位 block 指针，再进入 block 内部定位元素。复杂度符号表达增长阶，热路径性能还会受到指令数量、分支、cache 命中和预取效果影响。

deque 没有 reserve()，这也是扩容模型的直接后果。vector::reserve(n) 可以提前准备一整段能容纳 n 个元素的连续内存；deque 的存储分散在多个 block 中，标准接口没有暴露“预留多少 block”或“控制数组容量”这样的能力。调用者能控制的是操作模式，例如把频繁的头尾修改留给 deque，把需要连续 buffer 的接口留给 vector、array 或 span。

下面的判断顺序可以用于扩容相关问题：先看操作是否在头尾；再看端点 block 是否有空槽；再看控制数组对应方向是否有空槽；随后判断是否构造新元素或销毁旧元素；最后把 iterator 和引用失效规则按标准语义套回去。这个顺序把实现形状和可移植语义连接起来，能防止把“已有元素没有搬迁”误推成“iterator 一定可继续使用”。

12.5 iterator 失效、cache locality 与容器对比

deque 的 iterator 失效规则需要单独记。端点插入会使所有 iterator 失效，但已有元素引用保持有效。端点删除会使被删除元素的位置对象失效，并且过去末尾 iterator 需要重新获取。中间插入和中间删除会使更多位置对象失效，因为实现需要移动元素并调整分段边界。工程代码保存 deque 的 iterator 跨修改使用时，应先查对应操作的失效规则，再决定是否重新定位。

引用和 iterator 的差异来自它们保存的信息不同。元素引用直接指向某个元素对象，只要这个元素对象仍在原 block 中且生命周期没有结束，引用就能继续指代它。iterator 还保存了 block 边界和控制数组槽位；控制数组扩展、边界变化或中间移动会让这些辅助状态过期。把引用稳定性推导成 iterator 稳定性，是 deque 使用中常见的错误来源。

下面的例子展示这种差异。它表达的是规则形状，不要求输出某个实现的内部地址：

#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 没有可移植保证
}

这段代码要证明的点是：push_front 后，原来的元素 2 没有因为头部增长而被迁移成另一个对象，所以 ref 的目标仍有效；旧 iterator 保存的控制结构状态已经不能继续依赖。实际工程里更稳的写法是保存索引或重新查找位置，例如修改后重新计算 q.begin() + new_index。

cache locality 也要按层次判断。deque 的 block 内部连续，顺序访问同一 block 中的相邻元素通常有较好局部性。跨 block 时，需要先经控制数组找到下一个 block，硬件预取的效果通常弱于 vector 的整段连续扫描。若程序的热点路径是大规模线性遍历、排序、二分、向 SIMD 或 C 接口传递连续 buffer，vector 的布局更合适。

和 list 对比时，deque 的优势在于随机访问和较少的每元素指针开销。list 每个节点都携带链接指针，元素地址分散，顺序遍历需要沿指针跳转；它的强项是节点级插入删除和 iterator 稳定性。deque 的中间插入删除仍会移动元素，局部修改能力达不到 list 的节点重连模型。

这张表使用同一组维度比较 vector、deque 和 list：

维度	vector	deque	list
物理存储	单段连续	多 block 分段连续	独立节点
随机访问	O(1)，路径最短	O(1)，多一次分段定位	无下标随机访问
头部插入删除	线性移动	常数时间端点操作	常数时间节点操作
尾部插入删除	摊还常数，扩容会迁移元素	常数时间端点操作	常数时间节点操作
中间插入删除	线性移动	线性移动，通常选择较近端	常数时间重连已定位节点
iterator 稳定性	扩容和移动影响大	端点插入使 iterator 失效，引用较稳定	插入通常稳定，删除影响被删节点
cache locality	最好	block 内较好，跨 block 较弱	通常较弱
典型用途	连续数据、热遍历、排序	双端队列、滑动窗口、队列底层	稳定节点、频繁 splice

从这张表可以得到容器选型的顺序：先看是否要求连续内存；再看修改主要发生在尾部、两端还是中间；随后看是否保存 iterator 或引用跨修改；最后看热点操作是遍历、随机访问、局部插入还是节点转移。deque 的位置在“两端修改 + 下标访问 + 不要求连续 buffer”这一块。

12.6 deque 复杂度来源与 mini deque 实现

deque 的复杂度来自两层数组的组合。外层控制数组让 block 可以按逻辑顺序排列，内层 block 让一段元素保持连续。头尾操作通常只接触一个端点 block 和一个边界 iterator，所以是常数时间。随机访问通过除法、取模和两次寻址完成，所以也是常数时间。中间插入删除需要移动靠近一端的元素，移动数量随位置变化，所以是线性时间。

实现 mini deque 时，目标应收窄到四个部件：控制数组、固定大小 block、iterator、端点操作。完整标准库还要处理 allocator traits、异常安全、拷贝移动构造、范围插入、比较、shrink_to_fit、C++23 range 接口和大量边界条件。教学实现先固定 block 大小，完成对象状态和边界更新，就能验证本章主问题。

下面的简化代码只表达 mini deque 的存储布局。为了让代码短，它使用 std::vector<T*> 保存 block 指针；真实标准库实现通常会自己管理控制数组，以便更精确地控制两端预留和 iterator 失效。这个简化不会改变本节要证明的对象关系：控制数组保存 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 存在，再在目标槽位构造对象，最后增加 size_。operator[] 把逻辑下标转换成绝对偏移，再拆成 block 下标和 block 内偏移。它没有展示 push_front，原因是前端增长需要在控制数组前侧预留空间；教学实现可以通过给 first_ 一个中间起点，或通过环形控制数组来完成。

一个更接近 deque 的 mini 实现会把 first_ 放在控制数组中间，让头尾都能增长。初始化时先分配若干个控制槽位，把第一个 block 放到中间位置，begin 和 end 指向同一个槽位内的同一个偏移。push_front 发现 begin 位于 block 起点时，就向前找一个控制槽位，分配前置 block，把 begin 切到新 block 的末尾。push_back 则在尾侧执行对称操作。

mini iterator 的检查点有四个。第一，iterator 保存当前绝对位置或保存当前元素指针加 block 槽位。第二，++it 在 block 内推进，越过 block 尾部时切换到下一个 block。第三，it + n 使用 block 大小计算目标槽位和偏移。第四，两个 iterator 的距离由绝对偏移差得到，或由 block 槽位差和 block 内偏移组合得到。只要这四点成立，random access iterator 的核心路径就能搭起来。

mini deque 的验收顺序应从状态不变量开始。空容器的 size() 为 0，begin 与 end 表示同一位置；每个有效元素所在 block 已分配，并且对象生命周期已经开始；每个无效槽位只是原始存储，析构时不能调用元素析构函数；push_front、push_back 只在构造成功后提交边界；pop_front、pop_back 先销毁元素，再移动边界；析构函数只销毁有效区间内的对象，并释放所有已分配 block。

最终可以把 deque 的源码阅读压缩成一句判断：它用控制数组管理 block，用 block 承载局部连续元素，用 iterator 保存跨 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';
}

答案要点

ref 仍然可以使用，它指向原来的元素 20。端点插入不会影响已有元素引用的有效性，因为常见实现只在头端接入新槽位或新 block，已有元素对象没有被搬到新地址。

旧 it 在 push_front 后不能继续作为可移植位置使用。端点插入会使 deque 的 iterator 失效，原因是 iterator 保存了元素地址、block 边界和控制数组槽位等定位状态。修改后需要重新获取 iterator，例如重新计算 q.begin() + 2。

q[2] 是 O(1)，因为 deque 可以把逻辑下标加上起始偏移，再用 block 大小计算 block 编号和 block 内偏移。这个过程是固定次数的算术和间接访问。它的常数成本高于 vector 的单段指针偏移，但复杂度阶仍是常数。

本章知识点总结

• 双端语义：deque 表达的是支持头尾增长和下标访问的线性序列。
• 分段连续：deque 的元素在 block 内连续，block 之间可以分散分配。
• 控制数组：常见实现用控制数组保存 block 指针，并通过两端槽位支撑扩展。
• block 角色：block 提供元素原始存储，元素构造成功后才进入有效生命周期。
• iterator 状态：deque iterator 通常保存当前元素、block 边界和控制数组槽位。
• 头尾插入：端点插入通常只构造一个新元素并更新边界，必要时接入新 block。
• 头尾删除：端点删除先销毁被删元素，再推进或回退边界。
• 引用稳定：端点插入不会影响已有元素引用的有效性，但会使 iterator 失效。
• 随机访问：operator[] 通过 block 编号和 block 内偏移完成常数时间定位。
• 扩容差异：deque 扩容通常增加 block，vector 扩容通常迁移整段元素。
• 局部性边界：deque 在 block 内有局部性，跨 block 访问弱于 vector 的连续扫描。
• 容器选型：需要两端修改、下标访问且不要求连续 buffer 时，deque 是合适候选。
• mini 实现：最小 deque 应先实现控制数组、block、iterator 和端点边界操作。