std::forward_list<T> is a singly-linked list added in C++11: each node stores one element and a single pointer to the next node, with no back-pointer. It exists as a deliberately minimal container that matches the size and behaviour of a hand-written C linked list, trading away a lot of conveniences (no size(), no push_back, no back) for the smallest possible per-node footprint. This chapter covers the node layout, the surprising API quirks that follow from being singly-linked, the before_begin family of operations, the member algorithms (splice_after, merge, sort, remove, reverse, unique), and how to pick between forward_list and std::list.

A forward_list<T> node holds one T and one pointer to the next node. That's it. There is no previous pointer, no end-of-list sentinel pointer per node, and no per-node bookkeeping like a length counter.

The teal block is a conceptual "before-begin" sentinel that the implementation keeps to provide a handle for inserting before the first real element. The cyan boxes are the actual nodes, each carrying its value and a next pointer. The last node's next is null, which is how the end is detected.

Compare that with a std::list node, which carries two pointers (next and prev) plus the value. For a list of small values, the pointer overhead alone can dominate memory use. A forward_list<int> node is typically 4 + 8 = 12 bytes on a 64-bit system (often padded to 16); a std::list<int> node is 4 + 16 = 20 bytes (often padded to 24). With millions of nodes of small values, that ratio matters.

forward_list also drops the per-container size counter that std::list keeps. That choice lets the container shrink to one head pointer, but it has a visible consequence: there is no size() member, because computing it would mean walking the list.

forward_list has no size() because the only way to get it is an O(n) traversal. The container deliberately refuses to provide an operation whose cost would surprise readers. Use std::distance(list.begin(), list.end()) for the count.

The minimum to get a forward_list running:

The braced initialiser list works the same way it does on std::vector or std::list. Range-based for traverses the list by following next pointers internally. The order matches the order of the initialiser: the front of the list is the first element.

Many C++ programmers reach for std::vector first, std::deque second, and one of the linked variants only with a specific need. Given that, why ship a singly-linked list at all when std::list is already in the standard library?

Three reasons drove the C++11 addition:

The trade-off is that several operations that a doubly-linked list can perform in O(1) become either O(n) or simply unavailable on a singly-linked list. The committee chose not to paper over that with hidden traversals. If an operation would cost O(n), forward_list either doesn't provide it or provides it under a name that makes the cost obvious.

Three operations are absent from forward_list for the same underlying reason: they would each require an O(n) traversal that a doubly-linked list can avoid by keeping extra state.

The container can offer push_front, pop_front, and front in O(1) because it always has a handle to the head node. Anything that needs the tail or a previous link costs a traversal, and the API doesn't pretend otherwise.

push_front allocates one node and rewires the head pointer. pop_front unlinks the head node and deletes it. Both are constant time. There is no symmetric push_back; a push_back-shaped operation on a forward_list requires walking to the end and using insert_after, covered below.

Frequent reaches for push_back on a forward_list are a signal that std::list (doubly-linked, O(1) push_back) or std::vector (contiguous, amortised O(1) push_back) is the better fit.

The big API consequence of being singly-linked is that modifying a list at the position of a given iterator isn't easy. Unlinking the node an iterator points to would require a pointer to the previous node, to redirect its next pointer past the one being removed. With only forward links, the iterator alone can't help.

forward_list solves this by exposing two related iterators and providing operations that work on the position after a given iterator:

The mutation operations on forward_list come in _after flavours:

Insertion at the front uses before_begin as the prior-node handle.

before_begin() is the cleanest way to express "insert at the very front" using the _after family. The second insert goes between the first and second real elements: insert_after(first, ...) places its argument immediately after *first.

Erasing works the same way. To remove a node, pass an iterator to the node before the one to remove.

To remove the head, erase after before_begin(). That symmetry, with before_begin as the prior-node handle for the first element, keeps every mutation operation uniform: every removal needs a handle to the previous node, and the sentinel provides one for the front.

