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.
#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
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.
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
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. Usestd::distance(f.begin(), f.end())(O(n)) andempty(). - No
push_backor backward iteration: appending means walking to the end first. If you need that, usestd::listor 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_afterare O(1);sort()is O(n log n) and stable;removeanduniqueare 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(), notstd::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.