C++ Containers: Choose the Right Data Structure

By the end of this page you will understand the four container categories, choose between vector, deque, list, map, and unordered_map based on your access patterns, and know the iterator invalidation rules that prevent undefined behaviour.

What and Why

A container is an object that holds and manages a collection of elements. The C++ standard library provides twelve core containers, each optimised for a different mix of operations. Choosing the wrong container is one of the most common C++ performance mistakes — and it is entirely avoidable once you understand the tradeoffs.

The standard containers fall into four families:

The Containers

std::array — fixed-size, stack-allocated (C++11)

A thin wrapper around a C-style array that adds standard container semantics: .size(), iterators, range-for, and <algorithm> compatibility — without heap allocation or size overhead.

#include <array>
#include <algorithm>
#include <iostream>

std::array<int, 5> a = {5, 3, 1, 4, 2};  // C++11: size is a compile-time constant

std::sort(a.begin(), a.end());             // works with all STL algorithms

for (int n : a) std::cout << n << ' ';    // 1 2 3 4 5

std::cout << a.size() << '\n';            // 5 — unlike C arrays, always knows its size
std::cout << a.at(10) << '\n';            // throws std::out_of_range

Unlike a C-style array, std::array does not decay to a pointer — passing it to a function preserves its type and size information. Unlike vector, it never allocates on the heap: the elements live inside the object itself (stack if local, data-segment if global).

C++17 adds a class template argument deduction guide: std::array a{1, 2, 3} deduces std::array<int, 3>.

Use std::array when:

• The size is known at compile time and will never change.
• You want stack allocation and cache-friendly contiguous storage with zero heap overhead.
• You need constexpr-compatible storage.

Iterator invalidation: iterators to std::array are never invalidated — the array itself cannot be resized.

std::vector — the default choice

A contiguous array that grows automatically. Access by index is O(1). Appending to the end is amortised O(1). Insertion or deletion in the middle is O(n).

#include <vector>
#include <iostream>

std::vector<int> v;
v.reserve(100);           // pre-allocate to avoid reallocations
v.push_back(1);
v.push_back(2);
v.emplace_back(3);        // construct in place — no copy/move

std::cout << v[1] << '\n';          // O(1): 2
std::cout << v.at(1) << '\n';       // O(1) with bounds check: 2

v.insert(v.begin() + 1, 99);       // O(n): shifts elements right
v.erase(v.begin() + 1);            // O(n): shifts elements left

Use vector for everything by default. Its cache performance dominates any theoretical advantage of other containers for typical sizes.

Iterator invalidation: any operation that changes capacity() (such as push_back when full) invalidates all iterators, pointers, and references. Insertions/erasures invalidate all iterators at and after the modified position.

std::deque — fast at both ends

Double-ended queue. O(1) push and pop at both front and back. O(1) random access. Elements are stored in fixed-size chunks — not contiguous like vector.

#include <deque>

std::deque<int> dq = {3, 4, 5};
dq.push_front(2);   // O(1)
dq.push_back(6);    // O(1)
dq.pop_front();     // O(1)
std::cout << dq[0] << '\n';   // O(1): 3

Use deque when you need efficient insertion at both ends. Avoid it when cache performance matters — the chunked layout is slower than vector for linear traversal.

Iterator invalidation: insertions at either end invalidate all iterators (but not references/pointers to existing elements). Insertions in the middle invalidate everything.

std::list — stable iterators, slow traversal

Doubly-linked list. O(1) insertion and deletion anywhere given an iterator. O(n) random access (no operator[]). Each node is individually allocated — very poor cache performance.

#include <list>

std::list<int> lst = {1, 2, 3, 4, 5};

auto it = std::find(lst.begin(), lst.end(), 3);
lst.insert(it, 99);   // O(1) — no element moves
lst.erase(it);        // O(1) — it still valid after unrelated inserts

lst.sort();           // O(n log n) — member sort (not std::sort — needs random-access)

Use list when: you hold long-lived iterators into the middle of the container and insert/erase frequently at known positions. Do not use it for general storage — vector beats it in cache benchmarks even for O(n) inserts.

