C++ Reference ยท Containers
C++ std::list class
Reference for std::list: constant-time insertion and removal anywhere, splice, merge, sort, unique and remove, stable iterators, and when a list beats a vector.
std::list<T> is a doubly linked list. Every element lives in its own heap-allocated node with a pointer to the previous and next node. Given an iterator, inserting or erasing at that position takes constant time, and no other element moves. Iterators and references to the remaining elements stay valid when you insert or erase, which is the container's main selling point.
The price is that there is no random access (list[3] does not exist), traversal is slow because nodes are scattered in memory, and each element carries two pointers of overhead. For most programs a std::vector is faster even for insert-heavy work. Reach for list when you need stable iterators, cheap splice between lists, or elements that cannot be moved.
#include <list> std::list<int> l = {1, 2, 3}; l.push_front(0); l.push_back(4); // 0 1 2 3 4
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 list; // Modifiers void push_front(const T&); void push_back(const T&); void pop_front(); void pop_back(); iterator insert(const_iterator pos, const T& v); iterator erase(const_iterator pos); template <class... A> reference emplace_front(A&&...); // also emplace_back, emplace // List operations void splice(const_iterator pos, list& other); // overloads for one element or a range size_type remove(const T& v); // returns count since C++20 template <class Pred> size_type remove_if(Pred p); size_type unique(); // consecutive duplicates void merge(list& other); // both lists must be sorted void sort(); void reverse() noexcept;
| Name | Description |
|---|---|
pos |
Iterator before which to insert or splice. |
other |
Another list whose nodes are moved into this one. |
v |
Value to insert or compare against. |
p |
Predicate that returns true for elements to remove. |
Returns: insert returns an iterator to the new element; erase returns the iterator after the removed one. Since C++20, remove, remove_if and unique return the number of removed elements (before that they returned void).
Errors / undefined behavior: front(), back(), pop_front() and pop_back() on an empty list are undefined. Using an iterator to an erased element is undefined. Allocation can throw std::bad_alloc.
Usage notes
- Complexity:
push_front,push_back,insertanderaseat a known position are O(1);size()is O(1) (guaranteed since C++11); finding an element is O(n);sort()is O(n log n). - Stable iterators: only the iterators and references to erased elements are invalidated. Everything else stays valid, even after
splice(the iterators then refer to the element in its new list). - Member functions, not algorithms: use
l.sort(),l.remove(x),l.unique()andl.reverse().std::sortneeds random-access iterators and does not compile on a list.std::removewould not actually shrink the list; the memberremovedoes. splicemoves nodes: it never copies or reallocates, so it works even for types that cannot be copied or moved, and it is O(1) for a whole list or a single element (a range is O(n) only because of the count update in some implementations).mergeassumes both lists are sorted with the same ordering and keeps it stable.- Memory: one allocation per element plus two pointers. Small elements pay a large overhead. Use
std::pmr::listor a custom allocator if allocations dominate. - Singly linked alternative:
std::forward_listuses less memory but only moves forward. - Cache behavior: traversing a list is typically several times slower than a vector of the same size, so profile before choosing it.