Chapter 14: Forward List

std::forward_list 的主问题是：在每个节点只保存一个 next 指针的条件下，容器如何完成插入、删除、遍历和资源管理，并把这种限制转化成可预测的工程取舍。读完本章后，读者应能定位一个 forward_list 操作真正需要的位置对象，判断 insert_after 和 erase_after 的前驱节点边界，解释 size() 缺席背后的复杂度设计，并写出一个最小单向链表实现。

本章使用一个贯穿材料：维护一个按顺序处理的任务链表。任务节点只需要从前往后扫描，处理过程中可能在当前任务后插入新任务，也可能删除当前任务后面的过期任务。这个场景很贴近 forward_list 的接口形状：它关心“某个节点之后发生什么”，很少关心“某个节点之前是什么”。

在 vector 中，修改位置通常由下标或随机访问 iterator 表达；在 list 中，双向节点允许 iterator 同时向前和向后移动；在 forward_list 中，iterator 只持有当前节点位置，节点本身只知道后继节点。因此，本章的判断顺序固定为：先确认修改点的前驱节点，再确认被修改节点的生命周期，再确认 iterator 能力和遍历成本，最后比较它与 list 的空间、访问和维护代价。

std::forward_list 从 C++11 起定义在头文件 <forward_list> 中。它满足序列容器的主要接口要求，并通过 allocator 管理节点存储。C++20 增加了非成员 std::erase 和 std::erase_if，C++23 增加了 range 版本的构造和插入接口。版本演进会扩展接口表面，但本章核心仍然是单向节点、头前位置、after 操作和 forward iterator。

14.1 单向链表、节点结构与 before_begin

forward_list 的最小对象模型由三类状态组成：容器持有一个头前控制位置，每个元素节点保存一个值和一个后继指针，iterator 保存能定位某个节点的状态。这个模型的关键约束是单向链接：从一个节点可以走到它的后继节点，反向关系需要从链表头重新扫描才能找到。

可以把一个任务链表画成下面的状态。before_begin 位于第一个真实元素之前，它本身是容器提供的稳定位置接口，用来统一处理“在链表开头插入”和“删除第一个元素”这两类操作。

图中的 end 是尾后位置，表示遍历结束；before_begin 是头前位置，表示第一个元素的前驱。forward_list 通过这两个特殊位置把空链表、首元素修改和中间节点修改统一到同一套 after 接口上。

简化实现中，节点形状可以写成下面这样。真实标准库实现会加入 allocator traits、压缩空基类、异常安全 guard、调试 iterator 等设施；这段代码只展示对象关系。

#include <utility>

struct Task {
    int id{};
    bool expired{};
};

template <class T>
struct forward_node {
    T value;
    forward_node* next = nullptr;

    template <class... Args>
    explicit forward_node(forward_node* next_node, Args&&... args)
        : value(std::forward<Args>(args)...), next(next_node) {}
};

节点只保存 next，所以节点自身没有能力回答“谁指向我”。这个设计减少了每个节点的一个指针字段，也减少了插入和删除时需要维护的链接数量。代价也很直接：删除某个节点时，调用方必须已经拥有它的前驱位置。

before_begin 可以由一个哨兵节点表达，也可以由实现内部的头指针封装表达。教学实现常把它写成一个不保存用户值的头前哨兵：

struct node_base {
    node_base* next = nullptr;
};

template <class T>
struct node : node_base {
    T value;

    explicit node(const T& v) : value(v) {}
};

template <class T>
class mini_forward_list {
    node_base before_; // before_begin 位置

public:
    node_base* before_begin_node() noexcept {
        return &before_;
    }
};

这段简化代码表达了一个实现习惯：容器对象本身可以保存头前哨兵，哨兵的 next 指向第一个元素。空链表时，before_.next == nullptr。有元素时，before_.next 指向首节点。这样一来，首元素插入等价于“在 before_begin 之后插入”，首元素删除等价于“删除 before_begin 之后的元素”。

