Chapter 51: Mini List

mini list 的主问题是：怎样用节点、哨兵、iterator、allocator 和局部指针重连实现一个双向链表容器，并让 insert、erase、splice、clear 都能给出稳定的对象状态。标准库中的 std::list 支持任意位置常数时间插入和删除，常见实现形状是双向链表；本章把这个接口现象压缩成一个可读的教学版实现。

本章的贯穿材料是一条小链表：先建立 MiniList<int> a，依次插入 1、2、3，再在 2 前插入 10，删除 3，最后把另一条链表 b 的一段节点接入 a。读者要追踪的核心对象有三个：哨兵节点保存端点关系，普通节点保存元素，iterator 保存当前节点地址。容器操作的输出都落到这三类对象的状态变化上。

mini list 和 mini vector 的差异在于修改成本落点不同。mini vector 的 insert 常常触发元素搬移，容量变化还会改变所有元素地址；mini list 的 insert 和 erase 只接触目标位置附近的节点。代价是每个元素拥有独立节点，空间多出两个指针，遍历也失去连续内存访问收益。

读完本章后，应能按照固定顺序检查一个 list 实现：先看哨兵和空表不变量，再看 iterator 是否只包装节点位置，再看修改操作是否先完成对象构造再提交链接，再看删除路径是否先断链再销毁释放，最后看 allocator 是否同时覆盖节点存储和异常失败清理。

51.1 node 结构

node 结构要先解决端点问题。双向链表的每个普通节点至少保存 prev、next 和 value，但 end() 指向的位置没有元素值。直接让 end() 使用空指针会让 --end()、空表判断和边界重连都出现额外分支。mini list 使用哨兵节点把这些分支收束成一个统一不变量：空表时，哨兵的 prev 和 next 都指向自己；非空表时，哨兵的 next 指向第一个节点，哨兵的 prev 指向最后一个节点。

下面的简化代码展示节点分层。list_node_base 只保存链接关系，哨兵使用这个基类对象即可；list_node<T> 在链接关系之外增加 value。这种拆分让 end() 可以指向哨兵，同时防止代码对哨兵执行元素解引用。

#include <cstddef>
#include <memory>
#include <utility>

template<class T>
class MiniList {
    struct list_node_base {
        list_node_base* prev;
        list_node_base* next;
    };

    struct list_node : list_node_base {
        template<class... Args>
        explicit list_node(Args&&... args)
            : list_node_base{nullptr, nullptr},
              value(std::forward<Args>(args)...) {}

        T value;
    };

    list_node_base sentinel_;
    std::size_t size_ = 0;

public:
    MiniList() noexcept : sentinel_{&sentinel_, &sentinel_} {}
};

这段代码的关键不是字段数量，而是对象身份。哨兵是容器对象的一部分，生命周期跟随 MiniList 本体；普通节点来自 allocator，生命周期跟随元素插入和删除。begin() 可以返回 sentinel_.next，end() 可以返回 &sentinel_，空表时二者相等。链表是否为空由一个指针比较完成，尾部插入也等价于“插入到哨兵之前”。

节点不变量可以写成四个可检查条件。第一，任意在链上的节点 p 都满足 p->next->prev == p。第二，任意在链上的节点 p 都满足 p->prev->next == p。第三，sentinel_.next 沿 next 方向最终回到 sentinel_。第四，sentinel_.prev 沿 prev 方向最终回到 sentinel_。这四个条件成立时，插入、删除和区间转移都可以写成局部指针替换。

贯穿材料中的初始状态是空表 a。它在内存中已经有一个有效哨兵，size_ == 0，a.begin() == a.end()。当后续插入 1、2、3 时，每个元素都会得到一个独立普通节点，哨兵只改变端点链接，本身仍然不保存 int。

51.2 iterator

iterator 的职责是把节点地址包装成位置对象。mini list 的 iterator 不持有容器指针也不持有元素副本，它只保存一个 list_node_base*。自增操作沿 next 前进，自减操作沿 prev 后退，解引用时把当前位置转回 list_node<T>* 并访问 value。

下面的简化 iterator 只展示核心路径。真实实现还会补充 const_iterator、类型别名、友元关系和调试检查；这些补充不会改变它的核心状态模型。

