Chapter 14: Forward List
核心问题与阅读主线
std::forward_list 每个节点只保留一个 next 指针,在省去反向链接空间的同时,要求调用方显式持有前驱位置才能完成插入与删除。本章拆解 before_begin 与 after 语义、forward iterator 与 size() 缺席的复杂度边界,以及单向链表的最小实现与容器选型。
全章共用场景样本
本章使用一个贯穿场景:维护按顺序扫描的任务链表(任务包含 id 与 expired 标记),扫描时可能在当前任务后追加派生任务,或直接摘除后面的过期节点——只关心“某节点之后发生什么”,无需回溯前驱。
关键事实
std::forward_list 自 C++11 起定义于 <forward_list>,通过 allocator 管理节点存储;C++20 新增非成员 std::erase / std::erase_if,C++23 新增 range 构造与插入接口。
14.1 单向链表、节点结构与 before_begin
forward_list 的最小对象模型由三部分组成,所有操作均受单向链接约束(只能沿 next 向前,回溯前驱必须从头扫描):
- 头前控制位:容器持有的
before_begin位置,位于首元素之前。 - 元素节点:每个节点仅保存元素值与后继指针
next。 - iterator:仅保存指向当前节点的指针状态。
before_begin 不可解引用,仅作为首元素前驱参与 after 操作;空链表时 before_begin 的后继即 end,从而消除手写链表中修改 head 指针的特殊分支。
基础元素节点仅包含 value 与 next 指针:
#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) {}
};
为避免给 before_begin 构造无意义的 T 实例,实现通常将无值基类 node_base 与带值派生节点 node<T> 分离,并在容器内嵌一个 node_base 作为头前哨兵:
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_;
}
};
空链表时 before_.next == nullptr,非空时指向首节点。由此,首部插入等价于在 before_begin 后插入,首部删除等价于删除 before_begin 后的节点,手写链表中修改 head 与修改 prev->next 的双分支被统一为同一套前驱接口。
贯穿场景中的任务链表扫描从 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();
核心判断
由于节点自身无法回答“谁指向我”,扫描期间一旦可能需要删除当前节点 cur,就必须同步维护前驱 prev;只持有 cur 无法改写指向它的链接。
14.2 insert_after 与 erase_after 的前驱节点语义
insert_after 与 erase_after 的位置参数均表示前驱节点 prev,因为改写单向链接必须直接访问保存该链接的对象。
插入新节点遵循“先接后继、再改前驱”的提交顺序:
- 分配节点存储并构造元素(若构造抛异常,原链表链接不受影响)。
- 执行
created->next = prev->next,接上原后继。 - 执行
prev->next = created,将所有权提交给链表。
// 简化代码:展示 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。erase_after(prev) 先暂存被删节点 erased = prev->next,再令 prev->next = erased->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;
}
核心判断
forward_list 只重连局部指针,不搬移其他节点:insert_after / emplace_after 不使任何已有 iterator 或 reference 失效;erase_after 仅使指向被删节点的 iterator 与 reference 失效,其余节点地址与位置完全稳定(与 vector 因扩容或搬移引发大范围失效截然不同)。
贯穿场景中按条件删除过期任务的标准写法如下:
#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;
}
}
}
该循环维持不变量 prev->next == cur:删除分支保持 prev 不动并用 erase_after(prev) 返回的新后继更新 cur;保留分支同步推进 prev = cur; ++cur;。
若需在当前任务后插入派生任务,当前 iterator it 本身即可作为前驱,插入后指向 it 与原后继的 iterator 均保持有效:
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;
}
}
}
前端便捷接口同样遵守前驱语义:push_front(val) 等价于 insert_after(before_begin(), val),pop_front() 等价于 erase_after(before_begin())。
14.3 forward iterator、size 缺席与遍历成本
forward_list 提供 forward iterator(支持解引用、相等比较、前后置递增与多遍遍历,不支持 -- 回退与 + n 随机跳跃),对应三类操作成本:
- 顺序扫描(如按条件查找):
O(n)沿next推进。 - 已知前驱的局部修改(
insert_after、erase_after):O(1)改写指针。 - 未持前驱的值定位修改(如“删除值等于 7 的首节点”):先
O(n)从头定位前驱,再O(1)改链。
std::find_if 仅要求前向遍历能力,因此可直接用于 forward_list,每次递增沿 next 前进,整体耗时与元素数成正比:
#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();
}
forward_list 刻意不提供成员 size(),以维持仅持有一个头前位置的“零额外空间开销”模型:若保存计数字段,每次 insert_after、erase_after、splice_after、merge、remove、unique 都必须同步维护计数并增加操作开销。获取长度需调用 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());
}
下面这种限流判断是常见的性能陷阱:
#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;
}
边界与误区
std::distance 面对 forward iterator 会逐节点递增计数(O(n)),只有 random access iterator 才能通过相减在 O(1) 内求距。若在循环内调用 has_too_many_jobs,总复杂度会退化为 O(n^2)。
若业务需频繁校验长度,有两种直接改法:
- 扫描短路:遍历时顺带累加计数,一旦超过
limit立即返回,避免扫完整个链表。 - 外置计数:由业务层在入链/出链位置自行维护长度状态(需自担一致性责任)。
14.4 内存开销、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() |
| 空间开销 | 每节点少一个链接指针 | 每节点多维护一个反向链接 |
| 访问模式 | 适合单向扫描 | 适合双向遍历和当前位置删除 |
评估内存与运行成本时,需把“同为节点式”与“连续存储”分成两层对比:
- 对比
list:forward_list每节点省一个反向指针,但两者均按元素独立分配,都要承担分配器元数据与对齐填充开销。 - 对比
vector:节点地址分散,CPU 无法像顺序数组那样硬件预取相邻元素;在热路径上,指针追踪(pointer chasing)导致的缓存未命中往往会抵消省去一个指针字段的空间收益。
根据访问与修改特征选型:
| 业务特征 | 推荐容器 | 核心原因 |
|---|---|---|
| 单向扫描中局部增删、需稳定节点地址、元素较大且极少查长度 | forward_list | 每节点省一个指针,常见于空闲块链、单向任务过滤链、轻量 intrusive 风格链 |
| 需从当前位置直接删除、向前回退或双向遍历 | list | erase(it) 无需维护前驱,避免从头重扫 |
需下标随机访问、频繁调用 size() 或追求排序与遍历局部性 | vector / deque | 连续或分段存储具备缓存局部性与 O(1) 长度查询 |
回到贯穿场景:任务链表天然从头到尾单向处理且易于维护 prev,因此适合 forward_list;若需求转为“从任意任务回溯上一个依赖任务”,单向链表会退化为反复从头扫描,此时应改用 list 或索引结构。
排查顺序
- 核对遍历方向:确认访问与扫描严格单向。
- 核对前驱获取:确认所有修改点都能稳定拿到前驱位置。
- 核对长度查询:确认长度统计足够低频,或可在扫描中顺带截断计数。
- 核对空间与局部性:确认节点地址稳定性与少一个指针的收益高于缓存局部性损失。
14.5 mini forward_list 实现路径
将前文对象模型落为最小实现骨架,按“无值基节点 / 带值节点 → 单指针 iterator → 头前哨兵容器”三层组织。
先分离无值的 mini_forward_node_base 与带值的 mini_forward_node<T>,避免 before_begin 构造无意义的用户对象:
#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 仅持有一个 mini_forward_node_base*,operator* 通过 static_cast 向下转型访问 value;因此 before_begin() 与 end() 只能参与 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_;
}
};
容器主体内嵌头前哨兵 before_:before_begin() 返回 &before_,begin() 返回 before_.next,end() 返回 nullptr:
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;
}
};
边界与误区
mini_forward_list 仅保留核心链接路径,未展开拷贝/移动语义、allocator propagation 及节点构造失败回滚;调用 erase_after(pos) 时,调用方仍须保证 pos 后存在有效元素。
将贯穿场景放回该容器,注意 after 插入位置完全由传入 iterator 决定:
mini_forward_list<Job> pending;
auto prev = pending.before_begin();
pending.emplace_after(prev, Job{1, false});
pending.emplace_after(prev, Job{2, true});
两次都传入 before_begin() 时,Job{2, true} 会插在 Job{1, false} 之前(头插效果);若要保持追加顺序,必须把 emplace_after 返回的新节点 iterator 保存为下一次的 prev。
排查顺序
- 头前状态:定位容器内嵌的无值控制节点或等价头指针封装。
- 节点分层:查看带值节点如何在基础链接节点上附加
value。 - iterator 状态:核对 iterator 是否仅保存单节点指针及沿
next递增。 - 链接提交点:定位
insert_after、erase_after、splice_after何处完成重连与所有权移交。
最小自检任务
阅读下面的代码,判断循环删除逻辑是否正确,并说明每次删除后 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;
}
}
}
本章知识点总结
- 单向节点
节点仅存值与
next指针,无反向链接,回溯前驱必须从头扫描。 - 头前哨兵
before_begin()提供不可解引用的首元素前驱位,将头插/头删与中间修改统一为after语义。 - 前驱修改语义
insert_after先接旧后继再改前驱完成提交;erase_after先暂存、再跨接、后销毁释放。 - 失效边界
插入不使已有 iterator 或 reference 失效;删除仅使指向被删节点的 iterator 与 reference 失效。
- 前向能力与无 size()
只提供 forward iterator,省去成员
size()以免跨接口维护计数;std::distance需O(n)遍历。 - 空间与局部性取舍
相对
list每节点少一个指针,但仍承担独立分配与指针追踪成本,热路径局部性弱于vector。 - 源码定位路径
依次核对头前控制位、无值/带值节点分层、iterator 单指针状态与
after操作的链接提交点。