Iterator invalidation: only the erased element's iterator is invalidated. All other iterators remain valid.

std::map — sorted key-value pairs

Red-black tree. O(log n) for lookup, insert, and erase. Keys are always sorted. Iteration is in key order.

#include <map>
#include <string>

std::map<std::string, int> word_count;
word_count["hello"]++;
word_count["world"]++;
word_count["hello"]++;   // operator[] inserts with 0 if key absent

for (const auto& [word, count] : word_count) {
    std::cout << word << ": " << count << '\n';   // alphabetical order
}

// Safe lookup — no silent insertion
auto it = word_count.find("hello");
if (it != word_count.end()) {
    std::cout << it->second << '\n';
}

Warning: operator[] inserts a default-constructed value if the key does not exist. Use find() when you do not want to create missing entries.

Iterator invalidation: insert and erase do not invalidate any other iterators. map iterators are among the most stable in the standard library.

std::unordered_map — O(1) average lookup

Hash table. O(1) average for lookup, insert, and erase. O(n) worst case (all keys collide). No ordering — iteration order is unspecified.

#include <unordered_map>
#include <string>

std::unordered_map<std::string, int> cache;
cache.reserve(1000);      // pre-size to avoid rehashes
cache["key"] = 42;

if (auto it = cache.find("key"); it != cache.end()) {
    std::cout << it->second << '\n';
}

Use unordered_map when:

• You need faster average lookup than map (and O(1) vs O(log n) matters at your scale)
• You do not need keys in sorted order
• Your key type has a std::hash specialisation (built-in for strings, integers, pointers)

Iterator invalidation: rehashing (triggered by growth past max_load_factor) invalidates all iterators. Individual erasures invalidate only the erased element's iterator.

std::set and std::unordered_set

Like map and unordered_map but storing keys only — no values. Useful for membership testing and deduplication:

#include <set>
#include <unordered_set>

std::set<int> s = {5, 2, 8, 1, 9, 1};   // duplicates removed, sorted
// s = {1, 2, 5, 8, 9}

std::unordered_set<std::string> visited;
visited.insert("page1");
if (visited.count("page1")) { /* already visited */ }

Container adaptors

stack, queue, and priority_queue wrap a sequence container and restrict its interface:

#include <stack>
#include <queue>

std::stack<int> st;
st.push(1); st.push(2); st.push(3);
st.top();   // 3 (peek)
st.pop();   // removes 3

std::queue<int> q;
q.push(1); q.push(2);
q.front();  // 1
q.pop();    // removes 1

// Max-heap by default
std::priority_queue<int> pq;
pq.push(5); pq.push(1); pq.push(9);
pq.top();   // 9

Choosing a Container

Is the size fixed at compile time?
├── Yes → array (zero heap overhead, never invalidated)
└── No → dynamic container:
    Does order matter?
    ├── No → unordered_map / unordered_set (O(1) lookup)
    └── Yes, and it's by key → map / set (O(log n), sorted)
        └── Yes, by insertion order → vector / deque / list
            ├── Need fast random access? → vector
            ├── Need fast insert/delete at front? → deque
            └── Need stable iterators + O(1) middle insert? → list

Default rule: start with vector. Switch only when profiling shows a real bottleneck. Use array when the element count is truly fixed.

Iterator Invalidation Summary

Common Mistakes

Using operator[] on a const map

void print(const std::map<std::string, int>& m) {
    std::cout << m["key"];  // COMPILE ERROR: operator[] is non-const
}

// Fix: use at() or find()
std::cout << m.at("key");                    // throws if not found
auto it = m.find("key");
if (it != m.end()) std::cout << it->second;  // safe

Invalidating iterators during range-for over vector

std::vector<int> v = {1, 2, 3, 4, 5};
for (const auto& x : v) {
    if (x == 3) v.push_back(99);  // may reallocate — UB!
}

// Fix: don't modify the container during iteration, or use an index
for (std::size_t i = 0; i < v.size(); ++i) {
    if (v[i] == 3) v.push_back(99);  // ok: index not invalidated
}

