侯捷 STL：deque 的跨段迭代器，怎样托起 queue 与 stack

上一篇的 vector在空间不够时换一块更大的缓冲区。若既希望尾端增长，也希望前端增长，还希望通过下标直接访问元素，该怎样组织存储？侯捷在 P18–19 先画 deque 的分段结构，再把移动迭代器的过程逐步翻译成代码。最后的 queue 和 stack 则反过来做减法：复用已有存储，只向使用者开放符合特定次序的操作。

先修是前闭后开区间、指针和对象的区别、操作符重载，以及迭代器的相关类型。本文是依据两讲完整音轨转录与关键源码画面整理的 AI 辅助学习笔记，现代契约和独立实验单独说明。阅读位置见 STL 课程目录与侯捷 C++ 课程总导读。

来源档案

讲者：侯捷；原课标题页为**《C++标准库：体系结构与内核分析》**，带 Boolan 博览标识。本文对应 P18《deque、queue和 stack深度探索（上）》、P19《deque、queue和 stack深度探索（下）》。

本次使用 B 站账号 DetachmentSy 上传的《侯捷 - STL标准库和泛型编程》，BV1kBh5zrEYh，当前 46 个分 P；上传版本入口。当前上传属于 2025 年，原课录制年份未核实。课堂 G2.9、G4.9 标签指所讨论的历史实现，不代表今天所有标准库。编号及时间均以本上传版本为准，核对日期 2026-09-12。

把一条序列拆成缓冲区，再用指针表确定次序

课堂从“双向开口的一块空间”示意图转到真实实现图：元素放在多个缓冲区中，每个缓冲区内部连续，缓冲区之间不要求相邻。另一块指针表保存各缓冲区的地址，表项顺序决定这些段在逻辑序列中的次序。

旧源码将这张表称为 map。它与关联容器 std::map 无关。讲者也把它比作可增长的 vector，但课件成员实际是指针表指针与 map_size；不能据这个比喻断言 deque 内部持有一个 std::vector 对象。

尾段放满，可以申请后续缓冲区；前段放满，则可以在前面安排缓冲区。P19 还解释，控制表需要更大空间时，会把已有表项安排到新表的中间附近，为前后继续扩展留下余地。这里搬的是控制表中的地址，不等于把全部元素对象重新搬到一块大数组。

不过，元素没有搬走，也不能推出迭代器仍然有效。迭代器可能依赖控制表中的位置；标准也分别规定元素引用与迭代器的有效性。这个区别要一直保留到后面的代码实验。

四根指针分别回答四个问题

课件中的迭代器包含 cur、first、last、node：

成员	回答的问题
`cur`	当前指向本段哪个元素？
`first`	本缓冲区从哪里开始？
`last`	本缓冲区的尾后位置在哪里？
`node`	控制表中，哪一项指向本缓冲区？

容器还保存 start、finish 两个这样的迭代器，表示有效区间。finish 是尾后位置，所以 back() 要先把其副本减一，再解引用。P19 开头讲者曾口头说成直接取 finish，随后立即纠正；这里应保留纠正后的推导。

first、last 是缓冲区边界，不会在同一段内每走一步就改变；cur 才随着当前位置移动。跨段时，node 选择另一张表项，first、last 随之更新，再确定新的 cur。

这些是所示实现的结构。四根指针、40 字节的容器对象、512 字节附近的默认分段策略，都不是标准 deque 的统一布局承诺。旧代码的 BufSiz 非零时直接指定每段元素数；取零时才选择默认策略：元素小于 512 字节就取 512 / sizeof(T) 个，否则每段取 1 个。零表示“让实现选择”，不是创建零长度缓冲区。第三个 BufSiz 模板参数也不是现代标准接口；现行 deque 模板公开的是元素类型和分配器。C++ 工作草案：deque 概述

为什么递增先走一步，递减却要先看边界

P19 的 ++ 先增加 cur。若它还没到 last，操作就结束；若到达本段尾后位置，则通过 node + 1 换到下一段，把 cur 放到新段开头。

-- 的顺序有所不同。假如当前就在 first，不能先把指针减到这块数组之前，再想办法补救。源码先识别这个情况，切到前一段，把 cur 设为那一段的 last，然后再减一，得到前一段的最后一个元素。

这一点很适合停下来画图：数组尾后指针可以形成，但数组首前指针不能用来作为普通遍历步骤。边界检查的前后顺序不是风格差别，而是与指针运算是否合法有关。

