std::forward_list & std::list in Practice

July 2026 · 22 min read

You now know how to build a linked list. The standard library has already built two, and they are worth knowing not because you should reach for them often — you usually should not — but because the few places they win, they win decisively, and for reasons that are invisible in Big-O. This post is about the real APIs: the _after family, the three faces of splice and its one nasty complexity cliff, the member algorithms that exist because std::sort cannot touch these containers, and the iterator-stability guarantee that is the actual reason to choose them.

What Each Container Actually Is

std::forward_list is a singly linked list, deliberately kept to the bare minimum: one pointer per node, and famously no size() member and no push_back. Both omissions are principled. A size() would cost either an extra word per list or an O(n) count; push_back would be an O(n) walk. The library refuses to ship either footgun and instead offers before_begin() and the _after operations.

std::list is a doubly linked list built as a ring around one sentinel node — exactly the design from Part 4. Every end operation (push_back, push_front, pop_back, pop_front) is O(1), it iterates in both directions, and since C++11 its size() is required to be O(1) (implementations keep a running count).

#include <forward_list>
#include <list>

std::forward_list<int> fl{1, 2, 3};   // singly linked: no size(), no back(), no push_back
std::list<int>         dl{1, 2, 3};   // doubly linked ring; size() is O(1) since C++11

dl.push_back(4);    dl.push_front(0);   // both O(1)
// fl.push_back(4);  // does not compile \u2014 forward_list has no push_back

The _after API Family

Because a forward_list iterator cannot reach the node before it, every mutating operation is expressed in terms of the position after a given iterator: insert_after, emplace_after, erase_after, and splice_after. The missing predecessor for the very first element is supplied by before_begin() — an iterator to a notional slot ahead of the first node, which is the dummy-head idea promoted to a first-class API.

std::forward_list<int> fl{1, 2, 3};
auto before = fl.before_begin();
fl.insert_after(before, 0);          // O(1) front insert -> 0 1 2 3
fl.erase_after(fl.begin());          // remove the element after 0 -> 0 2 3

This is not a quirk to memorise; it is the singly-linked structure showing through the interface. Anytime an API is entirely _after-shaped, you are looking at a container that only knows how to go forward.

splice: The O(1) Superpower and Its One Gotcha

splice is why std::list exists. It moves nodes from one list into another by relinking pointers — no allocation, no element copies or moves, and no iterator invalidation. It comes in three overloads:

std::list<int> a{1, 2, 3}, b{9, 8, 7};

a.splice(a.begin(), b);                       // (1) whole list: O(1); b becomes empty
a.splice(a.end(),   b, b.begin());            // (2) one element: O(1)
a.splice(a.end(),   b, b.begin(), b.end());   // (3) a range: see the catch below

Overloads (1) and (2) are unconditionally O(1). Overload (3), the range splice, hides a trap. Moving a range from a different list is O(n) in the length of that range, not O(1), because size() must stay O(1) on both lists — so the implementation has to std::distance(first, last) to know how much to subtract from the source count and add to the destination. Splicing a range within the same list stays O(1), because the total size does not change and no counting is needed.

The single most useful splice is the LRU move-to-front. Given an iterator it to a just-accessed node, promoting it to the most-recently-used position is one O(1) line that keeps it and every other iterator valid:

// Move the node at 'it' to the front of the same list, in O(1).
lst.splice(lst.begin(), lst, it);   // 'it' stays valid and now sits at the front

Pair a std::list<pair<Key,Value>> with an unordered_map<Key, list::iterator> and that one line is the whole heart of an LRU cache. Here is the list order after each access, capacity 3, most-recently-used at the front:

merge, sort, unique, remove_if, reverse

These containers ship member algorithms that the generic <algorithm> versions cannot provide, because the free functions assume you can move elements and, for sorting, index them randomly. A node-based list can do neither cheaply — but it can relink, which is exactly what the members do.

std::list<int> a{1, 4, 5}, b{2, 3, 6};