Assuming unordered_map is always faster

For small containers (under ~100 elements), map's tree traversal is often faster than unordered_map's hash computation plus possible cache misses. Measure before switching.

Quick Reference

std::deque Internals: Chunk-Based Storage

std::deque achieves O(1) push at both ends by storing elements in a sequence of fixed-size chunks rather than one contiguous buffer. A central index array holds pointers to these chunks, so the deque can prepend a new chunk at the front without touching existing memory. This is fundamentally different from vector, which must shift every element or reallocate the entire buffer to insert at the front.

#include <deque>
#include <iostream>

int main() {
    std::deque<int> dq;

    // Both ends are O(1) — no element movement
    dq.push_back(3);
    dq.push_back(4);
    dq.push_front(2);
    dq.push_front(1);
    // dq: 1 2 3 4

    // Random access is also O(1) — chunk + offset arithmetic
    std::cout << dq[2] << '\n'; // 3

    // Efficient removal at either end
    dq.pop_front(); // O(1)
    dq.pop_back();  // O(1)
    // dq: 2 3
}

The cost of chunk-based storage is cache performance: iterating through a deque touches multiple non-contiguous memory regions. For linear scans over large sequences, vector is typically faster even though its algorithmic complexity is identical. Prefer deque when you need a true FIFO queue with many push/pop operations at both ends, and prefer vector when traversal dominates.

A less-obvious consequence: taking the address of a deque element is safe as long as you do not insert at the middle — front/back inserts do not move existing elements (though they do invalidate all iterators due to the index array potentially resizing).

std::list and std::forward_list: When Pointer Stability Matters

std::list and std::forward_list guarantee that inserting or erasing anywhere leaves all other iterators, pointers, and references valid — a property no contiguous container can offer. This makes them the right choice for intrusive data structures, observer lists, and any algorithm that holds long-lived pointers into a collection while concurrently modifying it.

std::list is a doubly-linked list; std::forward_list (C++11) is singly-linked and uses slightly less memory per node at the cost of being forward-only.

#include <list>
#include <forward_list>
#include <algorithm>
#include <iostream>

int main() {
    std::list<int> lst = {1, 2, 3, 4, 5};

    // Keep an iterator into the middle
    auto it = std::find(lst.begin(), lst.end(), 3);

    // Insert and erase elsewhere — it stays valid
    lst.push_front(0);
    lst.push_back(6);
    lst.erase(lst.begin()); // erase 0

    std::cout << *it << '\n'; // still 3 — valid!

    // splice: move elements between lists in O(1) — no copies
    std::list<int> other = {10, 20, 30};
    lst.splice(it, other); // insert entire 'other' before position it
    // 'other' is now empty; no elements were copied
}

The splice operation is unique to std::list: it transfers nodes between lists (or within the same list) in constant time, with no element construction or destruction. This makes list the natural choice when building intrusive LRU caches or task schedulers where items move between queues frequently.

std::forward_list saves the backward pointer per node but loses size(), bidirectional traversal, and push_back. Use it only when memory per-node is critical:

#include <forward_list>

std::forward_list<int> fl = {3, 1, 4, 1, 5};
fl.sort();              // O(n log n) — member sort, modifies list in place
fl.unique();            // remove consecutive duplicates: {1, 3, 4, 5}
fl.remove(4);           // remove all elements equal to 4

Flat Containers (C++23): Cache-Friendly Sorted Containers

std::flat_map and std::flat_set (C++23) provide the same sorted key interface as std::map and std::set but store elements in contiguous sorted vectors, making iteration and lookup dramatically more cache-friendly. They trade O(log n) insert/erase (with O(n) element movement) for much better constant factors on read-heavy workloads.

// Requires C++23
#include <flat_map>
#include <flat_set>
#include <string>
#include <iostream>

int main() {
    std::flat_map<std::string, int> scores;
    scores.emplace("alice", 90);
    scores.emplace("bob",   85);
    scores.emplace("carol", 92);

    // Iteration is cache-friendly: keys and values in sorted contiguous arrays
    for (const auto& [name, score] : scores) {
        std::cout << name << ": " << score << '\n';
    }

    // flat_set for fast membership testing over a small, rarely-mutated set
    std::flat_set<int> primes = {2, 3, 5, 7, 11, 13};
    std::cout << primes.contains(7) << '\n'; // 1
}

