std::forward_list — Singly Linked List

Overview

std::forward_list<T> was introduced in C++11 to provide a standards-compliant singly-linked list. It trades bidirectional traversal for memory efficiency: each node stores only one pointer to the next element, unlike std::list which stores two (next and previous). This design delivers zero time and space overhead relative to a hand-written C-style singly linked list.

Singly-linked lists excel in scenarios requiring frequent front insertion or when you only iterate forward through the sequence once. However, they impose a harsh constraint: you cannot efficiently access the element before a position. This manifests in a unique API: operations like insert() and erase() become insert_after() and erase_after().

The container deliberately omits size(). Computing size on a singly-linked list requires traversing all elements (O(n)), so the standard chose not to cache it, enforcing conscious design decisions about when you need the count.

Syntax

#include <forward_list>

// Construction (C++11)
std::forward_list<int> fl;                    // empty
std::forward_list<int> fl = {1, 2, 3};        // brace initialization
std::forward_list<int> fl(other);             // copy
std::forward_list<int> fl(std::move(other));  // move

Key member functions:

// Front access (only)
fl.push_front(val);        // O(1)
fl.emplace_front(args...); // O(1), in-place construction
fl.pop_front();            // O(1)
fl.front();                // O(1), returns T&

// No back(), no size(), no operator[], no rbegin/rend

// Iteration (forward only)
fl.begin(); fl.end();      // forward iterators
fl.cbegin(); fl.cend();    // const forward iterators
fl.before_begin();         // virtual iterator before first element

// Insertion/erasure (after an iterator)
fl.insert_after(pos, val);              // O(1), insert after pos
fl.insert_after(pos, count, val);       // O(1) insertion time
fl.insert_after(pos, first, last);      // O(1) insertion time
fl.emplace_after(pos, args...);         // O(1), in-place
fl.erase_after(pos);                    // O(1)
fl.erase_after(pos, last);              // O(1)

// Splice (move elements, zero-copy)
fl.splice_after(pos, other);            // move all of other after pos
fl.splice_after(pos, other, it);        // move *it after pos
fl.splice_after(pos, other, first, last); // move range after pos

// Sorting and merging
fl.sort();                              // O(n log n), in-place
fl.merge(other);                        // merge two sorted lists, O(n)
fl.unique();                            // remove consecutive duplicates, O(n)
fl.reverse();                           // O(n)

Examples

Basic Front Operations

#include <forward_list>
#include <print>

std::forward_list<int> fl = {2, 3, 4};

// Fast front insertion
fl.push_front(1);
fl.emplace_front(0);  // constructs 0 in-place
// fl = {0, 1, 2, 3, 4}

// Fast front removal
fl.pop_front();
// fl = {1, 2, 3, 4}

std::println("front: {}", fl.front());  // 1

Insertion After (The Singly-Linked Twist)

std::forward_list<int> fl = {1, 2, 4, 5};

auto it = fl.begin();
++it;  // now points to 2

// Insert 3 after position pointing to 2
fl.insert_after(it, 3);
// fl = {1, 2, 3, 4, 5}

// Insert range after position
fl.insert_after(it, {10, 11});
// fl = {1, 2, 10, 11, 3, 4, 5}

// Erase element immediately after iterator
fl.erase_after(it);
// fl = {1, 2, 11, 3, 4, 5}

before_begin() for Front Manipulation

std::forward_list<int> fl = {2, 3, 4};

// before_begin() is a virtual iterator to the position before the first element
// Use it to insert or erase at the front via insert_after/erase_after

fl.insert_after(fl.before_begin(), 1);  // prepend 1
// fl = {1, 2, 3, 4}

fl.erase_after(fl.before_begin());       // remove front
// fl = {2, 3, 4}

Sorting and Merging Sorted Lists

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

a.sort();     // {1, 1, 3, 4, 5, 9}
b.sort();     // {2, 3, 5, 6}

