第9.6章: forward_list

概述

::fast_io::forward_list 在各容器中很特别，因为它采用“在之后插入”的模型：你不是在迭代器处插入，而是在迭代器之后插入。这种设计避免了提供 size() 的需要，并让每个结点的额外开销降到只有一个指针。

1. before_begin()

forward_list 提供 before_begin() 迭代器，它指向第一个元素之前的位置。这样就可以在链表最前面插入元素：


#include <fast_io_dsal/forward_list.h>
#include <fast_io.h>

int main() {
    ::fast_io::forward_list<::std::size_t> fl{10zu, 20zu, 30zu};

    // Insert at the front using before_begin()
    fl.insert_after(fl.before_begin(), 5zu);
    // fl is now {5zu, 10zu, 20zu, 30zu}

    // Emplace at the front
    fl.emplace_after(fl.before_begin(), 1zu);
    // fl is now {1zu, 5zu, 10zu, 20zu, 30zu}

    // cbefore_begin() for const context
    auto cbi = fl.cbefore_begin();
}

2. _after 系列操作

forward_list 上所有插入与删除操作都带 _after 后缀：

操作	说明
`insert_after(pos, val)`	在 `pos` 所指元素之后插入 `val`
`emplace_after(pos, args...)`	在 `pos` 之后就地构造元素
`erase_after(pos)`	删除 `pos`之后的元素
`erase_after(first, last)`	删除范围 `(first, last)`（不包含 `first`）
`splice_before_after(pos, beforeit)`	把 `beforeit` 之后的元素移动到 `pos` 之后
`reverse_after(beforeit)`	反转从 `beforeit` 之后开始的子范围
`sort_after(beforeit, cmp)`	对从 `beforeit` 之后开始的子范围排序
`merge_after(beforeit, other, cmp)`	把 `other` 合并进 `beforeit` 之后的子范围

3. 完整示例


#include <fast_io_dsal/forward_list.h>
#include <fast_io.h>

int main() {
    ::fast_io::forward_list<::std::size_t> fl{30zu, 10zu, 20zu};

    // Sort the entire list
    fl.sort();
    // fl is now {10zu, 20zu, 30zu}

    // Reverse the entire list
    fl.reverse();
    // fl is now {30zu, 20zu, 10zu}

    // Erase element after begin (removes 20)
    fl.erase_after(fl.begin());
    // fl is now {30zu, 10zu}

    // Erase range: erase everything after before_begin up to end
    fl.erase_after(fl.before_begin(), fl.end());
    // fl is now empty
}

要点

forward_list 采用“在之后插入”的模型。
before_begin() 使得在链表最前面插入成为可能。
所有修改操作都带 _after 后缀。
forward_list 没有 size()，也没有 back()。
每个结点的额外开销只有一个指针（而 list 是两个）。