The internal layout keeps keys in one sorted vector and values in a parallel vector, so range iteration is equivalent to walking two arrays. Binary search (O(log n)) is faster in practice than the tree traversal of std::map because it never chases pointers.

Use flat_map/flat_set when:

• The container is built once (or rarely mutated) and read frequently.
• The key count is small to moderate (up to a few thousand).
• Cache performance matters more than O(1) insert.

Avoid them when frequent random insertions into the middle dominate — each such insert shifts O(n) elements.

Container Adapters: Choosing the Underlying Container

std::stack, std::queue, and std::priority_queue are thin wrappers that restrict a sequence container's interface rather than providing new storage structures. The default underlying containers are sensible for most uses, but you can swap them for a different sequence container to change the performance characteristics.

#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <functional>
#include <iostream>

int main() {
    // stack defaults to deque; use vector for slightly better cache performance
    std::stack<int, std::vector<int>> stk;
    stk.push(1); stk.push(2); stk.push(3);
    std::cout << stk.top() << '\n'; // 3
    stk.pop();

    // queue defaults to deque — the right choice since both ends are needed
    std::queue<int> q;
    q.push(10); q.push(20); q.push(30);
    std::cout << q.front() << ' ' << q.back() << '\n'; // 10 30
    q.pop();

    // priority_queue defaults to vector with heap algorithms (max-heap)
    std::priority_queue<int> max_heap;
    max_heap.push(5); max_heap.push(1); max_heap.push(9);
    std::cout << max_heap.top() << '\n'; // 9

    // Min-heap: use greater<int> as the comparator
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
    min_heap.push(5); min_heap.push(1); min_heap.push(9);
    std::cout << min_heap.top() << '\n'; // 1
}

The default underlying containers are almost always correct. Switch to vector for stack only after profiling — the push-back path is slightly faster, but you lose push_front. Never use vector for queue; it would make pop_front O(n). The priority_queue virtually always stays on vector because the heap algorithms require random access.

std::unordered_map Internals: Hashing and Load Factor

std::unordered_map stores elements in an array of buckets, where each bucket is a linked list of elements that hash to the same slot. Lookup is O(1) on average because a good hash function spreads elements across buckets, making each list length ≈ 1. When too many elements crowd into a single bucket (a collision), performance degrades toward O(n).

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

int main() {
    std::unordered_map<std::string, int> m;

    // Reserve buckets up front to avoid rehashing as you insert
    m.reserve(1000);

    m["alpha"] = 1;
    m["beta"]  = 2;

    std::cout << "bucket count: " << m.bucket_count() << '\n';
    std::cout << "load factor:  " << m.load_factor()  << '\n'; // elements / buckets
    std::cout << "max load:     " << m.max_load_factor() << '\n'; // typically 1.0

    // When load_factor() exceeds max_load_factor(), rehash doubles the bucket array
    // and invalidates ALL iterators
}

Custom hash for user-defined types. By default there is no std::hash specialization for your own structs. You must provide one:

#include <unordered_map>
#include <functional>
#include <string>

struct Point { int x, y; };

struct PointHash {
    std::size_t operator()(const Point& p) const noexcept {
        // Combine hashes with XOR + bit rotation (simple but effective)
        auto hx = std::hash<int>{}(p.x);
        auto hy = std::hash<int>{}(p.y);
        return hx ^ (hy << 32 | hy >> 32);
    }
};

struct PointEq {
    bool operator()(const Point& a, const Point& b) const noexcept {
        return a.x == b.x && a.y == b.y;
    }
};

std::unordered_map<Point, std::string, PointHash, PointEq> labels;
labels[{0, 0}] = "origin";
labels[{1, 2}] = "P1";

A common pattern is to use boost::hash_combine (or a hand-rolled equivalent) to mix multiple field hashes. A poor hash that returns the same value for all inputs causes every operation to degrade to O(n).

