skip to content

STL Containers

vector, map, unordered_map and their siblings each have a cost model and invalidation rules. Interviewers expect you to pick vector by default and say why.

on this pageshow

explore

questions

page 1 of 2

In C++, when does std::list actually beat std::vector, and what does each list element cost in memory and access?

level: juniorimportance: must knowfreq 72%

answer

  1. one heap node per element
  2. two pointers beside every value
  3. no operator[], no std::sort
  4. elements that never move

basics

~20 s

std::list wins when you need elements that never move, iterators that survive other insertions and erasures, or constant-time splicing between lists. Each element is a separately allocated node carrying two pointers, and there is no random access.

solid answer

~50 s

`std::list<T>` is a doubly linked list: every element lives in its own heap node that also stores a previous and a next pointer (libc++ and libstdc++ both lay nodes out this way), so a list of `int` spends more memory on pointers than on data, and every insertion is an allocation. Its iterators are bidirectional only: there is no `operator[]`, no `data()`, and `std::sort` does not compile on it, which is why it has a member `sort()`. In return, inserting or erasing at an iterator you already hold is constant time and leaves the other elements untouched; `splice` relinks nodes between lists without copying; and elements never move, so `std::list<std::mutex>` works where a growing `std::vector<std::mutex>` does not compile. Pick it for those guarantees, such as the recency order of an LRU cache. For storing and scanning data, `std::vector` remains the default.

code

cpp · 19 lines
cpp
#include <cstdio>
#include <forward_list>
#include <iterator>
#include <list>

int main() {
    std::forward_list<int> pending{3, 4};
    std::forward_list<int> urgent{1, 2};
    // splice_after inserts AFTER a position: before_begin() means "at the front".
    pending.splice_after(pending.before_begin(), urgent);
    for (int id : pending) std::printf("%d ", id);
    std::printf("| urgent empty: %d, count=%td\n", int(urgent.empty()),
                std::distance(pending.begin(), pending.end()));   // no size() member
    std::printf("sizeof list=%zu forward_list=%zu\n",
                sizeof(std::list<int>), sizeof(std::forward_list<int>));
#ifdef SHOW_ERROR
    pending.size();
#endif
}

go deeper

for a junior

Describe std::list as separately allocated nodes with two links, list what it lacks (operator[], std::sort, data()), and name splice and stable elements as its strengths.

for a middle

Explain why O(1) insertion rarely translates to speed: finding the position is linear and every node is an allocation. Contrast forward_list's insert_after model.

for a senior

Choose a list only for guarantees: stable addresses held by other structures, splicing, or non-movable elements. Otherwise measure before replacing a vector.

for a principal

Treat std::list as an exception in team guidelines: require a stated guarantee it provides, and watch allocation counts in hot paths when one is approved.