template<class T>
class MiniListIterator {
    using base_node = typename MiniList<T>::list_node_base;
    using value_node = typename MiniList<T>::list_node;

    base_node* current_ = nullptr;

public:
    using difference_type = std::ptrdiff_t;
    using value_type = T;
    using reference = T&;
    using pointer = T*;
    using iterator_category = std::bidirectional_iterator_tag;

    explicit MiniListIterator(base_node* p) noexcept : current_(p) {}

    reference operator*() const noexcept {
        return static_cast<value_node*>(current_)->value;
    }

    pointer operator->() const noexcept {
        return std::addressof(operator*());
    }

    MiniListIterator& operator++() noexcept {
        current_ = current_->next;
        return *this;
    }

    MiniListIterator& operator--() noexcept {
        current_ = current_->prev;
        return *this;
    }

    friend bool operator==(MiniListIterator lhs, MiniListIterator rhs) noexcept {
        return lhs.current_ == rhs.current_;
    }
};

这段代码能解释 list iterator 的能力边界。它能双向移动，因为节点保存了 prev 和 next。它不能随机访问，因为第 n 个后继需要沿链接走 n 次。它的比较只比较节点地址，所以两个 iterator 相等意味着它们指向同一个链表位置。跨容器比较在工程上没有有效意义，调试版实现通常会额外保存容器身份来检查这种误用。

end() 的特殊性来自哨兵。end() 是合法位置，可以比较，可以自减到最后一个元素；它没有元素值，因此解引用 end() 违反 iterator 前提。这个边界应由调用者和调试检查共同承担，mini list 的 release 版不需要在每次解引用时引入运行时分支。

贯穿材料中，插入 1、2、3 后，指向 2 的 iterator 保存的是节点 N2 的地址。后面在 2 前插入 10 时，N2 的地址不变，指向 2 的 iterator 仍然指向同一个元素。这个现象来自节点式容器的地址稳定性：局部插入只改相邻链接，不搬移已有元素。

51.3 insert

insert 的核心顺序是“创建新节点 → 构造元素 → 链接到目标位置之前 → 更新大小”。这个顺序把可能失败的动作放在提交之前。allocator 分配或元素构造抛出异常时，新节点还没有进入链表，容器旧状态保持完整；链接动作完成后，节点已经成为链表的一部分，后续只需要更新 size_。

局部链接函数可以独立出来。给定目标位置 pos 和新节点 fresh，插入到 pos 之前只需要读取 before = pos->prev，然后让 before <-> fresh <-> pos 成立。

static void link_before(list_node_base* pos, list_node_base* fresh) noexcept {
    list_node_base* before = pos->prev;

    fresh->prev = before;
    fresh->next = pos;
    before->next = fresh;
    pos->prev = fresh;
}

四次写指针的顺序有工程含义。先设置新节点的两侧链接，再改旧链上的两个端点，能缩短链表处在半提交状态的窗口。标准库实现仍会把这些操作封装得更细，因为调试 iterator、大小缓存和异常路径还会引入额外状态；教学版只需要保证链接提交前没有元素被暴露到链中。

下面的 emplace 展示完整路径。这里使用 node_allocator 分配普通节点，使用 allocator_traits 统一访问 allocator 的 allocate、construct、destroy 和 deallocate。insert 可以作为 emplace 的一层转发。

template<class T, class Alloc = std::allocator<T>>
class MiniList {
    struct list_node_base { list_node_base* prev; list_node_base* next; };
    struct list_node : list_node_base {
        template<class... Args>
        explicit list_node(Args&&... args)
            : list_node_base{nullptr, nullptr}, value(std::forward<Args>(args)...) {}
        T value;
    };

    using node_allocator = typename std::allocator_traits<Alloc>
        ::template rebind_alloc<list_node>;
    using node_traits = std::allocator_traits<node_allocator>;

    list_node_base sentinel_{&sentinel_, &sentinel_};
    std::size_t size_ = 0;
    node_allocator node_alloc_;

