STL Container Selection

Every STL container is a bundle of trade-offs, not a universal box for data — picking the wrong one silently turns an O(1) operation into an O(n) one, and interviewers know exactly which question to ask to find out if you understand why.

std::vector is not a safe default you can reach for every time. Reach for it when you shouldn't and you get quadratic-time insertion where a std::list would have been O(1), or you reach for std::map when std::unordered_map would have been three times faster, or you store a hot loop's data in a std::list and eat cache misses on every single access. Container selection is really a question with four sub-questions hiding inside it: how will this data be accessed (by index, by key, front/back, or only sequentially)? how will it grow and shrink (append only, insert/remove anywhere, fixed size)? does iteration order matter, and if so, does it need to be sorted? and how much does memory layout matter for this code's performance? This page walks through the standard sequence containers, the associative containers (ordered and hashed), and the container adapters, builds a decision process you can actually apply under interview pressure, and closes with the iterator-invalidation rules that trip up even experienced C++ programmers.

The Real Question: What Are You Doing With This Data?

Before naming a single container, answer three questions about the data's actual usage pattern. First, access pattern: do you need random access by index ("give me element 47"), lookup by key ("give me the value for \"alice\""), or only ever front-to-back iteration? Second, mutation pattern: do elements get added/removed only at the ends, only at the front, or anywhere in the middle? Third, ordering: does the container need to preserve insertion order, maintain sorted order automatically, or is order irrelevant? Every container in the standard library is a specific answer to those three questions, and picking one without asking them is how you end up with correct-but-slow code.

A rule of thumb that holds surprisingly often: default to std::vector until you have a specific, measured reason not to. Its contiguous layout makes it the fastest container for iteration in practice even when the textbook Big-O of some other container looks better on paper — cache effects usually dominate for anything smaller than a few hundred thousand elements.

Sequence Containers: vector, deque, list, array

std::vector stores elements contiguously, like a dynamically resizable array. Random access by index is O(1) — element i lives at data() + i * sizeof(T), pure arithmetic. Appending at the back is amortized O(1) (occasionally a reallocation copies everything, O(n), but that cost is spread out over many pushes). Inserting or erasing anywhere except the back is O(n), because every element after the insertion point has to shift.

reserve(1'000'000) pre-allocates the backing buffer once, so the loop below never triggers a reallocation — without it, push_back would reallocate and copy roughly log2(n) times as the vector doubles in capacity. values[500000] is a single pointer-arithmetic computation, not a traversal.

std::deque (double-ended queue) is a sequence of fixed-size chunks linked together, giving O(1) push_front and push_back while still supporting O(1) random access — something std::vector can't offer for push_front, since that would require shifting every existing element. The cost is weaker cache locality than std::vector, because the chunks aren't guaranteed contiguous with each other, and a slightly larger per-element overhead. std::deque is the right answer whenever a task needs efficient insertion at both ends — a sliding-window algorithm, a work queue processed from the front while new items arrive at the back.

