C++ STL Containers Cheatsheet

The C++ standard library ships with about a dozen containers. Most teams use three of them seriously and never reach for the rest. The reason is not laziness; it is that asymptotic complexity is a poor guide for picking containers in 2026. Cache locality, branch prediction, and allocator behavior usually matter more.

The mental model

Group the containers by what they are physically.

Contiguous arrays:    vector, array, string
Linked nodes:         list, forward_list
Block-of-arrays:      deque
Balanced trees:       map, set, multimap, multiset
Hash tables:          unordered_map, unordered_set
Adapters:             stack, queue, priority_queue

The physical layout determines almost everything that matters in practice: cache behavior, iterator stability, insertion cost, and how the compiler vectorizes loops over the container.

vector: the default choice

std::vector<T> is a contiguous, dynamically grown array. It is the right answer in roughly 80 percent of cases.

std::vector<int> v;
v.reserve(1000);
for (int i = 0; i < 1000; ++i) v.push_back(i);

Random access is O(1). Iteration is cache-friendly and vectorizable. Inserting at the back is amortized O(1). Inserting in the middle is O(n) because elements after the insertion shift. Iterator invalidation: a reallocation invalidates all iterators, pointers, and references. Insertions in the middle invalidate iterators from the insertion point on.

Use reserve when you know the final size. Use shrink_to_fit if memory matters and you have permanently shrunk.

list and forward_list

std::list is a doubly linked list. std::forward_list is singly linked. Both offer constant-time insertion anywhere given an iterator. Neither offers random access.

In practice, they are slow. Every node is a separate heap allocation. Traversal jumps around memory and the CPU prefetcher cannot help. For most workloads, a vector with shifts beats a list with constant-time splices.

Reach for list only when you genuinely need stable iterators across insertions and splicing whole sublists, and you have measured to confirm. The classic intrusive-list pattern in low-level code rarely uses std::list.

deque

std::deque<T> (pronounced “deck”) is implemented as a sequence of fixed-size blocks. It supports O(1) push at both ends and random access, at the cost of slightly slower iteration than vector.

It is the right choice for FIFO queues with high churn at both ends, or for cases where you cannot afford the occasional reallocation vector does. As a side note, std::queue and std::stack adapt deque by default.

map and set

std::map<K,V> and std::set<K> are typically red-black trees. Operations are O(log n). Iteration is in sorted order.

std::map<std::string, int> counts;
counts["apple"] += 1;
for (const auto& [key, value] : counts) {
    std::cout << key << ": " << value << '\n';
}

Iterators are stable: insertions and erasures do not invalidate other iterators. That stability is the main reason to pick map over unordered_map.

std::multimap and std::multiset allow duplicate keys.

unordered_map and unordered_set

These are hash tables. Average operations are O(1); worst case is O(n) if your hash is terrible. Iteration order is undefined and can change.

std::unordered_map<std::string, int> counts;
counts.reserve(1024);
counts["apple"] = 1;

reserve here means “reserve enough buckets for at least N elements” and avoids rehashing during insertion. The default hashers are fine for most fundamental types and strings. Custom types need a std::hash specialization or a hash function passed to the container.

unordered_map is generally faster than map for large containers, but smaller maps sometimes win because tree nodes can pack better than buckets.

array

std::array<T, N> is a fixed-size stack-allocated array with the STL interface. Use it when the size is known at compile time. It is zero overhead compared to a C array and plays nicely with range-based for loops, ranges, and algorithms.

Hands-on choices

A frequency counter: unordered_map<string, int>. Iteration order does not matter.

A leaderboard sorted by score: keep a vector<entry> and sort, or use a std::multiset if entries change often.

A FIFO of pending tasks: std::queue<Task> (backed by deque).

A priority queue for scheduling: std::priority_queue<Task, vector<Task>, Compare>.

A graph adjacency list: vector<vector<int>> almost always beats vector<list<int>>.

Common pitfalls

Assuming list is fast because asymptotic notation says so. Benchmark.

Mutating a container while iterating with range-based for. Erasures with iterators must use the returned iterator.

for (auto it = v.begin(); it != v.end(); ) {
    if (shouldRemove(*it)) it = v.erase(it);
    else ++it;
}

For vector, prefer erase-remove: v.erase(std::remove_if(v.begin(), v.end(), pred), v.end()), or in C++20, std::erase_if(v, pred).

Using operator[] on a map when you only want to read. It inserts a default-constructed value if the key is missing. Use find or contains.

Forgetting to provide a hash for custom keys in unordered_map. The compile error is loud, but the fix is template boilerplate.

Practical tips

Default to vector. Profile before reaching for anything else. When you need ordered iteration, pick map or set. When you only need lookup, pick unordered_map or unordered_set. Save the linked containers for the cases that really need iterator stability.

For small fixed sizes, prefer array and string_view to avoid heap allocation entirely. For string-keyed maps, std::unordered_map<std::string, V> paired with transparent hashers (heterogeneous lookup) lets you query with string_view without temporary strings.

Wrap-up

The STL containers cover almost every reasonable data layout. The difference between fast and slow code is usually not the algorithm; it is the layout. Pick contiguous storage when you can, ordered trees when iteration order matters, hash tables when only lookup matters, and linked structures only when iterator stability is non-negotiable.