Which Container?

Quick Answer

Sequential (ordered by position)?
  Yes ↓
    Size known at compile time?
      Yes → std::array<T, N>
      No ↓
        Need O(1) front insertion?
          Yes → std::deque
          No  → std::vector  ← default sequential container

Keyed by value (associative)?
  Yes ↓
    Need sorted order / range queries?
      Yes → std::map / std::set
      No  → std::unordered_map / std::unordered_set  ← faster lookups

Need priority queue?
  Yes → std::priority_queue

Need FIFO?
  Yes → std::queue (wraps deque)

Need LIFO?
  Yes → std::stack (wraps deque/vector)

Sequential containers

std::vector<T> — default choice

Contiguous heap storage. O(1) random access, amortized O(1) push_back, O(n) insert/erase in middle.

std::vector<int> v;
v.reserve(100);          // avoid reallocations
v.push_back(42);
v.emplace_back(43);

Choose vector when: you don't know the size at compile time, you iterate more than you insert/erase, you need random access.

std::array<T, N> — fixed size, stack allocated

std::array<int, 5> a = {1, 2, 3, 4, 5};
a[2] = 99;   // no bounds check
a.at(2);     // bounds-checked

Choose array when: size is known at compile time, you want stack allocation, you need the STL iterator/algorithm interface on a fixed array.

std::deque<T> — double-ended queue

Paged storage. O(1) push/pop at both ends, O(1) random access (slower than vector due to indirection).

std::deque<int> dq;
dq.push_front(0);   // efficient — vector can't do this
dq.push_back(1);

Choose deque when: you frequently insert/remove at both ends.

std::list<T> — doubly-linked list

O(1) insert/erase anywhere if you have an iterator, no random access.

Choose list rarely: cache-unfriendly, large per-element overhead. Only if you have iterators to positions that must remain valid across many insertions/deletions.

std::forward_list<T> — singly-linked list

Minimal overhead version of list. Even rarer.

Associative containers

std::map<K, V> — sorted by key

Red-black tree. O(log n) insert/find/erase. Keys are sorted; range queries work.

std::map<std::string, int> scores;
scores["Alice"] = 95;
auto it = scores.find("Alice");
// Iterate in sorted order:
for (const auto& [name, score] : scores) { ... }

Choose map when: you need sorted keys or range iteration (lower_bound, upper_bound).

std::unordered_map<K, V> — hash map

Average O(1) insert/find/erase. No order guarantees.

#include <unordered_map>
std::unordered_map<std::string, int> lookup;
lookup["key"] = 42;
lookup.contains("key");   // true (C++20)

Choose unordered_map when: you only need key lookup (no ordering) and performance matters. Roughly 2-5× faster than map for lookups.

std::set<T> / std::unordered_set<T>

Same as map/unordered_map but keys only (no mapped value).

std::unordered_set<int> seen;
if (seen.insert(x).second) {
    // x was not previously seen
}

std::multimap / std::multiset

Allow duplicate keys. Rarely needed — often map<K, vector<V>> is cleaner.

Priority queue

#include <queue>

// Max-heap by default
std::priority_queue<int> pq;
pq.push(3); pq.push(1); pq.push(4);
pq.top();   // 4 — largest element
pq.pop();

// Min-heap
std::priority_queue<int, std::vector<int>, std::greater<int>> minpq;

Comparison table

† requires iterator to position

C++23: flat_map and flat_set

std::flat_map<K, V> and std::flat_set<K> store keys and values in sorted contiguous arrays instead of a tree. They offer better cache performance for read-heavy workloads with small-to-medium sizes:

#include <flat_map>  // C++23

std::flat_map<std::string, int> scores;
scores.emplace("Alice", 95);
scores.emplace("Bob",   87);

// Iteration: same O(log n) lookup but elements are contiguous in memory
// Faster for small N (< ~1000 elements) vs std::map due to cache locality
auto it = scores.find("Alice");

Choose flat_map/flat_set over map/set when:

• Read-heavy (many lookups, few insertions)
• N is small-to-medium (< few thousand elements)
• Cache efficiency matters more than worst-case insert cost

Stick with map/set when:

• Frequent insertions/deletions (flat containers are O(n) for insert)
• You need stable iterators across modifications

std::span<T> — non-owning view (C++20)

std::span is not a container — it's a non-owning view over contiguous memory. Use it as a function parameter instead of const vector<T>& to accept any contiguous range:

#include <span>

void process(std::span<const int> data) {
    for (int v : data) { /* ... */ }
}

std::vector<int> v = {1, 2, 3};
int arr[] = {4, 5, 6};

process(v);           // works
process(arr);         // works
process({v.data(), 2}); // first 2 elements only

std::span<T, N> with a fixed extent is a zero-overhead view of exactly N elements, usable in constexpr contexts.

std::bitset<N> — fixed-size bit array

#include <bitset>

std::bitset<64> flags;
flags.set(3);          // set bit 3
flags.reset(3);        // clear bit 3
flags.flip(3);         // toggle bit 3
flags.test(3);         // read bit 3 (bounds-checked)
flags.count();         // number of 1 bits
flags.to_ulong();      // as unsigned long

Use bitset for a fixed-size set of boolean flags. For a dynamic-size bit array, use std::vector<bool> (packs bits) or a third-party bitset library.

Capacity and performance in practice

vector::reserve — avoid reallocations

Every time vector runs out of capacity it allocates a new buffer (2× size) and moves all elements. This is O(n) amortized, but the individual reallocation events are expensive:

// Bad: 10+ reallocations if n is large
std::vector<Widget> v;
for (int i = 0; i < n; ++i) v.push_back(Widget{i});

// Good: one allocation
std::vector<Widget> v;
v.reserve(n);
for (int i = 0; i < n; ++i) v.push_back(Widget{i});

// Shrink after bulk removal:
v.shrink_to_fit();   // release excess capacity

Cache friendliness: vector beats list and map

Big-O complexity doesn't tell the full story. A vector<T> of 10,000 elements with a linear scan typically beats a list<T> linear scan by 5-10× because:

• vector elements are contiguous in memory — prefetcher loads them in bulk
• list nodes are scattered on the heap — each node access is a cache miss

Rule: even when list has better asymptotic complexity for your operation, benchmark before switching. vector with linear search often wins for N < 10,000 due to cache effects.

unordered_map gotchas

std::unordered_map<std::string, int> m;

// GOTCHA: operator[] default-inserts 0 if key is missing
int x = m["missing_key"];   // creates {"missing_key": 0} in the map!

// Safe alternatives:
auto it = m.find("key");
if (it != m.end()) use(it->second);

if (m.contains("key")) use(m.at("key"));   // C++20

For user-defined key types, you must provide a hash:

struct Point { int x, y; };

struct PointHash {
    std::size_t operator()(const Point& p) const noexcept {
        return std::hash<int>{}(p.x) ^ (std::hash<int>{}(p.y) << 32);
    }
};

std::unordered_map<Point, int, PointHash> grid;

Iterator invalidation cheat sheet

Rule of thumb

Default to std::vector. Use std::unordered_map for key-value lookups. Use std::map only when you need sorted iteration or range queries. Prefer flat_map/flat_set (C++23) over map/set for small read-heavy tables. Use std::span for function parameters instead of const vector&.