a.merge(b);   // merge sorted lists into a; b becomes empty
// a = {1, 1, 2, 3, 3, 4, 5, 5, 6, 9}

// Remove consecutive duplicates (requires sorted list)
a.unique();
// a = {1, 2, 3, 4, 5, 6, 9}

Zero-Copy Splice

std::forward_list<int> src = {10, 20, 30};
std::forward_list<int> dst = {1, 2, 3};

auto pos = dst.begin();
++pos;  // position at 2

// Move all elements of src after position in dst (zero-copy)
dst.splice_after(pos, src);
// dst = {1, 2, 10, 20, 30, 3}
// src = {} (empty, no elements copied)

Best Practices

1. Use only when singly-linked semantics matter: If you never need size(), never traverse backward, and heavily manipulate the front, forward_list saves one pointer per node. This is rarely enough to justify the restricted API in practice.

2. Avoid computing size(): Since there is no size() member, each size computation requires O(n) traversal. Cache it yourself if needed, or redesign to avoid asking "how many?"

3. Prefer emplace_front() for construction: Both push_front() and emplace_front() are O(1), but emplace_front(args...) constructs the element in-place without temporaries.

4. Use splice_after() for bulk moves: When transferring sequences of elements between lists, splice_after() is zero-copy and vastly faster than erase-and-insert loops.

5. Remember insert_after and erase_after: The API intentionally lacks insert(pos, val) and erase(pos). Always use *_after variants to clarify singly-linked semantics and avoid subtle bugs.

6. Iterate once: Singly-linked lists suit one-pass algorithms. If you iterate multiple times or need random access, std::vector or std::deque will be faster.

Common Pitfalls

1. Forgetting before_begin(): Prepending or removing the front element can be done with push_front() or pop_front(), but generic manipulation at the front requires insert_after(before_begin(), ...) and erase_after(before_begin(), ...).

2. Assuming you can traverse backward: Iterators are forward-only; --it is illegal. No rbegin(), no rend(). If you need bidirectional traversal, use std::list.

3. Calling size() when it doesn't exist: There is no size() method. Each call would require a full traversal: O(n). Use empty() (O(1)) when possible, or cache the count yourself.

4. Expecting random access: operator[] and direct subscripting do not exist. Use std::next(it, k) to reach the kth element (still O(k)).

5. Splicing within the same list carelessly: Splicing elements within the same list can easily create logic errors or create cycles. Ensure the source and destination positions don't overlap unintentionally.

Performance Comparison

Choose forward_list only when the single-pointer-per-node savings justify the restricted API. In most cases, std::vector offers better cache locality and simpler iteration; std::list offers bidirectional traversal at the cost of one extra pointer per node.

before_begin and cbefore_begin: The Sentinel Iterator

Every mutating operation on forward_list — insert_after, erase_after, splice_after — takes an iterator to the element before the position of interest. For an insertion or erasure at the very front of the list, no element precedes the first one, so there is nothing to pass. before_begin() solves this by returning a special sentinel iterator that logically sits one step before begin().

std::forward_list<int> fl = {10, 20, 30};

// Insert 5 at the front — without before_begin() there is no "previous" to pass
fl.insert_after(fl.before_begin(), 5);
// fl = {5, 10, 20, 30}

// Remove the front element via erase_after
fl.erase_after(fl.before_begin());
// fl = {10, 20, 30}

cbefore_begin() is the const counterpart (returns a const_iterator). The sentinel iterator may never be dereferenced — doing so is undefined behaviour. Its sole purpose is to serve as the pos argument to *_after operations targeting the first position.

Why is this architecture necessary? A singly-linked node holds only a pointer to its successor. To splice or erase a node you must update the next pointer of the preceding node. When the target is the head node, the "preceding pointer" is the list's own head pointer, which is what before_begin() represents internally. This is also why forward_list has no insert(pos) or erase(pos) — those would silently require O(n) back-tracking to find the predecessor.