后置 ++/-- 则保存旧迭代器，再调用前置版本完成移动，返回旧值。这样跨段逻辑集中在一处，不必维护两份近似实现。

加十七步，不需要连续走十七次

能 ++ 还不足以说明随机访问。关键是：能否根据偏移直接算出目标段和段内位置？

课堂的 += 先合并“当前段内位置”和“本次移动距离”。如果结果仍在本段，直接调整 cur；否则计算要跨过多少段，更新控制表位置，再定位段内元素。+ 复用 +=，-= 则复用相反方向的偏移，迭代器下标最终也能用“移动后解引用”表达。

用整理者的数值例子看，假设每段有 8 个位置，当前在段内下标 2：

前进 17 步，总偏移为 19，应进入后面第 2 段的下标 3。
后退 3 步，总偏移为 -1，应进入前一段的下标 7。

负数例子特别重要。C++ 整数除法向零截断，不能直接把 -1 / 8 的结果当成“前一段”。实现需要处理负偏移，使段内下标回到 [0, 8)。这只是坐标计算，实际迭代器操作还必须留在允许的序列范围内；算得出一个负段号，不表示可以移动到容器起点之前。

两迭代器相减同理：完整缓冲区的长度，加上两端残余部分。课件示意中，三个完整缓冲区各有 8 个元素，再加头段 3 个、尾段 0 个，距离是 27。不能跨不相邻缓冲区直接对元素指针相减；应使用同一控制表中的表项距离和各段内部的偏移。

所以课程所谓“连续的假象”，准确地说是按序列位置进行随机访问。它不保证物理连续，不能把 &d[0] 当成覆盖整个 deque 的 C 数组首地址。需要连续缓冲区的接口，应选择真正满足该条件的存储。

中间插入，为什么移动较短的一侧

P18 的插入实现先处理两个简单位置：在头部交给 push_front，在尾后位置交给 push_back。其余情况交给辅助函数。

若一万个元素中要靠近开头插入，全部向后移动显然很浪费。因为 deque 两端都能扩展，辅助函数比较插入点到两端的距离，移动较短的一侧，为新元素腾出位置。课件以 index < size() / 2 区分方向，两侧分别涉及 copy 和 copy_backward。

这个例子把数据结构与算法方向联系起来了：两端可扩展，使插入不必总选择同一个搬移方向；但中间插入仍可能需要移动许多元素。现代标准给出的复杂度也包含到两端距离的较小值，并不把任意位置插入都承诺为常数时间。C++ 工作草案：deque 修改操作

这里的“移动”是口语统称。向已有对象写入通常涉及赋值，新位置的对象则需要构造；不能说每移动一个位置都必然析构再构造一次。

作为现代使用边界，还要记住：两端插入使 deque 的所有迭代器失效，但保持既有元素引用有效；中间插入则使迭代器和元素引用都失效。下标代表的是当前位置，也不能当作元素永恒身份。同一标准条款的失效规则

queue 和 stack：通过成员对象，把操作集合缩小

讲完复杂的 deque，后面的两个适配器就很短了。queue 要先进先出，stack 要后进先出；二者保存底层容器成员 c，将公开操作转交给它。

公开操作	queue 的底层操作	stack 的底层操作
加入元素 `push`	`push_back`	`push_back`
查看下一个取出的元素	`front`	`back`，公开名为 `top`
删除下一个取出的元素 `pop`	`pop_front`	`pop_back`

它们没有公开标准迭代器接口，也不提供任意位置插入。这是接口选择，用来表达预期使用方式；并不是说 FIFO 的数学定义禁止任何形式的只读观察。

接口隔离与适配器模式一文已经提过容器适配：它不必通过虚函数实现，也可以是模板加成员对象。这里能看到完整因果链——已有容器承担存储，外层类型转换调用方式，公开接口表达新的行为约束。

默认底层是 deque，也能在满足要求时替换。课堂先用 list 支撑两者，再用 vector 支撑 stack。这几种选择并不神秘，只需逐项核对底层操作：vector 有 back、push_back、pop_back，却没有 pop_front，因此不满足 queue 所需的接口。queue 定义、stack 定义

讲者推测默认 deque 应该更快，同时明确说自己没有做这个实验。整理时不能据默认值保证性能最优；元素大小、工作负载、分配次数和实现都会影响结果。能否适配先看契约，是否适合再测实际任务。

为什么有些错误要等调用 pop 才出现

P19 展示 queue 换用 vector 的尝试：部分操作能编译，调用 pop() 时才因底层缺少 pop_front() 报错。这个失败比只列一张“可以／不可以”表更有帮助，因为它把适配关系变成了可追踪的调用链。