before_begin 的工程意义在于把“头指针特殊分支”移入容器接口。手写单向链表时，经常需要单独处理头节点：删除首节点要修改 head，删除中间节点要修改 prev->next。forward_list 把 head 前面补出一个可表达的位置，使调用代码围绕前驱节点写成统一形式。

贯穿材料中的任务处理代码可以从 before_begin 开始维护前驱位置：

#include <forward_list>

struct Job {
    int id;
    bool expired;
};

std::forward_list<Job> jobs = {{1, false}, {2, true}, {3, false}};

auto prev = jobs.before_begin();
auto cur = jobs.begin();

这里的 prev 表示当前元素的前驱，cur 表示当前元素。对 forward_list 来说，这组位置比单独保存 cur 更有信息量，因为后续删除当前元素时需要改写 prev 的后继指针。

14.2 insert_after 与 erase_after 的前驱节点语义

insert_after 和 erase_after 的输入位置表示“前驱节点”，操作对象位于该位置之后。这个接口表面看起来多绕了一层，实际对应单向链表的最小可修改信息：改写一条链接必须能访问保存这条链接的节点。

插入一个新节点时，链表需要完成三步：分配节点存储，在节点存储中构造元素，把前驱节点原来的后继接到新节点后面，然后让前驱指向新节点。用伪代码表达就是 new_node->next = prev->next; prev->next = new_node;。整个操作只改写前驱节点和新节点两个对象。

// 简化代码：展示 insert_after 的链接顺序，省略 allocator 和异常安全 guard。
template <class T>
node_base* insert_after_node(node_base* prev, const T& value) {
    auto* created = new node<T>(value);
    created->next = prev->next;
    prev->next = created;
    return created;
}

插入顺序有明确原因。新节点先接上旧后继，再让前驱指向新节点。这样提交点集中在 prev->next = created 这一句。真实实现还会把节点分配、元素构造和链接提交分成阶段：分配或构造失败时，链表仍保持旧链接；链接提交完成后，新元素进入容器所有权。

删除一个节点时，前驱节点同样是必需输入。被删除节点本身只保存到下一个节点的链接，它无法找到指向自己的那条链接。erase_after(prev) 的核心动作是取出 prev->next，让 prev->next 跳过该节点，再销毁被跳过节点中的元素并释放节点存储。

// 简化代码：展示 erase_after 的链接顺序，调用方保证 prev 后面存在元素。
template <class T>
node_base* erase_after_node(node_base* prev) {
    auto* erased = static_cast<node<T>*>(prev->next);
    prev->next = erased->next;
    delete erased;
    return prev->next;
}

删除顺序也有对象生命周期含义。先保存被删节点地址，再重连前驱，再销毁节点。重连之后，链表不再拥有该节点；销毁之后，原来指向该元素的 iterator 和 reference 失效。其他节点没有被移动，指向其他元素的 iterator 和 reference 仍然指向原节点。

这正是 forward_list 与 vector 的修改语义差异。vector 插入和删除可能移动一段元素，位置稳定性受扩容和元素搬移影响；forward_list 修改局部链接，其他元素节点地址保持稳定。判断 iterator 有效性时，核心问题从“连续存储有没有搬移”变成“这个 iterator 是否指向被删除的节点”。

贯穿材料中的删除过期任务可以写成下面的形状：

#include <forward_list>

void remove_expired_after_scan(std::forward_list<Job>& jobs) {
    auto prev = jobs.before_begin();
    auto cur = jobs.begin();

    while (cur != jobs.end()) {
        if (cur->expired) {
            cur = jobs.erase_after(prev);
        } else {
            prev = cur;
            ++cur;
        }
    }
}

这段代码的关键并非 erase_after 这个名字，而是循环不变量：每次进入循环时，prev 总是 cur 的前驱。删除 cur 后，prev 仍然保留，erase_after(prev) 返回删除位置之后的新位置，所以循环可以继续扫描。保留前驱位置是单向链表删除逻辑的核心。