insert_after and emplace_after

insert_after(pos, ...) inserts one or more elements immediately after the element pointed to by pos, then returns an iterator to the last inserted element (not the iterator before it). This return value is intentional — it lets you chain multiple insertions efficiently without re-scanning from the beginning.

std::forward_list<std::string> fl = {"a", "d"};

auto it = fl.begin();   // points to "a"

// Single value — returns iterator to "b"
auto r1 = fl.insert_after(it, "b");
// fl = {"a", "b", "d"},  r1 -> "b"

// Insert a second element after "b"
auto r2 = fl.insert_after(r1, "c");
// fl = {"a", "b", "c", "d"},  r2 -> "c"

// Insert an initializer list — returns iterator to the last inserted element
fl.insert_after(fl.before_begin(), {"x", "y"});
// fl = {"x", "y", "a", "b", "c", "d"}

// Count overload: insert N copies
fl.insert_after(fl.before_begin(), 3, "!");
// fl = {"!", "!", "!", "x", "y", ...}

emplace_after(pos, args...) constructs the new element in-place directly inside the newly allocated node, forwarding args to the element's constructor. It returns an iterator to the constructed element.

struct Point { int x, y; };

std::forward_list<Point> pts;
auto it = pts.before_begin();

// Construct Point{1,2} in-place — no temporary created
it = pts.emplace_after(it, 1, 2);
it = pts.emplace_after(it, 3, 4);
// pts = { {1,2}, {3,4} }

Prefer emplace_after when constructing from individual constructor arguments; use insert_after when you already have a value or a range.

splice_after: Zero-Copy Node Transfer

splice_after moves nodes from one forward_list to another (or to a different position in the same list) by relinking pointers — no elements are copied or moved, and no memory is allocated or freed. All iterators to the transferred elements remain valid after the splice; they simply now belong to the destination list.

There are three overloads:

1. Move an entire list — O(n) because the end of other must be located to relink:

std::forward_list<int> src = {4, 5, 6};
std::forward_list<int> dst = {1, 2, 3};

auto pos = dst.begin();   // points to 1
++pos;                    // points to 2

dst.splice_after(pos, src);
// dst = {1, 2, 4, 5, 6, 3}
// src = {}   (all nodes moved)

2. Move a single element — O(1). The iterator it points to the element before the one to be transferred (same "after" convention):

std::forward_list<int> src = {10, 20, 30};
std::forward_list<int> dst = {1, 2, 3};

// Transfer the element after src.begin() — that is, 20
dst.splice_after(dst.before_begin(), src, src.begin());
// dst = {20, 1, 2, 3}
// src = {10, 30}

3. Move a half-open range (first, last) — O(n) in the number of elements transferred. Transfers all elements strictly between first and last (i.e. first and last themselves are not moved):

std::forward_list<int> src = {1, 2, 3, 4, 5};
std::forward_list<int> dst = {10, 20};

// Transfer elements 2, 3, 4 — those strictly after src.begin() up to (not including) the iterator pointing to 5
auto f = src.begin();      // points to 1  (not transferred)
auto l = std::next(f, 4);  // points to 5  (not transferred)

dst.splice_after(dst.begin(), src, f, l);
// dst = {10, 2, 3, 4, 20}
// src = {1, 5}

When splicing within the same list, take care that pos does not fall inside the transferred range — that produces undefined behaviour.

Memory Layout and the Missing size()

On a 64-bit platform each std::list<T> node carries two 8-byte pointers (next + prev) plus the element itself. Each std::forward_list<T> node carries only one 8-byte pointer. For a list of N integers the overhead difference is exactly N * 8 bytes — meaningful only when N is very large or when the element itself is very small (e.g. char or short).

#include <forward_list>
#include <list>
#include <cstdio>