    template<class... Args>
    list_node* create_node(Args&&... args) {
        list_node* p = node_traits::allocate(node_alloc_, 1);
        try {
            node_traits::construct(node_alloc_, p, std::forward<Args>(args)...);
        } catch (...) {
            node_traits::deallocate(node_alloc_, p, 1);
            throw;
        }
        return p;
    }

public:
    using iterator = MiniListIterator<T>;

    template<class... Args>
    iterator emplace(iterator pos, Args&&... args) {
        list_node* fresh = create_node(std::forward<Args>(args)...);
        link_before(pos.current_, fresh);
        ++size_;
        return iterator{fresh};
    }
};

这段代码的异常安全来自提交点清晰。allocate 成功后，construct 可能因 T 的构造函数抛出异常而失败；失败路径只释放未入链节点。link_before 没有元素构造和分配动作，可以设计成 noexcept。因此 insert 对旧链表提供强异常安全：成功时多一个节点，失败时旧节点和旧链接保持原样。

贯穿材料中，在 2 前插入 10 时，pos 指向 N2，before 是 N1。link_before 之后，局部关系从 N1 <-> N2 变成 N1 <-> N10 <-> N2。N2 地址没有变化，所以插入前保存的 iterator 仍能访问值 2。

51.4 erase

erase 的核心顺序是“记录后继 → 从链上断开目标节点 → 销毁元素和节点 → 更新大小 → 返回后继 iterator”。它处理的是已经在链上的节点，因此失败点主要来自用户类型析构。常规容器设计要求析构路径保持可清理，工程上应把元素析构写成不抛异常的操作。

断链函数和插入函数互为镜像。给定目标节点 victim，只需要让 victim->prev 和 victim->next 直接相连。断链后，victim 已经不属于链表，后续销毁释放不会影响遍历结构。

static void unlink_node(list_node_base* victim) noexcept {
    list_node_base* before = victim->prev;
    list_node_base* after = victim->next;

    before->next = after;
    after->prev = before;
}

erase 返回后继 iterator 是一个接口层约定。调用方常常在循环中一边遍历一边删除当前元素，返回后继能让循环继续前进。这个返回值必须在断链前保存，因为销毁释放后再从 victim 读取 next 会访问已经结束生命周期的对象。

iterator erase(iterator pos) noexcept {
    list_node_base* raw = pos.current_;
    list_node_base* next = raw->next;

    unlink_node(raw);
    destroy_node(static_cast<list_node*>(raw));
    --size_;

    return iterator{next};
}

erase(end()) 没有有效目标元素。end() 指向哨兵，哨兵没有 value，也不能被 allocator 释放。mini list 的实现可以把这个条件写成前置条件；调试版可以检查 pos.current_ != &sentinel_ 并在违反时报告错误。release 版通常把这种检查交给调用约束，以保持容器热路径简洁。

贯穿材料中，链表 1, 10, 2, 3 删除 3 时，victim 是尾节点 N3，next 是哨兵。断链后，哨兵的 prev 改为 N2，N2->next 改为哨兵。返回值是 end()，调用方可以据此判断已经到达末尾。

51.5 splice

splice 的价值在于转移节点所有权。标准库 list::splice 的语义是把另一条 list 的元素转移到当前位置前，元素值本身不拷贝也不移动，内部节点链接会被重新指向；被移动元素的 iterator 和 reference 仍指向同一批元素，只是这些元素现在属于目标容器。标准语义还要求两个 list 的 allocator 相容，常见表达是 get_allocator() == other.get_allocator()。

mini list 可以把区间转移拆成两个动作：先从源链表摘下半开区间 [first, last)，再把这段链插入目标位置 pos 前。这里的 last 是区间尾后位置，可能是源链表的哨兵；被转移的最后一个节点是 last->prev。

static void transfer_before(
    list_node_base* pos,
    list_node_base* first,
    list_node_base* last
) noexcept {
    if (first == last) {
        return;
    }

    list_node_base* before_first = first->prev;
    list_node_base* last_node = last->prev;
    list_node_base* before_pos = pos->prev;

    before_first->next = last;
    last->prev = before_first;

    before_pos->next = first;
    first->prev = before_pos;

    last_node->next = pos;
    pos->prev = last_node;
}