插入新任务时也要围绕前驱或当前位置思考。如果需求是“在当前任务后插入派生任务”，当前位置本身就能充当前驱：

void insert_followup_after_current(std::forward_list<Job>& jobs, int target_id, Job followup) {
    for (auto it = jobs.begin(); it != jobs.end(); ++it) {
        if (it->id == target_id) {
            jobs.insert_after(it, followup);
            return;
        }
    }
}

这里 it 指向目标任务，插入发生在 it 之后。新任务的出现不会改变目标任务节点，也不会移动其他节点。对外部保存的目标任务 iterator 来说，它仍然指向同一个节点；对保存到旧后继节点的 iterator 来说，它也仍然指向旧后继节点，只是遍历顺序中间多了一个新节点。

push_front 可以看作 insert_after(before_begin(), value) 的便捷形式，pop_front 可以看作 erase_after(before_begin()) 的便捷形式。这个等价关系很有用：它说明 forward_list 的“前端操作”仍然遵守前驱节点语义，只是容器替调用者提供了头前位置。

14.3 forward iterator、size 缺席与遍历成本

forward_list 的 iterator 属于 forward iterator。它支持解引用、相等比较和前置或后置递增，并能多次遍历同一个范围。它没有随机访问能力，也没有反向移动能力。这个能力边界直接来自节点结构：iterator 可以沿 next 前进，链表中没有从当前节点走回前驱节点的链接。

forward iterator 的工程后果可以从三类操作看出。第一类是顺序扫描，例如查找某个任务，成本是线性的。第二类是已知前驱位置后的局部修改，例如 insert_after 和 erase_after，链接修改本身是常数成本。第三类是需要定位前驱的修改，例如“删除值等于 7 的第一个节点”，定位过程仍然需要从头扫描。

#include <forward_list>
#include <algorithm>

bool contains_job(const std::forward_list<Job>& jobs, int id) {
    return std::find_if(jobs.begin(), jobs.end(), [id](const Job& job) {
        return job.id == id;
    }) != jobs.end();
}

这段查找代码可以使用通用算法，因为 std::find_if 只要求输入范围能向前遍历。算法并不关心底层是连续数组、分段数组还是节点链表。代价由 iterator 能力决定：对 forward_list，每次递增都沿一个 next 指针前进，整体扫描成本与元素数量成正比。

forward_list 没有成员 size()，这是它区别于多数标准容器的显著接口选择。原因可以按对象状态理解：如果容器只保存头前位置，长度只能通过遍历计数得到。若容器额外保存一个计数字段，每次插入、删除、splice、merge、remove、unique 等修改都要维护这个字段，并可能影响某些操作的常数开销和实现复杂度。

标准库选择让 forward_list 保持接近“零额外空间开销”的单向链表模型。需要长度时，调用方可以使用 std::distance(jobs.begin(), jobs.end())，并接受线性成本：

#include <forward_list>
#include <iterator>

std::ptrdiff_t count_jobs(const std::forward_list<Job>& jobs) {
    return std::distance(jobs.begin(), jobs.end());
}

这段代码的成本不应被误判成读取字段。std::distance 面对 forward iterator 时会逐个递增 iterator。只有 random access iterator 才能通过减法计算距离。用这段代码审查性能时，判断顺序是：先看 iterator category，再看算法是否需要距离，再看这个距离是否会在循环内重复计算。

下面的代码展示一个常见成本放大点：

#include <forward_list>
#include <iterator>

bool has_too_many_jobs(const std::forward_list<Job>& jobs, std::ptrdiff_t limit) {
    return std::distance(jobs.begin(), jobs.end()) > limit;
}

