Skip to content
Tutorials Center
My learning

Topics

Lesson 97 of 171 ยท The Standard Library (STL)

std::deque, std::list and std::forward_list

Learn C++ std::deque, std::list and std::forward_list - how they store elements, O(1) operations, splice, iterator stability and the real cost of node-based containers.

std::vector is the default sequence container, and for good reason. But it has one weakness: it's only fast at the back. Insert at the front or in the middle and every element after that point has to shift. The standard library offers three other sequence containers that make different trade-offs: std::deque is fast at both ends, while std::list and std::forward_list can insert and erase anywhere in constant time and never move their elements.

Those guarantees come at a price that the Big-O tables don't show: scattered memory, a heap allocation per element and slow traversal. In this lesson you'll learn how each container is built, which operations are cheap, the special tricks only linked lists can do (like splice), and how to measure whether the trade is worth it. The short version, which you'll verify yourself: reach for deque when you need a double-ended queue, and for list only when you need stable iterators or splicing, not merely "lots of inserts".

std::deque: a double-ended queue

A std::deque<T> (pronounced "deck", from double-ended queue, header <deque>) supports everything a vector does at the back, plus push_front, emplace_front and pop_front, all in O(1). It still has operator[] and at() for random access.

The trick is its storage. Instead of one block, a deque keeps a sequence of fixed-size chunks and a small index (the "map") of pointers to them. In GCC's library each chunk holds 512 bytes, so 128 ints. Pushing at the front fills the first chunk backwards and adds a new chunk when it's full; pushing at the back does the mirror image. Existing elements never move when you add at either end.

C++ A deque grows at both ends

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.

After 20,000 insertions the element 20 hasn't moved: the pointer to it still works. That is a guarantee a vector can't give. The precise invalidation rules for a deque are a little unusual:

  • push_front, push_back and their emplace versions invalidate all iterators, but no references or pointers to elements. (The chunk index may be reallocated, which breaks iterators, but the chunks themselves stay put.)
  • pop_front and pop_back invalidate only the removed element (and end() for pop_back).
  • insert or erase in the middle invalidates everything. Middle operations are O(n), like a vector's, though the deque shifts whichever side is shorter.

When a deque fits

  • Queues and sliding windows. Add at one end, remove at the other. std::queue uses a deque by default (see Container Adapters).
  • Large collections that must not move. Elements keep their addresses while the deque grows at the ends, and growth never copies the existing elements.
  • Undo histories with a size limit: push_back new actions, pop_front the oldest when full.
C++ A sliding window over sensor readings

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.

What a deque gives up compared with a vector: its elements are not contiguous, so there's no data() and no conversion to std::span; indexing costs an extra indirection; and there's no reserve or capacity. Even a small deque allocates its chunk index plus one 512-byte chunk, so a deque of three ints is much bigger than a vector of three ints. For pure back-insertion, a vector remains faster.

std::list: a doubly linked list

A std::list<T> (header <list>) stores every element in its own heap-allocated node with pointers to the previous and next nodes. That design gives it guarantees no other sequence container has:

  • Insert and erase anywhere in O(1), given an iterator to the position.
  • Nothing ever moves. Iterators, pointers and references to an element stay valid until that element itself is erased, no matter what else you insert or remove.
  • Splicing: moving nodes from one list to another (or within a list) in O(1) by relinking pointers, without copying, moving or allocating anything.

