Eleven lessons of containers come down to one question, and it is not "which container is fastest?".

It is: what will you actually do with this data?

The procedure

Answer these in order. The first one that applies decides it.

1. Is the size fixed at compile time? → std::array. No allocation, best cache behaviour, sizeof is the data.

2. Do you look elements up by key?

• Need sorted order or range queries → std::map / std::set
• Only exact lookup → std::unordered_map / std::unordered_set
• Built once, then only read → sorted std::vector (see below)

3. Do you push and pop at both ends? → std::deque.

4. Do you need iterators that survive insertion and removal? → std::list or std::map.

5. Everything else → std::vector.

Step 5 catches the large majority of cases, and that is correct. The standard's own guidance is to use std::vector unless you have a reason not to.

Three structures, same complexity, very different speed

std::map and a sorted std::vector are both O(log n) lookup. Here is what that is worth:

#include <algorithm>
#include <chrono>
#include <iostream>
#include <map>
#include <random>
#include <unordered_map>
#include <vector>

template <typename F>
long long time_us(F f) {
    auto t0 = std::chrono::steady_clock::now();
    f();
    auto t1 = std::chrono::steady_clock::now();
    return std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0).count();
}

int main() {
    const int N = 100000;
    std::vector<int> keys(N);
    std::mt19937 gen(42);
    for (int& k : keys) k = static_cast<int>(gen() % 1000000);

    // Three ways to store the same lookup table.
    std::map<int, int> tree;
    std::unordered_map<int, int> hash;
    std::vector<std::pair<int, int>> sorted;

    for (int k : keys) { tree[k] = k; hash[k] = k; }
    sorted.reserve(keys.size());
    for (int k : keys) sorted.push_back({k, k});
    std::sort(sorted.begin(), sorted.end());
    sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());

    long long sink = 0;

    auto tree_us = time_us([&] {
        for (int round = 0; round < 5; ++round)
            for (int k : keys) sink += tree.count(k);
    });
    auto hash_us = time_us([&] {
        for (int round = 0; round < 5; ++round)
            for (int k : keys) sink += hash.count(k);
    });
    auto sorted_us = time_us([&] {
        for (int round = 0; round < 5; ++round)
            for (int k : keys) {
                auto it = std::lower_bound(sorted.begin(), sorted.end(), std::pair<int,int>{k, 0});
                sink += (it != sorted.end() && it->first == k) ? 1 : 0;
            }
    });

    std::cout << "500k lookups over " << sorted.size() << " distinct keys:\n";
    std::cout << "  std::map:            " << tree_us << " us\n";
    std::cout << "  std::unordered_map:  " << hash_us << " us\n";
    std::cout << "  sorted std::vector:  " << sorted_us << " us\n";
    std::cout << "(sink " << sink << ")\n";

    // Memory: rough, but the ratio is the point.
    std::cout << "\napproximate bytes per element:\n";
    std::cout << "  sorted vector: " << sizeof(std::pair<int,int>) << " (exactly, contiguous)\n";
    std::cout << "  map node:      ~" << sizeof(std::pair<int,int>) + 4 * sizeof(void*)
              << " (pair + 3 pointers + colour, separately allocated)\n";
    return 0;
}

A representative run, compiled -O2:

500k lookups over 95186 distinct keys:
  std::map:            141447 us
  std::unordered_map:  9301 us
  sorted std::vector:  48917 us
(sink 1500000)

approximate bytes per element:
  sorted vector: 8 (exactly, contiguous)
  map node:      ~40 (pair + 3 pointers + colour, separately allocated)

The sorted vector beat std::map by 2.9×, and both are O(log n) doing the same number of comparisons. The entire difference is memory layout: the vector's binary search touches a handful of cache lines in one contiguous block, while the map's chases pointers to nodes scattered across the heap.

The hash table beat both, by 15× over the map. For pure exact-match lookup that is the expected result and it is why step 2 recommends it.

Memory is roughly 5× smaller for the vector — 8 bytes per element against about 40 for a red-black tree node, and the vector's are one allocation rather than 95,186.

The lesson is not "never use std::map". It is that complexity classes do not rank implementations. std::map earns its cost when you need stable iterators or interleaved insertions and lookups; when you build a table once and then query it, a sorted vector is strictly better on every axis.

The sorted-vector pattern

Worth writing out, because it is genuinely underused:

// Build phase — cheap appends, order does not matter yet.
// std::vector<std::pair<Key, Value>> table;
// table.reserve(expected);
// for (...) table.push_back({key, value});
//
// Freeze — one sort, then deduplicate.
// std::sort(table.begin(), table.end());
// table.erase(std::unique(table.begin(), table.end()), table.end());
//
// Query phase — O(log n), contiguous, cache friendly.
// auto it = std::lower_bound(table.begin(), table.end(), std::pair{key, Value{}});
// bool found = (it != table.end() && it->first == key);

The constraint is that it must be built once. An insertion after freezing is O(n), so this is for tables loaded at startup and then read: configuration, lookup tables, static indexes, interned strings.

The traps, collected

Each of these was measured in this module:

| Trap | Lesson | |---|---| | v.insert(v.begin(), x) in a loop is O(n²) — 326 ms for 100k | 13.3 | | std::list is slower than std::vector even where lists "should" win — 69× | 13.3 | | map["missing"] silently inserts | 13.4 | | A comparator that ignores a field silently merges elements | 13.4 | | unordered_map iteration order is unspecified and must never be relied on | 13.5 | | std::sort on a std::list does not compile — use l.sort() | 13.2 | | std::remove does not remove; use C++20 std::erase | 13.3 | | Any modification can invalidate iterators, spans, and references | 13.1, 13.11 | | <= in a comparator is undefined behaviour, and crashes inside the sort | 13.8 | | A view or span over a temporary dangles | 13.9, 13.11 |

Interface guidance

Two rules that outlive any choice of container:

Take the most general parameter that works. A function that reads contiguous numbers should take std::span<const int> (lesson 13.11), not const std::vector<int>& — it then accepts arrays, sub-ranges, and future containers. For text, std::string_view.

Return by value. Return a std::vector, not a view over something you own. Copy elision and move semantics (lesson 9.9) make this free, and it makes the ownership unambiguous.

Following both means the container choice stays an implementation detail you can change later, which is worth more than getting it right the first time.

Try it

Checkpoint

• Choose by access pattern, not by reputation. Ask what you will do with the data.
• Fixed compile-time size → std::array. Key lookup → map or unordered_map. Otherwise std::vector.
• Complexity classes do not rank implementations: a sorted vector beat std::map by 2.9× at the same O(log n).
• Memory: ~8 bytes per element contiguous, against ~40 in a separately allocated tree node.
• A sorted vector is the right answer for a table built once and then only read.
• std::unordered_map won pure lookup by 15× — but cannot answer a range query at all.
• Take std::span / std::string_view parameters; return by value.
• Every trap in this module was measured, not asserted — do the same in your own code.