Skip to content
Tutorials Center
My learning

Topics

C++ Reference ยท Containers

C++ std::forward_list class

Reference for std::forward_list: a singly linked list with insert_after, erase_after, before_begin, splice_after, sort and remove, and no size() member.

std::forward_list<T> is a singly linked list: each node knows only its successor. It is designed to have almost no overhead compared with a hand-written C list, so it has no size() member, no push_back() and no way to step backwards. You can only insert or erase after a given position, which is why the interface has insert_after, erase_after, emplace_after and splice_after.

To make an insertion at the very front possible with the same interface, the container offers before_begin(), an iterator to a position that is just before the first element. You can increment it but never dereference it.

C++
#include <forward_list>
std::forward_list<int> f = {2, 3};
f.push_front(1);          // 1 2 3
f.insert_after(f.before_begin(), 0);   // 0 1 2 3

Try it

C++ insert_after and erase_after

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

C++ sort, reverse, unique, remove and splice_after

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Syntax

C++
template <class T, class Allocator = std::allocator<T>>
class forward_list;

iterator before_begin() noexcept;      // also cbefore_begin()
void push_front(const T&);   void pop_front();
iterator insert_after(const_iterator pos, const T& v);
template <class... A> iterator emplace_after(const_iterator pos, A&&...);
iterator erase_after(const_iterator pos);                    // one element after pos
iterator erase_after(const_iterator first, const_iterator last);
void splice_after(const_iterator pos, forward_list& other);  // plus single-element and range overloads
size_type remove(const T&);   size_type remove_if(Pred);     // sizes returned since C++20
void sort();   void reverse() noexcept;   size_type unique();   void merge(forward_list&);
Name Description
pos The element after which to insert, erase or splice. May be before_begin().
first, last For the range overload, erases the open range (first, last).
other List whose nodes are moved into this one.

Returns: insert_after and emplace_after return an iterator to the new element; erase_after returns the iterator after the removed element(s).

Errors / undefined behavior: calling erase_after(pos) when pos is the last element or end() is undefined, as is dereferencing before_begin() or calling front() / pop_front() on an empty list.

Usage notes

  • No size(): it would require a counter in every list. Use std::distance(f.begin(), f.end()) (O(n)) and empty().
  • No push_back or backward iteration: appending means walking to the end first. If you need that, use std::list or a vector.
  • Operations act on the next node: to erase the element an iterator points at, you need the iterator to the element before it. Keep a "previous" iterator in loops that erase, starting from before_begin().
  • Stable iterators to surviving elements, like std::list.
  • Complexity: push_front / insert_after / erase_after are O(1); sort() is O(n log n) and stable; remove and unique are O(n).
  • Memory: one pointer per node, smaller than std::list. Still one allocation per element and poor cache behavior.
  • Member functions again: use f.sort(), not std::sort, which needs random access.
  • Rarely the best choice: it is useful for memory-tight code, hash-table buckets and algorithms that only ever push and pop at the front.