课堂借此说明模板成员按需实例化。准确边界是：类模板的实例化，不等于立即实例化所有普通成员函数的定义；相关成员在需要时才进一步实例化。它不意味着模板完全不检查，也不意味着所有错误都一定拖到某个成员被调用时才发现。声明本身、约束及其他实例化要求同样可能更早报错。C++ 工作草案：隐式实例化

因此，某个不满足底层要求的组合暂时通过几个操作，不能用来证明它是合格的容器适配。课程最后还试了 set、map：set 缺少相应顺序容器操作；画面中的 map<string> 连映射值类型都没有提供，首先就是模板实参错误。即使补齐实参，也不会因此获得适配器所需的尾插、头删等接口。不能只凭“它也叫容器”就替换。

用坐标实验和真实容器分别验证

以下为整理者编写的 C++20 完整程序，已用 Clang 编译运行，通过全部断言。shift 只验证有限整数范围内的分段坐标，不是自行实现 deque；后半段验证标准接口行为。

#include <cassert>
#include <deque>
#include <iterator>
#include <list>
#include <queue>
#include <stack>
#include <utility>
#include <vector>

// 教学坐标：B>0，计算量很小，不涉及溢出或实际内存地址。
std::pair<int, int> shift(int offset, int n, int B) {
    int total = offset + n;
    int block = total / B;
    int within = total % B;
    if (within < 0) { --block; within += B; }
    return {block, within};
}

int main() {
    assert((shift(2, -3, 8) == std::pair{-1, 7}));
    assert((shift(2, 17, 8) == std::pair{2, 3}));
    for (int offset = 0; offset < 8; ++offset)
        for (int n = -30; n <= 30; ++n) {
            auto [block, within] = shift(offset, n, 8);
            assert(0 <= within && within < 8);
            assert(block * 8 + within == offset + n);
        }

    std::deque<int> d{10, 20, 30};
    int& element = d[1];
    d.push_front(5);
    d.push_back(40);
    assert(element == 20 && &element == &d[2]);
    // 端点插入后重新获取迭代器。
    auto it = d.begin() + 2;
    assert(*it == 20 && d.end() - d.begin() == 5);
    d.insert(it, 15);
    assert((d == std::deque<int>{5, 10, 15, 20, 30, 40}));
    // 中间插入后，不再使用之前的 it 和 element。

    std::queue<int, std::list<int>> q;
    std::stack<int, std::vector<int>> s;
    for (int n : {1, 2, 3}) { q.push(n); s.push(n); }
    for (int n : {1, 2, 3}) {
        assert(q.front() == n); q.pop();
        assert(s.top() == 4 - n); s.pop();
    }
    assert(q.empty() && s.empty());
    static_assert(std::random_access_iterator<std::deque<int>::iterator>);
    static_assert(!std::contiguous_iterator<std::deque<int>::iterator>);
}

小规模 deque 的例子不会保证在当前实现中跨越了物理分段；它验证的是公开契约。真正的跨段数学由前面的坐标循环验证，两种证据不要混为一谈。

继续练习时可以选三个问题：

删除 shift 的负余数修正，哪条断言先失败？再检查总偏移恰为 -8、-16 时是否需要相同修正。
用纸面表项和段内偏移推导两个位置的距离，检查同段、相邻段和跨三段的情况；用对应逻辑下标相减作为答案。
单独写一个 queue<int, vector<int>> 的诊断实验，分别保留和加入 pop()，记录你所用标准库的报错位置。它是观察实现诊断的练习，不是推荐这种底层组合。

重点回看

讲次与时间	画面或讨论线索	回看的问题
P18 · 01:35–10:23	buffer、map、`cur/first/last/node`	分段以后，迭代器还需知道什么？
P18 · 23:27–29:08	`insert_aux`、`size()/2`	为什么中间插入选择较短一侧？
P19 · 05:22–09:28	`operator-`、整段与两端余量	距离如何计算，而非逐个遍历？
P19 · 09:52–15:34	`++`、`--`、`set_node`	为什么两种移动的边界检查顺序不同？
P19 · 15:36–22:44	`+=`、段数、段内偏移	怎样把一次大跳转拆成两层坐标？
P19 · 31:18–35:01	queue/stack 成员 `c` 与转调用	适配器复用了什么，又限制了什么？
P19 · 39:37–42:28	`queue<vector>`、缺少 `pop_front`	部分成员编译成功为何不代表适配成立？