The cost: no operator[] (reaching element i takes i steps), bidirectional iterators only (so std::sort doesn't work; use the member sort()), and two pointers of overhead per element plus a separate allocation.

Member algorithms

Because general algorithms like std::sort need random access, and because a list can do some jobs more cleverly by relinking nodes instead of moving values, std::list has its own member versions:

Member What it does
sort(), sort(comp) Stable merge sort by relinking nodes, O(n log n); iterators stay valid
merge(other) Merges another sorted list into this one; other ends up empty
unique() Removes consecutive duplicates; returns how many (C++20)
remove(value), remove_if(pred) Erases matching elements; returns how many (C++20)
reverse() Reverses the links
splice(pos, other, ...) Moves one node, a range, or a whole list to before pos
C++ Splicing nodes between lists

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.

Notice that the iterator bug keeps working after the node moved to another list; it now points into done. Splicing between two lists with different allocators is undefined behavior, but with the default allocator that never comes up.

A real use: an LRU cache

The textbook job for std::list is a least-recently-used cache: a list keeps keys in order of use, and a hash map stores, for each key, an iterator to its node. On every access you splice the node to the front in O(1); when the cache is full, you evict from the back. Iterator stability is what makes this work: the map's stored iterators stay valid while nodes move around.

C++ An LRU cache with list and unordered_map

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.

The cache uses std::optional for "maybe a value" and std::unordered_map for the index; both get their own lessons soon.

std::forward_list: the minimal singly linked list

std::forward_list<T> (header <forward_list>, C++11) is a singly linked list designed to have zero overhead over a hand-written C list: one pointer per node and no stored size. That minimalism shapes its interface:

  • There's no size() (use std::ranges::distance(fl), which is O(n)), no back() and no push_back.
  • Since a node only knows its successor, you insert and erase after a position: insert_after, emplace_after, erase_after, splice_after.
  • before_begin() returns an iterator to a position before the first element, so insert_after(fl.before_begin(), x) inserts at the front.
C++ Working after positions in a forward_list

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.

Use forward_list when you have huge numbers of short lists (for example, hash buckets or adjacency lists in a sparse graph) and the extra pointer of std::list matters. In ordinary application code it's rare.

The real cost of node-based containers

On paper, inserting into the middle of a list is O(1) and into a vector is O(n). In practice that comparison misleads, for three reasons:

  1. You have to find the position first. Finding the 5,000th element of a list takes 5,000 pointer hops. Unless you already hold an iterator, list insertion is O(n) too.
  2. Pointer chasing is slow. Each hop is a load from an unpredictable address, often a cache miss costing as much as dozens of instructions. A vector's elements arrive in the cache in contiguous lines, and the CPU prefetches the next ones.
  3. Every node is an allocation. A std::list<int> node holds 4 bytes of data plus 16 bytes of pointers, and the allocator adds its own bookkeeping and alignment. Memory use is often 6 to 8 times that of a vector, and allocating and freeing nodes takes time.

Measure it. The program below fills both containers with the same numbers, sums them, and then performs sorted insertions (find the position by walking, then insert) in each:

C++ vector versus list in practice

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.

Your exact numbers will vary from run to run, but the pattern is reliable: the vector wins both tests, often by a wide margin, even though the second one is supposedly the list's specialty. (Here the list's nodes were allocated in order, which is the best case for it; after many random inserts and erases, its nodes end up scattered and traversal gets slower still.) With a sorted vector you could also find the position with binary search (std::lower_bound), which a list can't do at all.

Choosing a sequence container

Need Choose
A general-purpose sequence; appends; random access; fast iteration std::vector
Fast insertion and removal at both ends; queues; elements that keep their address while growing at the ends std::deque
Iterators and references that must stay valid through any insert/erase; O(1) splicing between lists; huge elements you never want to move std::list
Same as list but minimal memory, front-only operations std::forward_list
Fixed size known at compile time std::array

When in doubt, start with a vector and measure. The Writing Fast C++ lesson comes back to cache-friendliness in more depth.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. You hold a pointer to an element of a std::deque and then call push_front 1,000 times. What is true?

    Insertion at either end of a deque never moves existing elements, so pointers and references survive. The internal chunk index may be reallocated, which invalidates iterators.
  2. 2. Why can't you call std::sort on a std::list?

    std::sort requires random-access iterators. Use the member function list.sort(), which is a stable merge sort that relinks nodes.
  3. 3. std::list<int> a{1, 2, 3}, b{9}; auto it = a.begin(); b.splice(b.end(), a, it); What does b contain and what does it refer to?

    splice moves exactly the node at it to before b.end(), so b becomes {9, 1}. No element is copied, and the iterator stays valid; it now points into b.
  4. 4. How do you insert a value at the front of a std::forward_list using insert_after?

    before_begin() is a special position before the first element. Inserting after it puts x first (push_front does the same).
  5. 5. Inserting 5,000 values in sorted position (found by linear search) into a vector and into a list. Which is typically faster and why?

    Finding the position dominates, and walking a list is a cache miss per node. The vector's search and memmove run over contiguous memory, so it usually wins clearly.

Summary

  • std::deque stores elements in fixed-size chunks: O(1) push and pop at both ends, O(1) random access, and growth at the ends never moves elements (but invalidates iterators).
  • std::list is doubly linked: O(1) insert and erase at a known position, iterators that stay valid until their element is erased, and O(1) splice between lists.
  • Lists have member sort, merge, unique, remove_if and reverse, because the generic algorithms need random access or would move values instead of relinking.
  • std::forward_list is singly linked with no stored size; it works "after" positions, starting from before_begin().
  • Node-based containers pay for an allocation per element, extra memory and cache misses. In practice a vector often beats a list even at middle insertion, so measure before switching.

Next: Container Adapters: stack, queue and priority_queue, which build restricted, purpose-made interfaces on top of these containers.