这个函数每调用一次都完整扫描链表。若它出现在外层循环的每次迭代中，整体成本会从一次线性扫描变成多次线性扫描。工程上通常有两种处理方式：把长度作为业务层状态单独维护，或者改写逻辑为“扫描时顺便计数并在超过阈值时返回”。选择哪一种取决于修改频率、长度查询频率和状态一致性责任。

iterator 失效也要放在 forward iterator 能力边界内判断。insert_after 不会移动已有节点，原有 iterator 仍指向原节点；erase_after 销毁被删除节点，指向该节点的 iterator 和 reference 失效；指向其他节点的 iterator 仍然可用。这个判断来自节点所有权和生命周期，并非来自接口命名。

14.4 内存开销、list 对比与工程使用场景

forward_list 和 list 都是节点式序列容器，元素存储在独立节点中，插入和删除主要通过重连指针完成。它们的核心差异是节点链接方向：forward_list 每个节点只保存后继指针，list 每个节点同时保存前驱和后继指针。这个差异会传导到空间开销、iterator 能力、接口形状和可维护性。

用同一组维度比较两者，可以得到稳定的选型判断。

维度	forward_list	list
节点链接	单个 next 指针	prev 与 next 两个指针
iterator 能力	forward iterator	bidirectional iterator
删除接口	以 erase_after 表达前驱语义	以 erase 表达当前位置语义
首元素前位置	提供 before_begin	通过双向哨兵和 begin / end 处理
长度接口	无成员 size()	有成员 size()
空间开销	每节点少一个链接指针	每节点多维护一个反向链接
访问模式	适合单向扫描	适合双向遍历和当前位置删除

这张表的结论应落实到访问模式上。若业务逻辑天然从头到尾处理元素，且修改点总能由“前驱位置”表达，forward_list 的节点更小，接口也足够。若业务逻辑经常需要从当前位置删除自己、向前回退、在双向遍历中移动位置，list 的反向链接能减少额外扫描和前驱维护负担。

内存开销需要同时看节点字段、分配元数据和访问模式。节点式容器通常每个元素一次独立分配，分配器元数据、对齐填充和缓存局部性都会影响真实成本。forward_list 相对 list 的空间收益主要来自节点内少一个链接指针；相对 vector 的成本则来自节点分散、每个节点带指针和分配开销。比较容器时，应把“同为节点式”和“连续存储”分成两个层级。

forward_list 的缓存局部性通常弱于 vector。顺序遍历时，CPU 很难像处理连续数组那样提前加载一段相邻元素，因为链表的下一个地址存放在当前节点里。即使每次节点访问本身是常数动作，常数项也可能受缓存未命中和分配碎片影响。在热路径中，少一个指针字段带来的空间收益可能被分散访问成本抵消。

适合 forward_list 的场景通常满足以下条件：元素数量可能变化，插入删除发生在扫描过程中，外部保存节点位置的需求有限，遍历方向单一，长度查询频率低，元素对象较大或节点链接开销相对可接受。典型例子包括简化的空闲块链、单向任务队列中的中间过滤链、只向前处理的 intrusive 风格链表，以及需要稳定节点地址的轻量序列。

较弱的使用场景也很明确：需要频繁按下标访问，使用 vector 或 deque 更直接；需要频繁获取长度，额外维护计数或选择其他容器；需要从当前位置删除当前节点，list 的 erase(it) 更贴合；需要排序并追求连续内存局部性，通常先考虑 vector 加算法，再用数据移动成本和 iterator 稳定性验证选择。

本章贯穿的任务链表适合 forward_list 的原因在于处理逻辑天然单向，并且删除时可以维护 prev。如果业务变成“从任意任务向前找上一个依赖任务”，单向链表就会反复从头扫描。此时容器选择应重新评估，因为接口限制已经进入业务复杂度。

工程选型可以按下面顺序执行：先看访问方向是否单向；再看修改操作是否能稳定拿到前驱位置；然后看是否频繁查询长度；接着看节点稳定性是否比缓存局部性更重要；最后看元素规模和分配策略是否让少一个指针字段具备实际收益。这个顺序能把“容器特性”转成可检查的代码事实。