a.merge(b);        // both sorted -> 1 2 3 4 5 6; stable, O(n+m), b emptied, no allocation
a.sort();          // list's own bottom-up merge sort: stable, O(n log n), no allocation
a.unique();        // removes CONSECUTIVE equal elements; sort first for a global dedup
a.remove(3);       // erase every element == 3
a.remove_if([](int x){ return x % 2 == 0; });   // erase every element matching a predicate
a.reverse();       // relink in place, O(n), no allocation

Why not std::sort? std::sort requires random-access iterators — it needs to reach the i-th element in O(1) to partition. list and forward_list offer only bidirectional and forward iterators respectively, so std::sort(l.begin(), l.end()) does not even compile. The member sort is a bottom-up merge sort that repeatedly merges runs by splicing nodes, so it is stable and allocates nothing — it never moves an element, only relinks. This is the one place a linked list sorts competitively, because merge sort is naturally node-friendly.

Iterator and Reference Invalidation

This table is the real reason to choose these containers. For list and forward_list, insertion invalidates nothing at all, and erasure invalidates only handles to the erased element. Nothing else — not iterators, not references, not raw pointers — ever moves. No other standard sequence container can promise that.

If your code holds long-lived iterators, pointers, or references to elements while the container keeps mutating — a cache, a graph of nodes, an observer registry — this stability is worth more than all the cache-locality you give up. It is the guarantee, not the asymptotics, that should drive the choice.

Why the erase–remove Idiom Does Not Apply

On a vector you delete matching elements with the erase–remove idiom: v.erase(std::remove_if(v.begin(), v.end(), pred), v.end());. std::remove_if works by shifting surviving elements forward and returning the new logical end. That is precisely the wrong tool for a list: shifting means move-assigning values between nodes, which throws away the node identity and iterator stability you chose a list for.

// DON'T do this on a list \u2014 it moves values between nodes and defeats the point:
// lst.erase(std::remove_if(lst.begin(), lst.end(), pred), lst.end());

// DO use the member \u2014 it unlinks matching nodes directly, keeping every other
// iterator valid, in O(n) with no element moves:
lst.remove_if(pred);

The member remove/remove_if exists so that deletion is a pointer operation, not a value shuffle. Reach for it every time; the generic idiom is for contiguous containers.

Recovering Locality with pmr

The one honest complaint about std::list — every node is a separate heap allocation, so traversal is a pointer chase across scattered memory — has a practical fix. Give the list a polymorphic memory resource backed by a contiguous arena, and its nodes come out of one block with near-array locality and no per-node malloc:

#include <memory_resource>
#include <list>

std::byte buffer[1 << 16];
std::pmr::monotonic_buffer_resource pool{buffer, sizeof(buffer)};
std::pmr::list<int> lst{&pool};    // nodes carved from 'buffer', contiguously

for (int i = 0; i < 1000; ++i) lst.push_back(i);   // no per-node heap allocation

A monotonic_buffer_resource allocates by simply bumping a pointer and frees nothing until it is destroyed, so a freshly built pmr::list traverses almost as fast as a vector while keeping list's O(1) splice and iterator stability. When you need the guarantees but the profiler blames cache misses, this is the fix to try before abandoning the container.

When to Actually Use These

Check Yourself

Each item is a situation; pick the statement that is actually correct about the standard containers.

Practice

• LeetCode 146 — LRU Cache splice std::list + hash map; the move-to-front one-liner is the core.
• LeetCode 21 — Merge Two Sorted Lists merge hand-implement what list::merge does.
• LeetCode 148 — Sort List sort the bottom-up merge sort behind list::sort.
• LeetCode 23 — Merge k Sorted Lists merge repeated merging, exactly list::merge at scale.
• LeetCode 707 — Design Linked List api reproduce the container interface by hand.
• LeetCode 83 — Remove Duplicates from Sorted List unique the sort-then-unique pattern in miniature.