C / C++ / 系统课时
forward_list 适合什么场景
forward_list 适合什么场景
std::forward_list 是 STL 中的单向链表。它牺牲反向遍历、尾部直接操作和 size() 等能力,换取更精简的链接结构。本节通过 before_begin()、insert_after() 和 erase_after() 理解它的操作方式,并判断什么时候它比 std::list 更合适。
学习目标
- 理解
forward_list的单向链接结构及其能力边界 - 会使用
before_begin()配合insert_after()、erase_after()修改链表 - 能根据遍历方向、修改位置和节点开销在
forward_list与list之间选择
单向结构决定了接口
forward_list 的逻辑结构中,每个节点只需要记录后继节点,因此迭代器只能向前移动。它没有 back()、push_back(),也没有成员函数 size();如果必须统计元素数量,需要遍历整个链表,例如使用 std::distance,时间复杂度是 。
before_begin() 返回一个位于首元素之前的特殊迭代器。它不能解引用,但可以作为 insert_after() 或 erase_after() 的位置参数。这样,插入或删除首元素也能和处理中间节点使用同一套“操作后继节点”的规则。

用 before_begin 修改首部附近元素
下面先在链表头部插入 10,再让指向首元素的迭代器删除它后面的 20。注意,erase_after(pos) 删除的是 pos 的后继节点,而不是 pos 自己。
#include <forward_list>
#include <iostream>
int main() {
std::forward_list<int> values{20, 30};
// before_begin 不能解引用,但适合统一处理首元素之前的位置。
values.insert_after(values.before_begin(), 10);
auto first = values.begin();
values.erase_after(first); // 删除 first 后面的 20
bool first_output = true;
for (int value : values) {
if (!first_output) {
std::cout << ' ';
}
std::cout << value;
first_output = false;
}
std::cout << '\n';
}预期输出
10 30如果要删除首元素,可调用 erase_after(before_begin())。如果需要在某个目标节点之前插入,则必须提前保留它的前驱迭代器;这正是单向链表和双向链表在使用习惯上的核心差异。
与 list 的选择差异
| 需求 | forward_list |
list |
|---|---|---|
| 遍历方向 | 仅向前 | 向前、向后 |
| 节点链接 | 通常只需要后继链接 | 通常需要前驱和后继链接 |
| 尾部直接操作 | 不提供 back()、push_back() |
提供 back()、push_back() |
| 元素个数 | 无成员 size(),统计需遍历 |
提供 size() |
| 插入删除接口 | 主要围绕“当前位置之后” | 可在迭代器位置前插入,并直接删除当前位置 |
forward_list 的优势主要是更小的链接开销和明确的单向访问模型,但标准并不规定每个节点具体占多少字节,实际内存还会受到分配器和对齐影响。因此不要仅凭“少一个链接”就假定它一定显著省内存,应结合真实数据量做测量。
什么时候适合使用
当数据天然只需要从前向后扫描,频繁操作发生在已知前驱之后,而且不需要尾部访问和反向遍历时,forward_list 很合适,例如轻量级空闲链、只向前扫描的邻接记录或按前驱位置频繁插删的内部链。
如果业务经常需要从当前节点回退、在尾部追加、直接查询元素数量,或者代码更重视接口便利性,std::list 往往更直接。若主要需求是随机访问、缓存局部性和顺序遍历性能,则应优先考虑 std::vector 或其他连续存储容器,而不是链表。