C++ 第29题：std::forward_list 单向链表极简内存占用与 insert_after 操作

题目

编写程序，演示 C++11 引入的单向链表容器 std::forward_list。验证其为达到与原生手写 C 单链表等同的极致轻量内存开销（每个节点仅多消耗一个 next 指针），因此不提供 size() 方法（保持 O(1) 空间）且不支持后向遍历；重点掌握其独有的 insert_after 和 erase_after 单链表指针拓扑操作。

输入格式：无需外部输入。

输出格式：输出 forward_list 单向链表构造、就地插入与遍历结果。

数据范围与约定：极简内存开销单向链表与 STL 零开销原则。

思路与算法

1. 为什么没有 size() 和 push_back()
若维护 size 会增加额外 8 字节结构体空间，若支持 push_back 需维护尾指针或退化为 O(N) 遍历。为践行“你不用就不为此付出代价”（Zero-overhead Principle），它只提供单向前进操作。

2. insert_after 的前驱机制
单链表插入节点必须修改待插入位置的前驱节点的 next 指针。因此标准库设计了 before_begin() 假头迭代器，用于支持在链表首个元素前插入。

3. 内存对比
std::list 每个节点存两个指针（prev 与 next），在 64 位下指针开销 16 字节；std::forward_list 仅 1 个指针（8 字节），减半指针负担。

完整程序

#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> flist = {10, 20, 30};

    // 1. 利用 before_begin() 在头部之前插入新首节点
    flist.insert_after(flist.before_begin(), 5); // 变成 5, 10, 20, 30

    // 2. 查找值为 10 的节点并在其后方插入 15
    for (auto it = flist.begin(); it != flist.end(); ++it) {
        if (*it == 10) {
            flist.insert_after(it, 15);
            break;
        }
    }

    std::cout << "--- 1. insert_after 拓扑插入后的链表序列 ---\n";
    for (int x : flist) {
        std::cout << x << " -> ";
    }
    std::cout << "nullptr\n\n";

    // 3. 删除 15 之后的节点（删除 20）
    auto target = flist.begin();
    while (target != flist.end() && *target != 15) {
        ++target;
    }
    if (target != flist.end()) {
        flist.erase_after(target); // 删去 15 后面的 20
    }

    std::cout << "--- 2. erase_after 删除 20 后的链表序列 ---\n";
    for (int x : flist) {
        std::cout << x << " -> ";
    }
    std::cout << "nullptr\n";

    return 0;
}

运行示例

输出：

--- 1. insert_after 拓扑插入后的链表序列 ---
5 -> 10 -> 15 -> 20 -> 30 -> nullptr

--- 2. erase_after 删除 20 后的链表序列 ---
5 -> 10 -> 15 -> 30 -> nullptr