## What a std::list is `std::list<T>` (header `<list>`) is a **doubly linked list**. Each element is stored in its own **node**, allocated separately through the list's allocator, and each node carries two link pointers next to the value. The standard specifies the behaviour, not the node layout, but libc++ (`__prev_`, `__next_`) and libstdc++ (`_M_next`, `_M_prev`) both use exactly that shape. The list object itself is small: with libc++ on a 64-bit target, `sizeof(std::list<int>)` is 24 bytes, a sentinel node's two pointers plus the element count. Since C++11 the standard requires `size()` to be constant time, so the count is stored. ## What you give up - **Memory per element.** A `std::list<int>` node holds 4 bytes of data and 16 bytes of pointers on a 64-bit target, before the allocator's own bookkeeping and alignment. - **One allocation per insertion.** Every `push_back` or `insert` calls the allocator; a `std::vector` allocates only when its capacity runs out. - **Random access.** Iterators are bidirectional, so there is no `operator[]`, `it + 5` does not compile, and reaching the n-th element is a walk of n steps. - **The generic sort.** `std::sort` requires random-access iterators; with libc++ the call fails with "invalid operands to binary expression" inside the library. The list offers a member `sort()`, which is stable and relinks nodes instead of moving values. - **Contiguity.** There is no `data()`, so a list cannot be passed to a C API or viewed as a `std::span`. Scanning scattered nodes is also slower than scanning an array, which the material on cache-friendly layout covers. ## What you get 1. **Elements that never move.** A node stays where it was allocated until it is erased. Pointers and references to an element stay valid while other elements are inserted or erased, and the list's insert, erase and `sort` operations do not affect the validity of iterators to the remaining elements. 2. **Constant-time insert and erase at a known position.** Given an iterator, `insert` and `erase` only relink neighbours. Finding the position is still linear, so this wins only when you already hold the iterator. 3. **`splice`.** Moving one node, or a whole other list, into a list is constant time and copies nothing. This is the operation an LRU cache is built on. 4. **Non-movable element types.** `std::list<std::mutex>` with `emplace_back()` compiles, because nodes are never relocated. `std::vector<std::mutex>` with `emplace_back()` does not: growth must move elements, and libc++ rejects it with a static assertion that the type "does not meet the requirements of Cpp17MoveInsertable". ## And std::forward_list `std::forward_list<T>` is the singly linked variant. The standard states its goal as zero space or time overhead compared with a hand-written C-style singly linked list, so it drops what would cost extra: there is no `size()` member, no `push_back`, and no way to step backwards. Because a node only knows its successor, insertion and erasure happen **after** a position: `insert_after`, `erase_after`, `splice_after`, plus `before_begin()` to address the front. With libc++, `sizeof(std::forward_list<int>)` is 8 bytes, a single head pointer. | | `std::vector<T>` | `std::list<T>` | `std::forward_list<T>` | |---|---|---|---| | Storage | one contiguous block | one node per element, two links | one node per element, one link | | Random access | yes | no | no | | `size()` | constant | constant (since C++11) | not provided | | Insert or erase at a held position | linear (shifts the tail) | constant | constant, after the position | | Elements move on growth | yes | never | never | | Splice | not available | constant for one node or a whole list | `splice_after` | ## What to say in the interview The honest answer is "rarely, and for guarantees rather than speed". A list wins when the design needs **stable elements**, **iterators held across modifications**, **O(1) splice**, or **non-movable elements**. It loses on memory, allocation count and scanning, which is most workloads. Saying "list insertion is O(1), so a list is faster for inserts" without mentioning the walk to find the position, or the allocation per node, is the answer interviewers are probing for.

  • Why does std::list have its own sort() member when std::sort already exists?
    `std::sort` requires random-access iterators, and a list only has bidirectional ones, so the call does not compile. The member `list::sort()` is a stable sort with about N log N comparisons that relinks nodes instead of moving values, so iterators and references to elements stay valid and no element is copied or moved.
  • What does std::forward_list leave out compared with std::list, and why?
    It has one link per node instead of two, no `size()` member, no `push_back`, and only forward iterators, so insertion and erasure take the position before the element: `insert_after`, `erase_after`, `splice_after` and `before_begin()`. The standard's stated goal is zero overhead compared with a hand-written singly linked list, so anything that would cost extra space or time was omitted.

  • A std::list is faster than a std::vector for any workload with insertions
  • std::list nodes are stored contiguously, like a vector's elements
  • std::sort works on std::list as long as the elements are comparable
  • std::list::size() is linear because it has to count the nodes
  • std::forward_list has a constant-time size() member
open as a page

In a C++ standard container, what does end() refer to, and why must you never dereference it?

level: juniorimportance: must knowfreq 62%

basics

~20 s

end() returns the past-the-end iterator: a position one past the last element, not the last element itself. Container ranges are half-open, [begin, end), so begin() == end() means empty, and dereferencing end() is undefined behaviour.

open as a page

In C++, what happens when std::map::operator[], at() and find() are each called with a key that is not in the map?

level: juniorimportance: must knowfreq 75%

basics

~10 s

std::map::operator[] inserts the missing key with a value-initialized mapped value and returns a reference to it; at() throws std::out_of_range; find() returns end(). Only operator[] changes the map, so a const map has no operator[].

open as a page

In C++, when do you choose std::unordered_map over std::map, and what must the key type provide for each?

level: juniorimportance: must knowfreq 80%

basics

~20 s

std::unordered_map hashes keys into buckets: lookup is O(1) on average but O(n) in the worst case, iteration order is unspecified, and the key needs a hash and equality. std::map keeps keys sorted, guarantees O(log n), and needs only a less-than ordering.

open as a page

In C++, what is the difference between std::vector's size() and capacity(), and what does push_back cost as the vector grows?

level: juniorimportance: must knowfreq 80%

basics

~20 s

size() is how many elements a std::vector holds; capacity() is how many fit in its current allocation. push_back is amortized constant: when size reaches capacity it allocates a larger block, transfers every element, then appends.

open as a page

In C++, what does std::array give you over a built-in C array, and how does it differ from std::vector?

level: juniorimportance: must knowfreq 68%

basics

~20 s

std::array<T, N> wraps a fixed-size C array: it does not decay to a pointer, can be copied and returned, and offers size(), at() and iterators. Unlike std::vector, its size is fixed at compile time and its elements live inline.

open as a page

In C++, why does std::priority_queue<int> pop the largest element first, and how do you get a min-heap or a custom task order?