14.5 mini forward_list 实现路径

最小 forward_list 实现的目标是把本章前面的对象关系落到代码：容器保存头前哨兵，节点保存 value 和 next，iterator 保存当前节点指针，修改操作围绕 after 语义展开。这个实现不追求覆盖完整标准接口，它服务于源码阅读时识别真实实现中的主路径。

先定义基础节点。为了让 before_begin 不构造用户元素，可以把无值的 node_base 和有值的 node<T> 分开。真实实现也常见类似分层，只是名称、继承方式和 allocator 封装会不同。

#include <cstddef>
#include <utility>

struct mini_forward_node_base {
    mini_forward_node_base* next = nullptr;
};

template <class T>
struct mini_forward_node : mini_forward_node_base {
    T value;

    template <class... Args>
    explicit mini_forward_node(Args&&... args)
        : value(std::forward<Args>(args)...) {}
};

iterator 只需要保存一个节点指针。operator++ 沿 next 前进，operator* 把基础节点转换成有值节点。这个转换依赖一个前提：普通 iterator 指向真实元素节点；before_begin 位置只能用于 after 操作和递增到首元素，不能解引用。

template <class T>
class mini_forward_iterator {
    mini_forward_node_base* current_ = nullptr;

public:
    using difference_type = std::ptrdiff_t;
    using value_type = T;

    explicit mini_forward_iterator(mini_forward_node_base* p = nullptr) : current_(p) {}

    T& operator*() const {
        return static_cast<mini_forward_node<T>*>(current_)->value;
    }

    T* operator->() const {
        return &static_cast<mini_forward_node<T>*>(current_)->value;
    }

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

    bool operator==(const mini_forward_iterator& other) const {
        return current_ == other.current_;
    }

    bool operator!=(const mini_forward_iterator& other) const {
        return current_ != other.current_;
    }

    mini_forward_node_base* node_ptr() const {
        return current_;
    }
};

这段 iterator 代码展示了 forward iterator 的最小状态。它没有 operator--，没有下标运算，也没有两个 iterator 相减的能力。算法看到这种 iterator，就应把它当作只能向前推进的位置对象。

容器主体保存一个头前哨兵。begin() 返回首元素位置，before_begin() 返回哨兵位置，end() 返回空指针尾后位置。insert_after 和 erase_after 通过哨兵或普通节点统一处理首元素和中间元素。

template <class T>
class mini_forward_list {
    mini_forward_node_base before_;

public:
    using iterator = mini_forward_iterator<T>;

    mini_forward_list() = default;

    ~mini_forward_list() {
        clear();
    }

    iterator before_begin() noexcept {
        return iterator(&before_);
    }

    iterator begin() noexcept {
        return iterator(before_.next);
    }

    iterator end() noexcept {
        return iterator(nullptr);
    }

    template <class... Args>
    iterator emplace_after(iterator pos, Args&&... args) {
        auto* prev = pos.node_ptr();
        auto* created = new mini_forward_node<T>(std::forward<Args>(args)...);
        created->next = prev->next;
        prev->next = created;
        return iterator(created);
    }

    iterator erase_after(iterator pos) {
        auto* prev = pos.node_ptr();
        auto* erased = static_cast<mini_forward_node<T>*>(prev->next);
        prev->next = erased->next;
        delete erased;
        return iterator(prev->next);
    }

    void clear() noexcept {
        auto* cur = before_.next;
        while (cur != nullptr) {
            auto* next = cur->next;
            delete static_cast<mini_forward_node<T>*>(cur);
            cur = next;
        }
        before_.next = nullptr;
    }
};

这段实现省略了几个真实容器必须处理的边界：erase_after 需要调用方传入后面存在元素的位置；拷贝构造、移动构造、赋值和 allocator propagation 没有展开；节点构造失败时的释放保护也被简化。它仍然足以建立源码阅读主线：找到头前状态，找到节点基类，找到 iterator 内部指针，找到 after 操作的链接提交点。