这六次指针写入构成 splice 的主路径。前两次把源链表缺口闭合，中间两次把目标前驱接到区间头，最后两次把区间尾接到目标位置。元素对象没有经历构造、赋值和析构，因此持有资源的 T 不会被触碰。这个性质让 splice 适合实现任务队列合并、LRU 链表移动、批量重排等节点级操作。

splice 的边界比 insert 更严格。第一，源区间必须是有效半开区间。第二，目标位置不能落在被移动区间内部。第三，跨容器转移时 allocator 必须相容，因为节点最终要由目标容器的清理路径释放；两个 allocator 不相容时，把源节点交给目标 allocator 释放会破坏分配/释放配对。第四，自身内部移动需要特别处理 pos == first、pos == last 这类无效果情况。

size 维护也需要选择策略。若 splice 转移单个节点，两个容器的 size_ 可以常数时间更新。若转移区间，教学版可以在线性遍历中计算节点数量；工程实现会根据标准版本、实现策略和是否为同一容器调整成本。关键判断是：指针重连本身是常数动作，区间长度统计可能引入线性成本。

贯穿材料中，若 b 为 20, 30, 40，将 [20, 40) 接到 a 的 2 前，转移的是 20, 30 两个节点。操作后 a 变成 1, 10, 20, 30, 2，b 剩下 40。保存的 20 节点 iterator 仍能解引用为 20，它现在沿 prev 和 next 连接到 a 的节点。

51.6 clear

clear 的职责是销毁所有普通节点，并把哨兵恢复到空表状态。它既要完成资源释放，又要留下一个可继续使用的容器对象。清空后的 MiniList 仍然拥有同一个哨兵，begin() 和 end() 再次相等，后续还能继续插入新元素。

清理循环必须在销毁当前节点之前保存下一个节点。普通节点释放后，它的 next 字段也随对象生命周期结束，继续读取会进入无效访问。这个顺序和 erase 返回后继 iterator 的理由一致。

void clear() noexcept {
    list_node_base* current = sentinel_.next;
    while (current != &sentinel_) {
        list_node_base* next = current->next;
        destroy_node(static_cast<list_node*>(current));
        current = next;
    }

    sentinel_.next = &sentinel_;
    sentinel_.prev = &sentinel_;
    size_ = 0;
}

clear 可以不逐个调用 erase。直接循环销毁节点能减少重复的断链写指针，因为最终结果一定是空表。断链是否逐个维护取决于实现目标：若要在调试工具中观察每一步不变量，可以先断链再销毁；若只要求 clear 结束后状态有效，顺序遍历销毁再重置哨兵更直接。

析构函数通常调用 clear() 后结束容器本体生命周期。析构路径不释放哨兵，因为哨兵是对象成员；它只释放 allocator 分配出的普通节点。若 T 的析构函数抛出异常，容器析构期间会导致严重后果，工程类型应把析构设计为不抛异常。mini list 的 clear() noexcept 体现的是容器清理路径的正常前提。

贯穿材料中，a.clear() 会按当前顺序销毁 1, 10, 20, 30, 2 对应节点。每个节点先取后继，再销毁释放。循环结束后，a 回到空表，b 仍保留自己的 40 节点。跨容器 splice 已经改变节点归属，所以被接入 a 的节点由 a.clear() 清理。

51.7 allocator 参与

allocator 在 mini list 中管理的是节点存储。容器元素类型是 T，但实际分配单位是 list_node，因此实现需要把 Alloc 通过 allocator_traits 重新绑定为 list_node 的 allocator。C++11 起，std::allocator_traits 提供了访问 allocator 属性和操作的标准化入口，标准容器也通过这个入口使用用户提供的 allocator。

节点分配路径可以拆成四个阶段：分配一块能容纳 list_node 的原始存储，构造 list_node 并在其中构造 T，把节点链接进链表，在删除时按相反顺序销毁和释放。这个顺序把内存责任和对象生命周期分开，便于处理构造失败。

void destroy_node(list_node* p) noexcept {
    node_traits::destroy(node_alloc_, p);
    node_traits::deallocate(node_alloc_, p, 1);
}

create_node 和 destroy_node 必须成对理解。create_node 中，allocate 成功后若 construct 失败，代码只执行 deallocate，因为对象尚未构造完成。destroy_node 中，对象已经在链上存在过，先 destroy 结束 list_node 与 T 的生命周期，再 deallocate 归还原始存储。把这两个函数封装起来，可以让 insert、erase、clear 都保持清晰的主路径。