level: middleimportance: must knowfreq 65%

basics

~10 s

std::priority_queue keeps a heap under its comparator, default std::less, so the greatest element is on top. Use std::greater<T> for a min-heap, or a comparator returning true when a should come out after b.

open as a page

After an insert into a C++ std::vector, std::deque, std::list or std::map, which existing iterators and references stay valid?

level: middleimportance: must knowfreq 66%

basics

~10 s

std::list and std::map insertion leaves every iterator and reference valid. std::vector keeps those before the insertion point unless it reallocates. std::deque invalidates all iterators, but insertion at either end keeps references valid.

open as a page

In C++, what happens when a range-based for loop over a std::vector calls push_back on that same vector?

level: middleimportance: must knowfreq 78%

basics

~10 s

It is undefined behaviour. The loop holds cached begin and end iterators; push_back always invalidates the end iterator, and when size exceeds capacity it reallocates, invalidating every iterator and reference, including the loop variable.

open as a page

How do you make a struct holding a user id and a device id usable as a std::unordered_map key in C++?

level: middleimportance: must knowfreq 65%

basics

~20 s

Give the struct equality, such as a defaulted operator== in C++20, and a hash: specialize std::hash for it or pass a hasher type as the third template argument. Keys that compare equal must hash equal, and the hash should mix every field.

open as a page

In C++, what do std::vector's reserve, resize and shrink_to_fit each change, and when does reserving before a loop pay off?

level: middleimportance: must knowfreq 70%

basics

~20 s

reserve(n) raises capacity to at least n without creating elements; resize(n) changes size, constructing or destroying elements; shrink_to_fit asks, without obligation, to drop unused capacity. Reserve before a loop whose final count you know, so the loop never reallocates.

open as a page

In C++, a loop runs for (auto it = c.begin(); it != c.end(); ++it) if (skip(*it)) c.erase(it); — what is wrong, and what is the correct pattern?

level: seniorimportance: must knowfreq 64%

basics

~10 s

c.erase(it) invalidates it, so the following ++it is undefined behaviour. Use the iterator erase returns, which refers to the element after the erased one: it = c.erase(it) when removing, ++it only when keeping.

open as a page

In C++, what containers do std::stack and std::queue wrap, and why does their pop() return nothing?

level: juniorimportance: should knowfreq 55%

basics

~20 s

std::stack and std::queue adapt a sequence container, std::deque by default; a stack can also use vector or list, a queue list but not vector. pop() returns void so that a throwing copy can never lose the removed element.

open as a page

In C++20, what is std::span, and how does a std::span<const float> parameter differ from const std::vector<float>&?

level: juniorimportance: should knowfreq 46%

basics

~20 s

std::span is a C++20 non-owning view of a contiguous sequence: in effect a pointer plus a count. A std::span<const float> parameter accepts a vector, std::array, C array or slice without copying, while a vector reference accepts only a vector.

open as a page

In C++, how does std::deque store its elements, and why do references survive push_front and push_back while iterators do not?

level: middleimportance: should knowfreq 55%

basics

~20 s

std::deque keeps elements in fixed-size blocks tracked by an array of block pointers. Pushing at either end fills or adds a block and never moves existing elements, so references stay valid; the pointer array may be reallocated, which invalidates iterators.

open as a page

Why does std::sort not compile on a std::list in C++, and what do iterator categories have to do with it?

level: middleimportance: should knowfreq 52%

basics

~10 s

std::sort needs random access iterators, which jump and subtract in constant time; std::list iterators are only bidirectional. Call the member list::sort() instead, which relinks nodes, keeps iterators valid and is stable.

open as a page

What must a custom comparator for std::map or std::set guarantee, and what goes wrong if it compares with <= instead of <?

level: middleimportance: should knowfreq 50%

basics

~20 s

It must induce a strict weak ordering: comp(a, a) is false, comp is transitive, and equivalence, neither comp(a, b) nor comp(b, a), is transitive too. A <= comparator breaks irreflexivity, so using it is undefined behaviour and lookups silently fail.

open as a page

In C++17, how do std::map::try_emplace and insert_or_assign differ from insert, emplace and operator[] when the key already exists?

level: middleimportance: should knowfreq 40%

basics

~20 s

When the key exists, try_emplace does nothing, leaves its arguments untouched and returns {iterator, false}; insert_or_assign assigns the new value and returns {iterator, false}. insert and emplace also keep the old value, but may already have consumed a moved argument.

open as a page

Does indexing a C++ std::span check bounds, and what did C++26 change with std::span::at?

level: middleimportance: should knowfreq 36%

basics

~10 s