// On a typical 64-bit implementation:
// sizeof(std::list<int>)         = 24  (head ptr + tail ptr + size counter)
// sizeof(std::forward_list<int>) = 8   (head ptr only — no tail, no count)
std::printf("list:         %zu bytes\n", sizeof(std::list<int>));
std::printf("forward_list: %zu bytes\n", sizeof(std::forward_list<int>));

forward_list deliberately omits size(). If the method existed, it would have to be either O(n) (traversing every node) or it would require storing a counter — and storing a counter would mean an extra 8 bytes in the list object plus the overhead of maintaining it on every insert and erase. The designers chose neither: the container stays as lean as a hand-written C singly-linked list. The standard committee documented this trade-off explicitly in N2543 (the original proposal).

To count elements when you must:

std::forward_list<int> fl = {1, 2, 3, 4, 5};

// O(n) — traverse every node
auto n = std::distance(fl.begin(), fl.end());

// O(n) — equivalent with ranges
auto m = std::ranges::distance(fl);

// O(1) — only ask whether the list is empty
bool empty = fl.empty();

If your algorithm genuinely needs the element count frequently, maintain it externally or reconsider whether forward_list is the right container.

Erasing While Iterating

Because every operation needs the iterator to the predecessor, erase-while-iterating requires tracking two iterators simultaneously — prev and curr — instead of the single iterator pattern that works with std::list::erase.

std::forward_list<int> fl = {1, 4, 2, 7, 3, 6};

// Remove all elements greater than 4
auto prev = fl.before_begin();
auto curr = fl.begin();

while (curr != fl.end()) {
    if (*curr > 4) {
        curr = fl.erase_after(prev);  // erase_after returns iterator to element after the erased one
        // prev stays the same — the next element is now curr
    } else {
        prev = curr;
        ++curr;
    }
}
// fl = {1, 4, 2, 3}

For common predicates, the member functions remove, remove_if, and unique eliminate the need to write this loop manually:

std::forward_list<int> fl = {1, 4, 2, 7, 3, 6};

// remove_if handles the prev/curr bookkeeping internally — C++20 returns the count removed
auto removed = fl.remove_if([](int v) { return v > 4; });
// fl = {1, 4, 2, 3},  removed == 2

std::forward_list<int> dups = {1, 1, 2, 3, 3, 3, 4};
dups.unique();   // removes consecutive duplicates
// dups = {1, 2, 3, 4}

remove and remove_if return forward_list::size_type (the number of elements removed) since C++20. In C++11/14/17 they return void.

When to Use forward_list vs list vs vector

The decision reduces to two questions: do you need pointer/iterator stability on insert, and how often do you traverse?

Choose forward_list when:

• Memory is extremely constrained and you need true singly-linked semantics (embedded systems, intrusive data structures modelled after forward_list).
• You build a list by prepending elements one-by-one and then iterate it once in O(n) — the classic "stack then scan" pattern.
• You must splice or merge large lists without copying elements.

Choose std::list when:

• You need bidirectional iteration (rbegin, rend, --it).
• You need O(1) size().
• You need to erase or insert at a known iterator position without tracking the predecessor.

Choose std::vector (almost always) when:

• You iterate the data more than once, or in tight inner loops — cache locality dominates.
• You need random access by index.
• The number of elements is stable or only grows at the back.

On a 64-bit machine with 4-byte int elements, the per-node memory cost is:

The gap between forward_list and list is one pointer per node — a saving of 8 bytes per element on 64-bit. For one million int nodes that is approximately 8 MB. For most applications that fit comfortably in memory, std::vector wins because it eliminates all per-node pointer overhead, and its sequential memory layout makes CPU prefetching dramatically more effective than either linked-list variant.

See Also

• std::list — Doubly-linked list with bidirectional iterators
• std::vector — Contiguous, cache-friendly dynamic array
• std::deque — Double-ended queue, fast at both ends
• Iterator categories — Forward, bidirectional, and random-access iterators