把贯穿材料放回这个 mini 容器，可以得到和标准接口一致的思考方式：

mini_forward_list<Job> pending;

auto prev = pending.before_begin();
pending.emplace_after(prev, Job{1, false});
pending.emplace_after(prev, Job{2, true});

第二次 emplace_after(prev, ...) 仍然插入在 before_begin 之后，所以新节点会成为首元素。这个行为提醒我们：after 操作的插入位置由传入 iterator 决定。如果要保持追加顺序，调用方需要把返回的 iterator 保存为新的尾部位置，或者每次扫描到尾前位置再插入。

源码阅读时可以按四个检查点定位 forward_list 实现。第一，容器对象中是否有头前控制节点或等价头指针包装。第二，普通节点如何在基础链接节点上附加 value。第三，iterator 是否只保存当前节点以及如何递增。第四，insert_after、erase_after、splice_after 等操作在哪里完成链接重连和所有权提交。只要这四点清楚，模板包装和 allocator 细节就能放回相应层级理解。

最小自检任务

阅读下面的代码，判断循环删除逻辑是否正确，并说明每次删除后 prev 和 cur 分别应指向哪里。再判断哪些 iterator 或 reference 会失效。

#include <forward_list>

struct Job {
    int id;
    bool expired;
};

void cleanup(std::forward_list<Job>& jobs) {
    auto prev = jobs.before_begin();
    auto cur = jobs.begin();

    while (cur != jobs.end()) {
        if (cur->expired) {
            cur = jobs.erase_after(prev);
        } else {
            prev = cur;
            ++cur;
        }
    }
}

答案要点

这段循环是正确的。循环不变量是 prev 始终表示 cur 的前驱。遇到过期任务时，erase_after(prev) 删除的正是 cur 指向的节点，并返回被删节点之后的位置；此时 prev 保持原位置，cur 更新为返回值。遇到非过期任务时，扫描向前推进，先让 prev = cur，再让 cur 指向后继节点。

失效判断以节点生命周期为依据。被 erase_after 删除的那个节点被销毁，指向该节点的 iterator 和 reference 失效。指向其他节点的 iterator 和 reference 仍然指向原节点，因为 forward_list 删除只重连局部链接，不移动其他元素。若外部代码保存了被删节点的引用，删除后继续访问会进入悬垂引用风险。

这道题还验证了一个选型边界：删除当前节点时，循环必须保留前驱位置。若代码只保存 cur，单向链表无法从 cur 直接找到前驱，需要重新从头扫描或改用能表达当前位置删除的容器。

本章知识点总结

• 单向节点：forward_list 节点只保存后继链接，所有反向定位都需要额外状态或重新扫描。
• 头前位置：before_begin 把首元素前驱显式表达出来，使首元素修改和中间节点修改使用同一套 after 语义。
• 前驱语义：insert_after 和 erase_after 的位置参数表示前驱节点，修改对象位于该位置之后。
• 链接提交：插入先构造新节点并接上旧后继，再让前驱指向新节点，提交点集中在前驱链接改写处。
• 删除生命周期：删除先重连前驱，再销毁被跳过节点，只有被销毁节点对应的 iterator 和 reference 失效。
• 迭代器能力：forward_list 提供 forward iterator，只能向前推进，算法成本必须按单向遍历计算。
• 长度成本：forward_list 无成员 size()，长度统计需要遍历，频繁查询时应在业务层维护计数或改写扫描逻辑。
• 空间取舍：相比 list，forward_list 每节点少一个反向链接；相比连续容器，它仍然承担节点分配和缓存局部性成本。
• 适用场景：单向扫描、局部插入删除、低频长度查询和稳定节点地址需求共同支持选择 forward_list。
• 源码检查：阅读实现时先找头前状态、节点分层、iterator 当前指针和 after 操作的链接重连路径。