std::list is a doubly linked list: O(1) insertion and removal anywhere, given an iterator to the position, but O(n) to reach that position in the first place (no random access at all — list::operator[] doesn't even exist), and every node is a separate heap allocation with two pointers of overhead plus whatever the cache misses walking the chain cost you. In practice std::list is rarely the right first choice; it earns its place when you need to splice large chunks of a sequence together in O(1) (std::list::splice moves nodes without copying elements) or when iterators/pointers to existing elements must remain valid across insertions and removals anywhere in the sequence — std::vector invalidates on reallocation, std::list never invalidates except for the erased element itself.

std::array<T, N> is a fixed-size, stack-allocated (when declared as a local) array with no dynamic resizing at all — it wraps a C-style array with STL-container ergonomics (begin()/end(), size(), bounds-checked at() ). Use it whenever the size is known at compile time and won't change; it avoids heap allocation entirely and has zero overhead beyond the raw array itself.

#include <vector>
#include <chrono>
#include <iostream>

int main()
{
    std::vector<int> values;
    values.reserve(1'000'000);   // avoid repeated reallocation

    for (int i = 0; i < 1'000'000; ++i)
        values.push_back(i);

    std::cout << "front: " << values.front() << ", back: " << values.back() << "\n";
    std::cout << "random access values[500000]: " << values[500000] << "\n";

    return 0;
}

Cache Locality and Why Contiguous Wins More Than Big-O Suggests

Big-O analysis counts operations, not cache misses — and on real hardware, a cache miss can cost 100-300 CPU cycles versus roughly 1 cycle for an L1 hit. std::vector's contiguous layout means that reading element i almost always pulls elements i+1 through i+15 or so into the same cache line for free, so sequential iteration over a vector of a million ints can be an order of magnitude faster in wall-clock time than the theoretically-equal-complexity iteration over a std::list of a million ints, whose nodes are scattered across the heap with no locality guarantee at all.

Ordered Associative Containers: map and set

std::map<K, V> and std::set<K> are typically implemented as red-black trees, giving O(log n) insertion, lookup, and deletion, with keys always visitable in sorted order via in-order traversal. That sorted-order guarantee is the entire reason to reach for std::map over std::unordered_map: if code needs range queries ("all entries with key >= 100"), the smallest or largest key, or to print entries in key order, std::map (or std::multimap, which allows duplicate keys) is the tool, because std::unordered_map's iteration order is unspecified and can change between insertions.

Structured bindings ([name, count]) unpack each std::pair<const std::string, int> node cleanly. lower_bound is the operation std::unordered_map cannot offer at all — it depends entirely on the keys being kept in sorted order internally, which a hash table does not do.

Each node in std::map is a separate heap allocation (typically three pointers plus red-black-tree bookkeeping on top of the key/value pair), so std::map uses noticeably more memory per entry than a contiguous container and has worse cache locality during traversal — another case where std::unordered_map, when sorted order isn't needed, tends to win both in memory and in raw lookup speed.

#include <map>
#include <string>
#include <iostream>

int main()
{
    std::map<std::string, int> inventory;
    inventory["widgets"] = 40;
    inventory["bolts"] = 120;
    inventory["gears"] = 15;

    // Iterates in sorted key order: bolts, gears, widgets
    for (const auto& [name, count] : inventory)
        std::cout << name << ": " << count << "\n";

    auto it = inventory.lower_bound("g");   // first key >= "g"
    if (it != inventory.end())
        std::cout << "first key >= 'g': " << it->first << "\n";

    return 0;
}

Hashed Associative Containers: unordered_map and unordered_set

std::unordered_map<K, V> and std::unordered_set<K> are hash tables: average-case O(1) insertion, lookup, and deletion, achieved by hashing the key to pick a bucket and then (usually) chaining within that bucket. The worst case is O(n) if every key collides into the same bucket, but with a reasonable hash function and load factor that's pathological, not typical. Use an unordered container whenever you need fast key lookup and don't care about iteration order — the overwhelmingly common case for caches, lookup tables, and "have I seen this before?" sets.

wordCount[word] default-constructs the value (0 for int) on first access and increments it, a common idiom for counting. The printed order is not guaranteed to match insertion order or any sorted order — that unpredictability is the price paid for the average O(1) lookups.

Hashed containers also carry meaningful memory overhead: a load factor typically kept around 1.0 means the bucket array itself is roughly as large as the element count, on top of the per-node allocation for chaining, and rehashing (growing the bucket array when the load factor is exceeded) invalidates all iterators and can momentarily spike memory use as the old and new tables coexist.

#include <unordered_map>
#include <string>
#include <iostream>

int main()
{
    std::unordered_map<std::string, int> wordCount;
    for (const std::string& word : {"cat", "dog", "cat", "bird", "dog", "cat"})
        ++wordCount[word];

    for (const auto& [word, count] : wordCount)
        std::cout << word << " -> " << count << "\n";   // order is unspecified

    return 0;
}

Container Adapters: stack, queue, priority_queue

std::stack and std::queue aren't independent data structures — they're thin interfaces (push/pop/top or push/pop/front-back) wrapped around an underlying container, std::deque by default. Reach for std::stack when the problem is naturally LIFO (matching parentheses, undo history, DFS traversal with an explicit stack instead of recursion) and std::queue when it's naturally FIFO (BFS traversal, a task queue processed in arrival order). std::priority_queue wraps a container (std::vector by default) as a binary heap, giving O(log n) push and O(1) access to the largest element (or smallest, with a custom comparator) — the standard tool for "give me the top-k" or Dijkstra's-algorithm-style problems.

Each push is O(log n) as the heap re-establishes its invariant, and top() is O(1) because the largest element always sits at the root. Popping in a loop like this yields elements in descending order, which is exactly the heap-sort pattern.

#include <queue>
#include <iostream>

int main()
{
    std::priority_queue<int> maxHeap;
    for (int v : {5, 1, 9, 3, 7})
        maxHeap.push(v);

    while (!maxHeap.empty())
    {
        std::cout << maxHeap.top() << " ";   // 9 7 5 3 1
        maxHeap.pop();
    }
    std::cout << "\n";

    return 0;
}

Iterator Invalidation Rules

Every container has its own rules for when an iterator, pointer, or reference into it stops being valid, and using an invalidated one is undefined behavior — it may work by accident in testing and crash in production. std::vector invalidates every iterator and pointer on reallocation (any insertion that exceeds current capacity()), and invalidates iterators from the insertion/erasure point onward even without reallocation. std::deque invalidates all iterators on any insertion or erasure in the middle, but push_front/push_back only invalidate iterators, not references to existing elements. std::list and std::map/std::set/std::unordered_map only invalidate the iterator to the specific element erased — everything else remains valid, which is exactly why std::list is preferred when code needs to hold onto iterators across mutations.

A Decision Flow You Can Apply Under Pressure

Reduce the whole decision to a short sequence of questions, roughly in this order of priority, and you'll land on the right container in an interview or in real code almost every time.

Ownership matters too: every one of these containers owns its elements by value and manages their lifetime automatically — construct, copy/move, and destroy all happen through the container's own operations, so there's no manual new/delete bookkeeping unless you're storing raw pointers (which you generally shouldn't; store smart pointers or values instead so the container's destructor does the right thing automatically).

Why is std::vector usually faster in practice than std::list for a workload that inserts a handful of times but then iterates millions of times, even though std::list has O(1) insertion and std::vector has O(n) insertion in the middle?

The one-time O(n) shift cost in the vector is paid once and is a cheap, cache-friendly memmove-style operation, while every iteration over the list pays a cache miss per node because the nodes are scattered across the heap. With millions of iterations dominating a handful of inserts, the vector's superior cache locality during iteration outweighs its worse insertion complexity.

When should you choose std::map over std::unordered_map even though std::unordered_map has better average-case lookup complexity?

Choose std::map when the code needs keys visited in sorted order, needs range queries (lower_bound/upper_bound, "all keys >= x"), or needs the smallest/largest key efficiently — none of which std::unordered_map can provide, since its bucket-based layout has no notion of key ordering.

Why does std::deque support O(1) push_front while std::vector does not?

std::vector stores its elements in one contiguous block, so inserting at the front would require shifting every existing element over by one slot, an O(n) operation. std::deque is internally a sequence of separate fixed-size chunks with an index structure on top, so it can allocate a new chunk (or reuse space) at either end without touching existing elements, making both push_front and push_back O(1).

What happens to existing iterators when a std::vector reallocates, and why does that make erasing elements during a range-based for loop dangerous?

Reallocation copies (or moves) every element into a new, larger heap buffer and frees the old one, which invalidates every iterator, pointer, and reference into the old buffer. Erasing during a range-based for loop is dangerous because operations like erase() can invalidate the iterator the loop is using internally; you must use the iterator explicitly returned by erase() to continue safely, which a range-for loop doesn't give you access to.

Why is std::priority_queue built on top of std::vector by default rather than std::list, given that it needs to grow and shrink dynamically?

std::priority_queue implements a binary heap, which relies on treating the underlying storage as an implicit tree using index arithmetic (children of index i are at 2i+1 and 2i+2) — that arithmetic requires O(1) random access, which std::vector provides and std::list does not. The contiguous layout also keeps the heap's sift-up/sift-down operations cache-friendly.

Write a C++ program that reads a list of words and uses a std::unordered_map<std::string, int> to count how many times each word appears, then prints each word with its count.

operator[] on an unordered_map default-constructs a 0 the first time a key is seen, so ++counts[word] both inserts and increments in one expression. This is O(1) average per word, versus O(log n) per word if std::map had been used instead — the right call here since nothing about the output requires sorted word order.

What does the following program print, and why does the output order look the way it does?

It prints 7: Bob, then 19: Carol, then 42: Alice — sorted ascending by key, regardless of insertion order (42, then 7, then 19). std::map keeps its elements in sorted key order internally (typically as a red-black tree), so iteration always visits keys from smallest to largest.

Write a C++ program that uses std::stack to check whether a string of parentheses, brackets, and braces is balanced (e.g. "{[()]}" is balanced, "{[(])}" is not).

Every opening bracket is pushed; every closing bracket must match the most recently pushed (and not-yet-closed) opener, which is exactly what stack::top() gives access to — LIFO order. If a closing bracket doesn't match top, or the stack is empty when a closer arrives, or brackets remain unclosed at the end, the string isn't balanced. This is the canonical use case for a stack rather than any other container.

Write a C++ program that stores a small set of task priorities in a std::priority_queue<int> and processes them in descending priority order, printing each as it's popped.

std::priority_queue keeps its largest element accessible in O(1) via top(); each pop() is O(log n) as the heap restores its invariant. The loop drains tasks in the order 9, 6, 3, 1 — always the highest remaining priority first — which is exactly the behavior a task scheduler or Dijkstra's algorithm relies on.

Need index-based random access, mostly append at the back?
  -> std::vector (default choice; use std::array if size is fixed at compile time)

Need fast insertion/removal at BOTH the front and back?
  -> std::deque

Need O(1) insertion/removal anywhere, given an iterator, and
iterators/pointers must survive other mutations?
  -> std::list

Need key -> value lookup and DON'T care about order?
  -> std::unordered_map / std::unordered_set  (average O(1))

Need key -> value lookup AND sorted order / range queries?
  -> std::map / std::set  (O(log n), always sorted)

Need strict LIFO access only (push/pop/top)?
  -> std::stack

Need strict FIFO access only (push/pop/front)?
  -> std::queue

Need repeated access to the current min/max as items come and go?
  -> std::priority_queue

#include <map>
#include <iostream>

int main()
{
    std::map<int, std::string> scores;
    scores[42] = "Alice";
    scores[7]  = "Bob";
    scores[19] = "Carol";

    for (const auto& [key, name] : scores)
        std::cout << key << ": " << name << "\n";

    return 0;
}