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,时间复杂度是 O(n)O(n)。

before_begin() 返回一个位于首元素之前的特殊迭代器。它不能解引用,但可以作为 insert_after() 或 erase_after() 的位置参数。这样,插入或删除首元素也能和处理中间节点使用同一套“操作后继节点”的规则。

forward_list 与 list 的链接和操作位置对比

用 before_begin 修改首部附近元素

下面先在链表头部插入 10,再让指向首元素的迭代器删除它后面的 20。注意,erase_after(pos) 删除的是 pos 的后继节点,而不是 pos 自己。

cpp
#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';
}

预期输出

text
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 或其他连续存储容器,而不是链表。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

forward_list 适合什么场景

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通