emplace_after builds the new node in place by forwarding its arguments to the element's constructor, which avoids constructing a temporary and then moving from it. For cheap types like std::string it rarely shows up in a microbenchmark, but for larger types or types with non-trivial constructors it can be worthwhile.

The forwarded constructor arguments build the Product directly inside the new node. No temporary Product is constructed and then moved.

forward_list provides several member functions that mirror the ones on std::list, with the same names where the singly-linked structure doesn't change the semantics, and with _after suffixes where it does.

splice_after

splice_after moves nodes from one list to another without copying or reallocating. Because nodes are linked by pointers, splicing only rewires a few next pointers; the elements themselves stay put in memory.

After the splice, wishlist is empty because its nodes have been transferred. The strings themselves were never copied; only the next pointers connecting them changed. Compare this with std::vector::insert of one vector into another, which copies (or moves) every element.

splice_after(pos, other) is O(1) when moving the entire other list. The overloads that splice a specific range or a single element are also O(1) once the iterators are available, but forward_list doesn't track size, so a range splice doesn't update any internal counters (there are none to update).

Three overloads to know:

The half-open range here is (first, last): the element immediately after first up to but not including last. The convention follows the _after pattern that runs through the whole API.

merge

merge merges another sorted list into this list, keeping the result sorted. Both lists must already be sorted under the comparator (default operator<). After the merge, other is empty.

Like splice_after, merge rewires pointers instead of copying. The two lists are walked in tandem and the smaller head node is linked to the result until one list runs out.

sort

sort sorts the list in place under the comparator (default operator<). The standard guarantees O(n log n) and stability. The algorithm header's std::sort does not work on a forward_list, because std::sort needs random-access iterators and forward iterators are not random access. The member function exists specifically because the algorithm version can't.

A comparator sorts in another order.

forward_list::sort is O(n log n) and works by repeatedly merging sorted sub-runs (essentially a list-friendly merge sort). It doesn't allocate because it only rewires pointers.

remove and remove_if

remove(value) removes every element equal to value. remove_if(predicate) removes every element for which the predicate returns true. Both walk the list once and unlink matching nodes.

The remove-then-erase idiom that the algorithm header forces on std::vector doesn't apply here. The member function actually deletes the nodes, which is fine because there's no contiguous storage to maintain.

reverse

reverse reverses the order of the list in place by walking the nodes and flipping each next pointer. No allocation, no element copies.

unique

unique removes consecutive duplicates. To remove all duplicates regardless of position, sort first and then call unique.

The first call leaves the 2 2 at the end because the earlier 2 was not adjacent. After sorting, all the 2s are next to each other and unique collapses them.

This is the question to settle before picking forward_list for real code. For most application code, std::list is the better choice when a linked list is the right structure, and a contiguous container (std::vector, std::deque) is usually better than either.

When `forward_list` is the right choice:

When `std::list` is the right choice:

When neither is the right choice (which is most of the time):

The summary: forward_list is a specialist tool. Without a specific reason to pick it over std::list, pick std::list. Without a specific reason to pick std::list over std::vector, pick std::vector.

A small program uses a forward_list as a queue of orders being processed. It builds the list, sorts by total, filters out free orders, and splices a batch of new orders in.

The sort orders the pipeline by total. remove_if walks once and unlinks ORD-4 (total $0). The splice moves both orders from nextBatch to just after the first element of the sorted pipeline. The new batch's nodes weren't copied; only next pointers changed. The output ordering reflects the splice position rather than the totals because the splice is unconditional. For a fully sorted result, sort the merged result or use merge on a sorted batch.

Iterator invalidation rules for forward_list are almost trivially simple, which is one of the few wins it has over contiguous containers.

Inserting a node in the middle of a list doesn't move any other node in memory, so every iterator into the list except the one to the erased element keeps pointing at the same node. This is the same property std::list has, and it's a real reason a linked structure is sometimes the right pick: pointers and iterators to elements stay valid across mutations.