Ch9.6: forward_list

Overview

::fast_io::forward_list is unique among the containers because it uses an “insert after” model. Instead of inserting at an iterator, you insert after an iterator. This design avoids the need for a size() method and keeps the per-node overhead to a single pointer.

1. before_begin()

forward_list provides a before_begin() iterator that points to the position before the first element. This allows insertion at the very front of the list:


#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 Operations

All insertion and erasure operations on forward_list use the _after suffix:

Operation	Description
`insert_after(pos, val)`	Insert `val` after the element pointed to by `pos`
`emplace_after(pos, args...)`	Construct element in-place after `pos`
`erase_after(pos)`	Erase the element after `pos`
`erase_after(first, last)`	Erase range `(first, last)` (exclusive of `first`)
`splice_before_after(pos, beforeit)`	Move the element after `beforeit` to after `pos`
`reverse_after(beforeit)`	Reverse the subrange starting after `beforeit`
`sort_after(beforeit, cmp)`	Sort the subrange starting after `beforeit`
`merge_after(beforeit, other, cmp)`	Merge `other` into the subrange after `beforeit`

3. Complete Example


#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
}

Key takeaways

forward_list uses an “insert after” model.
before_begin() enables insertion at the very front.
All mutation operations use the _after suffix.
forward_list has no size() and no back().
Per-node overhead is only one pointer (vs two for list).