No. std::span::operator[] has the precondition index < size(), and breaking it is undefined behaviour in C++20 and C++23. C++26 adds span::at(), which throws std::out_of_range, and makes operator[] a hardened precondition.

open as a page

In C++20, how does std::span<float, 4> differ from std::span<float>, and when does converting between them compile?

level: middleimportance: should knowfreq 30%

basics

~20 s

std::span<float, 4> has a static extent: the size 4 is part of the type. std::span<float> has dynamic extent, storing its size at run time. Static converts implicitly to dynamic; dynamic to static needs an explicit conversion whose size must match.

open as a page

What do load_factor, max_load_factor, rehash and reserve mean for a C++ std::unordered_map, and when should you call reserve?

level: middleimportance: should knowfreq 50%

basics

~20 s

load_factor() is size() divided by bucket_count(); when an insert would exceed max_load_factor(), 1.0 by default, the table rehashes into more buckets. rehash(n) asks for at least n buckets; reserve(n) makes room for n elements. Reserve before a known bulk insert.

open as a page

In C++, how does std::vector::emplace_back differ from push_back, and when is emplace_back no faster or even riskier?

level: middleimportance: should knowfreq 62%

basics

~20 s

push_back takes an element-type object, building a temporary if needed and moving it in; emplace_back forwards arguments to a constructor and builds the element in place. With an existing object they do the same work, and emplace_back can call explicit constructors.

open as a page

In C++, why does an LRU cache pair std::list with an unordered_map of list iterators, and what does list::splice guarantee that makes it work?

level: seniorimportance: should knowfreq 50%

basics

~20 s

The list holds entries in recency order; the hash map finds each entry's node by key. list::splice moves a node to the front in constant time, without copying or throwing, and its iterator stays valid, so the map needs no update.

open as a page

A word-frequency std::map<std::string, int> is searched with std::string_view tokens; why does find(token) not compile, and how do you fix it without allocating?

level: seniorimportance: should knowfreq 35%

basics

~20 s

With std::lessstd::string, find takes const std::string&, and std::string_view does not convert to it implicitly. Declare the map with a transparent comparator such as std::less<>, and the C++14 find, count and lower_bound templates compare the string_view directly.

open as a page

A C++ class keeps a std::span<const float> into its own std::vector<float> member; why does it break after push_back, and how do you fix it?

level: seniorimportance: should knowfreq 45%

basics

~20 s

The span stores the vector's data pointer and a size. A push_back that exceeds capacity reallocates and frees the old buffer, so the span dangles. Store an offset and length and rebuild the span when needed.

open as a page

A session cache std::unordered_map keyed by user id and device id slows down under load although load_factor() looks normal; how do you diagnose and fix it?

level: seniorimportance: should knowfreq 40%

basics

~20 s

Suspect the hash, not the table size: load_factor() is an average that hides one overloaded bucket. Measure bucket_size(bucket(key)) and the largest bucket, then replace a weak combine such as user ^ device with one that mixes every field.

open as a page

Code inserts into a std::unordered_map while holding an iterator to one element and a pointer to another; which survives a rehash, and why?

level: seniorimportance: should knowfreq 45%

basics

~20 s

The pointer survives and the iterator may not. A rehash invalidates every iterator and reorders elements, but each element lives in its own node that is relinked rather than moved, so pointers and references stay valid until that element is erased.

open as a page

In C++, why can worker threads writing different indices of a std::vector<bool> still race, and what else makes it unlike other vectors?

level: seniorimportance: should knowfreq 45%

basics

~20 s

std::vector<bool> is a specialization that packs flags into bits, so operator[] returns a proxy object instead of bool&. Neighbouring flags share a word, so concurrent writes to different indices can race, and bool&, bool* and data() are unavailable.

open as a page

Should a team standardize on std::unordered_map or a third-party open-addressing hash map for hot lookup paths, and how would you decide?

level: principalimportance: should knowfreq 30%

basics

~20 s

Keep std::unordered_map as the default where code relies on stable references, node handles or the bucket interface; adopt an open-addressing library behind a project alias only where profiles show hash lookups hot, after benchmarking real keys and auditing reference-stability assumptions.

open as a page

As a C++ lead, would you make std::vector the default container in your guidelines, and which exceptions would you write into that rule?

level: principalimportance: should knowfreq 40%

basics

~20 s

Yes: std::vector is contiguous, cache-friendly and simple, so it should be the default sequence. Write exceptions for fixed sizes (std::array, C++26 std::inplace_vector), stable element addresses, front insertion, keyed lookup and packed bools, each backed by a stated reason or a measurement.

open as a page

showing 1–30 of 34