emplace vs insert: Constructing In Place

emplace_back (and emplace, emplace_hint, etc.) constructs an element directly inside the container's storage using forwarded constructor arguments, eliminating an extra copy or move. push_back(T(args...)) first constructs a temporary T, then moves it into the container — two operations instead of one.

#include <vector>
#include <string>
#include <iostream>

struct Widget {
    int id;
    std::string name;

    Widget(int i, std::string n) : id(i), name(std::move(n)) {
        std::cout << "constructed " << name << '\n';
    }
};

int main() {
    std::vector<Widget> v;
    v.reserve(4);

    // push_back: constructs a temporary, then moves it in — 1 ctor + 1 move
    v.push_back(Widget{1, "alpha"});

    // emplace_back: constructs directly in the vector — 1 ctor, 0 moves
    v.emplace_back(2, "beta");

    // For containers with keys, emplace avoids temporaries for both key and value
    #include <map>
    // std::map<int, Widget> m;
    // m.emplace(3, 3, "gamma"); // directly constructs Widget in the map node
}

The practical advice: use emplace_back when you are providing constructor arguments, and push_back when you already have a fully-formed object (the compiler will move it either way). emplace on std::map and std::unordered_map uses std::piecewise_construct to forward arguments for key and value separately:

#include <map>
#include <string>

std::map<int, std::string> m;
m.emplace(std::piecewise_construct,
          std::forward_as_tuple(42),
          std::forward_as_tuple(5, 'x')); // constructs string("xxxxx") in-place

One caution: emplace on associative containers does not check for an existing key before constructing the element — it may construct and then discard. Use try_emplace (C++17) to avoid this waste:

#include <unordered_map>
#include <string>

std::unordered_map<int, std::string> m;
m.try_emplace(1, "hello");  // constructs only if key 1 is absent
m.try_emplace(1, "world");  // key 1 exists — no construction, no side effect

Multi-Key Containers: multimap and multiset

std::multimap and std::multiset allow multiple elements with the same key, and equal_range retrieves all of them in O(log n). They share the same red-black tree implementation as map and set and offer the same O(log n) complexity for all operations.

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

int main() {
    // Each student can have multiple grades
    std::multimap<std::string, int> grades;
    grades.emplace("alice", 88);
    grades.emplace("alice", 92);
    grades.emplace("bob",   75);
    grades.emplace("alice", 79);

    // equal_range returns a pair of iterators bracketing all "alice" entries
    auto [begin, end] = grades.equal_range("alice");
    for (auto it = begin; it != end; ++it) {
        std::cout << it->first << ": " << it->second << '\n';
    }
    // alice: 88
    // alice: 92
    // alice: 79  (insertion order within equal keys is preserved by the tree)

    // count() tells you how many entries exist for a key
    std::cout << grades.count("alice") << '\n'; // 3
}

std::multiset is the key-only version, useful for counting occurrences or maintaining a sorted bag:

#include <set>

std::multiset<int> bag = {3, 1, 4, 1, 5, 9, 2, 6, 5};
// bag: {1, 1, 2, 3, 4, 5, 5, 6, 9}
std::cout << bag.count(1) << '\n'; // 2
std::cout << bag.count(5) << '\n'; // 2
bag.erase(bag.find(1)); // erase exactly one 1, not both

Note: erasing by value (bag.erase(1)) removes all matching elements. To remove only one occurrence, get an iterator with find and erase that single iterator.

For unordered multi-key storage, std::unordered_multimap and std::unordered_multiset provide O(1) average operations with the same semantics.

Container Selection Guide

Choosing the right container eliminates whole classes of performance problems before any profiling is needed. The decision comes down to four questions: does order matter, do you need pointer stability, what operations dominate, and how large is the collection?

The decision tree from the earlier section still applies — use it to get to the right family, then use this table to pick within the family.

What's Next

• Iterators — how to navigate containers, and which iterator category each container provides.
• STL Algorithms — sort, find, transform, and fifty other operations that work with any container's iterators.
• Iterator Invalidation — full invalidation rules for every container operation.