allocator 还影响 splice。节点从源容器转入目标容器后，未来会被目标容器销毁释放。若两个容器使用不同内存资源，目标 allocator 可能无法释放源 allocator 分配出的节点。教学版 mini list 可以直接规定跨容器 splice 需要 allocator 相等；违反时通过断言或异常报告。标准库对这一点有明确边界，工程代码应把它视为节点所有权转移的前置条件。

allocator 传播规则也会影响拷贝、移动和交换，但本章只需要抓住 mini list 的最小充分路径：节点怎么分配，构造失败怎么清理，节点进入链表后由谁释放，跨容器转移是否保持分配/释放配对。这个顺序比记住所有 allocator trait 名称更可迁移。

到这里，贯穿材料的所有动作已经闭合。插入负责创建节点并提交链接，删除负责断链并释放节点，splice 负责转移节点归属，clear 负责批量销毁普通节点并恢复哨兵。mini list 的实现质量可以用一个顺序判断：哨兵不变量是否一直成立，iterator 是否保存稳定节点位置，修改操作是否有清晰提交点，allocator 是否覆盖所有节点生命周期。

最小自检任务

阅读下面的操作序列，判断每一步之后哪些 iterator 仍可用，哪些节点由哪个容器负责清理，并说明 splice 对元素对象执行了哪些构造、移动、析构动作。

MiniList<int> a;
MiniList<int> b;

a.emplace(a.end(), 1);
a.emplace(a.end(), 2);
a.emplace(a.end(), 3);

b.emplace(b.end(), 10);
b.emplace(b.end(), 20);

MiniList<int>::iterator it2 = ++a.begin();
MiniList<int>::iterator it10 = b.begin();

a.emplace(it2, 7);
a.erase(--a.end());
a.splice(it2, b, it10, b.end());
a.clear();

答案要点

it2 在 a.emplace(it2, 7) 之后仍指向值为 2 的节点，因为插入只在 it2 前重连局部指针，没有搬移已有节点。a.erase(--a.end()) 删除的是值为 3 的尾节点，只有指向该节点的 iterator 失效，返回值会是 a.end()。

it10 在 a.splice(it2, b, it10, b.end()) 之后仍能解引用为 10，但它现在指向 a 内的节点。splice 转移的是 b 中从 10 到末尾前的区间，即 10、20 两个节点；操作后 b 为空，a 的顺序为 1, 7, 10, 20, 2。

splice 对 10 和 20 的元素对象不执行构造、移动、拷贝和析构，只修改节点链接和容器归属。前提是两个容器的 allocator 相容，且 it2 没有落在被转移区间内部。最后 a.clear() 会销毁并释放 1、7、10、20、2 对应节点，b 只保留空表哨兵。

本章知识点总结

• 哨兵节点：哨兵把空表、头部、尾部和 end() 统一成同一套链接规则。
• 节点分层：基类节点保存 prev 和 next，普通节点在此基础上保存元素值。
• 空表不变量：空表时哨兵的 prev 和 next 都指向哨兵自身。
• iterator 状态：list iterator 只需要保存当前节点地址，移动操作沿节点链接完成。
• 端点边界：end() 可以比较和自减，但它指向哨兵，没有可解引用的元素值。
• 插入提交点：insert 应先完成节点分配和元素构造，再把节点链接进链表。
• 异常清理：元素构造失败时，新节点尚未入链，释放原始存储即可恢复旧状态。
• 删除顺序：erase 应先保存后继并断链，再销毁和释放目标节点。
• 返回后继：erase 返回后继 iterator，方便遍历删除场景继续推进。
• splice 语义：splice 转移节点链接和容器归属，不触碰元素对象本身。
• allocator 边界：跨容器 splice 需要 allocator 相容，保证节点最终由正确内存资源释放。
• clear 收束：clear 销毁所有普通节点后，必须把哨兵恢复为空表状态。
• 实现检查：mini list 的检查顺序是哨兵不变量、iterator 位置、修改提交点、节点生命周期和 allocator 配对。