Choosing a C++ container: complexity and speed

The C++ standard library offers more than a dozen containers, and choosing one comes down to two questions: which operations does your program perform most often, and which guarantees does it need? Start with std::vector. Its elements sit next to each other in one block of memory, so it is the fastest container to loop over and to index, and adding at the end takes amortised constant time. Choose another container when an operation that a vector does badly dominates the work, such as adding at the front or finding values by key in a large collection, or when you need a guarantee that a vector cannot give: keys kept in sorted order, or references that stay valid while elements are added.

This lesson sorts the containers into families and lists what the C++ standard promises about the cost of each operation. Then it measures what those promises leave out: how much memory each container uses per element, and how long a lookup really takes at sizes from a thousand to a million elements, with two compilers. The numbers are evidence from one machine, not laws, and the last section shows how to measure your own case.

Four families of containers

Every standard container owns its elements: it creates them, keeps them and destroys them. How it stores them is what sets the families apart:

• Sequence containers, array, vector, deque, list and forward_list, keep the elements in the order you put them: in one block (array, vector), in fixed-size blocks (deque) or in one node per element (list, forward_list).
• Ordered associative containers, set, map, multiset and multimap, keep them sorted by key, one node per element, in a balanced tree.
• Unordered associative containers, unordered_set, unordered_map, unordered_multiset and unordered_multimap, keep them in buckets chosen by a hash of the key, one node per element.
• Container adaptors, stack, queue and priority_queue, and since C++23 flat_set, flat_map, flat_multiset and flat_multimap, keep them inside other containers, behind a narrower or different interface.

A few details matter later:

• The multi versions allow several elements with the same key; the others keep each key once.
• The standard never says “red-black tree” or “hash table”. It specifies each operation’s cost and which iterators and references stay valid, and those rules are hard to meet any other way: libc++ and libstdc++ both build std::map as a red-black tree and std::unordered_map as an array of buckets, each holding a chain of nodes.
• The flat containers are adaptors because they keep their elements in other containers, by default std::vectors kept in sorted order. A flat_map uses one vector for the keys and another for the values.
• std::span and std::string_view look like containers but are views: they refer to elements that something else owns.

For a first choice, ask four questions in order. The first answer “yes” names the container to start with:

What the standard guarantees

The standard states the cost of every container operation as an upper bound on the work it does: comparisons, hash calls, copies or moves of elements. Two words in it need care. Amortised means averaged over a long run of calls: one push_back on a full vector moves every element, but doubling the capacity keeps the average cost per call constant. On average, for the unordered containers, assumes a hash function that spreads the keys over the buckets; when many keys share a bucket, a lookup compares the key with each of them, and the worst case is linear.

For the sequence containers:

• Element at position i: O(1) in a vector and a deque; O(i) in a list, which has to walk from one end.
• Add or remove at the back: O(1) amortised in a vector; O(1) in a deque and a list.
• Add or remove at the front: O(n) in a vector; O(1) in a deque and a list.
• Insert or erase in the middle: O(n) in a vector, whose later elements move, and in a deque, whose nearer end moves; O(1) in a list, once you hold an iterator to the place.
• Find a value: O(n) in all three, or O(log n) with a binary search when a vector or deque is sorted.

For the containers that look up by key:

• Find a key: O(log n) in a map or set and in a flat_map or flat_set; O(1) on average and O(n) at worst in an unordered_map or unordered_set.
• Insert a key: O(log n) in a map; O(1) on average and O(n) at worst in an unordered_map; O(n) in a flat_map, whose later elements move.
• Erase at an iterator: O(1) amortised in a map; O(1) on average in an unordered_map; O(n) in a flat_map.
• Visit the elements in key order: a map and a flat_map always list them in order; an unordered_map lists them in an unspecified order.
• Find the nearest key with lower_bound: O(log n) in a map and a flat_map; an unordered_map has no such function.

Four of these lines are worth reading twice:

• A vector has no push_front. The standard gives sequence containers push_front, push_back, operator[] and its other optional operations only where they take amortised constant time. Adding at the front of a vector moves every element, so the function does not exist; v.insert(v.begin(), x) still works, in linear time.
• A list inserts in constant time only once you hold an iterator to the place. Finding the place is a walk, which is linear, as a measurement below shows.
• A flat_map finds a key in O(log n), like a map, but inserts in O(n), because its keys sit sorted in a vector and every later key has to move to make room. The standard lists linear-time insertion and erasure of a single element as one of the ways the flat containers differ from the other associative containers.
• Big-O hides the constant factor. O(1) for a hash lookup includes computing the hash and following a pointer or two; O(log n) for a sorted vector is about 20 comparisons for a million elements, all inside one block of memory. The rest of the lesson measures what that means.

Memory per element

These costs count operations, not bytes. This program fills seven containers with the same 100,000 int values and asks each one, through an allocator that counts, how much memory it requested:

// What seven containers ask the allocator for while each holds the same 100,000 ints.
// Counting<T> is an allocator that adds up the bytes the container holds at the end and how many times it allocated;
// every standard container accepts an allocator as its last template argument.
#include <cstddef>
#include <cstdlib>
#include <deque>
#include <flat_set>
#include <forward_list>
#include <functional>
#include <list>
#include <new>
#include <print>
#include <set>
#include <unordered_set>
#include <vector>

struct Usage {
    std::size_t bytes = 0;        // bytes allocated and not yet freed
    std::size_t allocations = 0;  // calls to allocate, including buffers that were freed again
};
inline Usage usage;

template <class T>
struct Counting {
    using value_type = T;
    Counting() = default;
    template <class U>
    Counting(const Counting<U>&) noexcept {}
    T* allocate(std::size_t n) {
        usage.bytes += n * sizeof(T);
        ++usage.allocations;
        if (void* p = std::malloc(n * sizeof(T))) return static_cast<T*>(p);
        throw std::bad_alloc{};
    }
    void deallocate(T* p, std::size_t n) noexcept {
        usage.bytes -= n * sizeof(T);
        std::free(p);
    }
    friend bool operator==(Counting, Counting) { return true; }
};

template <class Container>
void measure(const char* name, int n) {
    usage = {};
    Container c;
    for (int i = 0; i < n; ++i) {
        if constexpr (requires { c.push_back(i); }) c.push_back(i);
        else if constexpr (requires { c.push_front(i); }) c.push_front(i);  // forward_list has no push_back
        else c.insert(i);
    }
    long long total = 0;
    for (int x : c) total += x;  // use the elements, so the compiler keeps every allocation
    std::println("{:<14} {:>9} {:>8.1f} {:>12} {:>14}", name, usage.bytes, double(usage.bytes) / n, usage.allocations, total);
}

int main() {
    const int n = 100'000;
    std::println("{} ints of {} bytes each", n, sizeof(int));
    std::println("{:<14} {:>9} {:>8} {:>12} {:>14}", "container", "bytes", "per int", "allocations", "sum (a check)");
    measure<std::vector<int, Counting<int>>>("vector", n);
    measure<std::deque<int, Counting<int>>>("deque", n);
    measure<std::list<int, Counting<int>>>("list", n);
    measure<std::forward_list<int, Counting<int>>>("forward_list", n);
    measure<std::set<int, std::less<int>, Counting<int>>>("set", n);
    measure<std::unordered_set<int, std::hash<int>, std::equal_to<int>, Counting<int>>>("unordered_set", n);
    measure<std::flat_set<int, std::less<int>, std::vector<int, Counting<int>>>>("flat_set", n);
}

from session import run

# memory.cpp built and run with Apple clang and libc++, then with GCC 16 and libstdc++: the two libraries lay out
# their nodes and buckets differently, so the numbers differ where the containers allocate nodes. The first command
# asks the processor for the size of its cache lines, the blocks in which it reads memory.
run("""
/usr/sbin/sysctl -n hw.cachelinesize
clang++ -std=c++23 -O2 -Wall -Wextra memory.cpp -o memory
./memory
g++-16 -std=c++23 -O2 -Wall -Wextra memory.cpp -o memory-gcc
./memory-gcc
""")

$ /usr/sbin/sysctl -n hw.cachelinesize
128
$ clang++ -std=c++23 -O2 -Wall -Wextra memory.cpp -o memory
$ ./memory
100000 ints of 4 bytes each
container          bytes  per int  allocations  sum (a check)
vector            524288      5.2           18     4999950000
deque             402432      4.0          106     4999950000
list             2400000     24.0       100000     4999950000
forward_list     1600000     16.0       100000     4999950000
set              3200000     32.0       100000     4999950000
unordered_set    3223016     32.2       100016     4999950000
flat_set          524288      5.2           18     4999950000
$ g++-16 -std=c++23 -O2 -Wall -Wextra memory.cpp -o memory-gcc
$ ./memory-gcc
100000 ints of 4 bytes each
container          bytes  per int  allocations  sum (a check)
vector            524288      5.2           18     4999950000
deque             410608      4.1          790     4999950000
list             2400000     24.0       100000     4999950000
forward_list     1600000     16.0       100000     4999950000
set              4000000     40.0       100000     4999950000
unordered_set    2983464     29.8       100014     4999950000
flat_set          524288      5.2           18     4999950000

An int takes 4 bytes, so 4 bytes per element would mean no overhead at all:

• vector and flat_set requested 524,288 bytes, 5.2 per element: the capacity doubled from 1 to 131,072 slots, which took 18 allocations. A reserve(100000) first would have made it one allocation of exactly 400,000 bytes.
• deque also needs about 4 bytes per element, kept in blocks: libc++ uses blocks of 4,096 bytes and libstdc++ blocks of 512 bytes, which is why the two libraries made 106 and 790 allocations.
• list requested 24 bytes per element in both libraries, and forward_list 16. A node holds the int and two pointers (list) or one (forward_list), padded to a multiple of 8 bytes, the alignment of a pointer.
• set took 32 bytes per element with libc++ and 40 with libstdc++. A tree node holds three pointers (left child, right child and parent) and a colour flag beside the value; libc++ fits the one-byte flag and the int into the same 8 bytes, while libstdc++ gives the colour a padded 8-byte slot of its own.
• unordered_set took about 30 bytes per element: a node per element plus an array of buckets of 8 bytes each. The libc++ node stores the element’s hash and takes 24 bytes; the libstdc++ node does not store the hash of an int and takes 16, but that library kept more buckets (172,933 against 102,877).

Each node-based container made 100,000 allocations, one per element, against 18 for the vector. These are the bytes the containers asked for; the allocator rounds small requests up and keeps bookkeeping of its own, so the real memory used by the node-based containers is higher still.

Memory matters for speed as well as for size. A processor reads memory in fixed blocks called cache lines, 128 bytes on the processor used here, as the first line of the output shows. In a vector, the next element is usually in a line already read, and the processor fetches the following lines ahead of time when a loop walks forward. In a node container, the next element can be anywhere, so each step may wait for memory. The C++ Core Guidelines turn this into a rule of their own (Per.19): access memory predictably.

Timing lookups at four sizes

Lookups by key are where the choice of container matters most often. This program stores n random 64-bit keys, each with a value, in four containers, and times lookups of keys that are present for n from 1,000 to 1,000,000:

• a std::vector of pairs sorted by key, searched with std::ranges::lower_bound, a binary search;
• std::map;
• std::unordered_map;
• std::flat_map.

// Times lookups of keys that are present in four containers holding the same n key-value pairs, for n from 1,000 to
// 1,000,000. Each container answers the same 16,384 random queries; a round times each container once, and the
// table shows the fastest of 9 rounds, because other programs can only make a run slower, never faster.
#include <algorithm>
#include <array>
#include <chrono>
#include <cstdint>
#include <flat_map>
#include <functional>
#include <map>
#include <print>
#include <random>
#include <unordered_map>
#include <utility>
#include <vector>

using Key = std::uint64_t;
using Clock = std::chrono::steady_clock;

int main() {
    std::mt19937_64 random(42);  // the engine's output is the same with every standard library
    const std::size_t queries_per_round = 16'384;
    const int rounds = 9;

    std::println("nanoseconds per lookup, fastest of {} rounds", rounds);
    std::println("{:>9} {:>14} {:>9} {:>19} {:>14}", "n", "sorted vector", "std::map", "std::unordered_map", "std::flat_map");
    for (std::size_t n : {1'000uz, 10'000uz, 100'000uz, 1'000'000uz}) {
        std::vector<std::pair<Key, Key>> items;  // random keys, each with its position as the value
        for (std::size_t i = 0; i < n; ++i) items.emplace_back(random(), i);
        std::vector<Key> queries;
        for (std::size_t i = 0; i < queries_per_round; ++i) queries.push_back(items[random() % n].first);

        auto sorted = items;
        std::ranges::sort(sorted);
        std::map<Key, Key> tree(items.begin(), items.end());
        std::unordered_map<Key, Key> hashed(items.begin(), items.end());
        std::flat_map<Key, Key> flat(items.begin(), items.end());

        // Each lookup adds the value it found, so the compiler cannot skip the work, and all four sums must agree.
        std::array<std::function<Key()>, 4> lookup_all{
            [&] { Key sum = 0; for (Key q : queries) sum += std::ranges::lower_bound(sorted, q, {}, &std::pair<Key, Key>::first)->second; return sum; },
            [&] { Key sum = 0; for (Key q : queries) sum += tree.find(q)->second; return sum; },
            [&] { Key sum = 0; for (Key q : queries) sum += hashed.find(q)->second; return sum; },
            [&] { Key sum = 0; for (Key q : queries) sum += flat.find(q)->second; return sum; },
        };
        std::array<double, 4> fastest;
        fastest.fill(1e300);
        std::array<Key, 4> sums{};
        for (int round = 0; round < rounds; ++round) {
            for (std::size_t c = 0; c < lookup_all.size(); ++c) {
                auto start = Clock::now();
                sums[c] = lookup_all[c]();
                std::chrono::duration<double, std::nano> took = Clock::now() - start;
                fastest[c] = std::min(fastest[c], took.count() / queries_per_round);
            }
        }
        bool agree = std::ranges::all_of(sums, [&](Key s) { return s == sums[0]; });
        std::println("{:>9} {:>14.1f} {:>9.1f} {:>19.1f} {:>14.1f}   same answers: {}", n, fastest[0], fastest[1], fastest[2], fastest[3], agree);
    }
}

from session import run

# lookups.cpp built with optimisation (-O2), as timings only mean something for optimised code, and run once with
# each compiler and its standard library. The first command names the processor the times come from.
run("""
/usr/sbin/sysctl -n machdep.cpu.brand_string
clang++ -std=c++23 -O2 -Wall -Wextra lookups.cpp -o lookups
./lookups
g++-16 -std=c++23 -O2 -Wall -Wextra lookups.cpp -o lookups-gcc
./lookups-gcc
""")

$ /usr/sbin/sysctl -n machdep.cpu.brand_string
Apple M5 Pro
$ clang++ -std=c++23 -O2 -Wall -Wextra lookups.cpp -o lookups
$ ./lookups
nanoseconds per lookup, fastest of 9 rounds
        n  sorted vector  std::map  std::unordered_map  std::flat_map
     1000           20.7      44.8                 6.1           21.6   same answers: true
    10000           48.7      98.1                11.0           45.3   same answers: true
   100000          105.1     312.7                24.6           97.1   same answers: true
  1000000          388.6    2088.0                34.3          362.1   same answers: true
$ g++-16 -std=c++23 -O2 -Wall -Wextra lookups.cpp -o lookups-gcc
$ ./lookups-gcc
nanoseconds per lookup, fastest of 9 rounds
        n  sorted vector  std::map  std::unordered_map  std::flat_map
     1000           55.3      44.4                 7.1           50.3   same answers: true
    10000           84.1     115.4                13.4           74.2   same answers: true
   100000          193.1     395.4                21.6          112.4   same answers: true
  1000000          256.7     990.0                32.3          214.4   same answers: true

The numbers change from run to run, but in every run on this machine the pattern was the same:

• std::unordered_map was the fastest at every size, with both compilers: a few nanoseconds per lookup at 1,000 elements and a few dozen at a million. A lookup computes one hash and usually reads one bucket and one node, however large the map grows.
• std::map was the slowest from 10,000 elements up. A lookup walks from the root through about 10 levels at 1,000 elements and 20 at a million, and once the tree no longer fits in the caches, most of those steps wait for memory.
• The sorted vector and std::flat_map stayed close to each other: both are binary searches over contiguous memory. At a million elements flat_map was usually ahead, because its search reads only the 8-byte keys, which sit in a vector of their own, while the sorted vector’s search reads 16-byte pairs.
• At 1,000 elements, GCC’s binary searches were slower than its std::map, while Clang’s were about twice as fast as its own. The next section shows why.

Times at a million elements vary most from one run to the next, because they depend on how much of the processor’s caches the other programs running at the same moment occupy.

Same code, two compilers

The C++ source was the same for both compilers, so the difference at 1,000 elements comes from the machine code. This file holds only the sorted vector’s lookup, and the session keeps the instructions that decide, at each step of the binary search, which half the search continues in:

// The lookup that lookups.cpp times in the sorted vector, as a function on its own, so that its machine code is easy
// to read: a binary search for the first pair whose key is not less than q.
#include <algorithm>
#include <cstdint>
#include <utility>
#include <vector>

using Key = std::uint64_t;

Key value_of(const std::vector<std::pair<Key, Key>>& sorted, Key q) {
    return std::ranges::lower_bound(sorted, q, {}, &std::pair<Key, Key>::first)->second;
}

from session import run

# lower_bound_value.cpp compiled to assembly (-S) by each compiler with -O2. grep keeps the instructions that decide
# which half the search continues in: csel is a conditional select, and b.lo, b.hs, bcc and bcs are conditional
# branches (Clang and GCC spell the same branch two ways).
run("""
clang++ -std=c++23 -O2 -S lower_bound_value.cpp -o clang.s
grep -E "csel|b[.]lo|b[.]hs|bcc|bcs" clang.s
g++-16 -std=c++23 -O2 -S lower_bound_value.cpp -o gcc.s
grep -E "csel|b[.]lo|b[.]hs|bcc|bcs" gcc.s
""")

$ clang++ -std=c++23 -O2 -S lower_bound_value.cpp -o clang.s
$ grep -E "csel|b[.]lo|b[.]hs|bcc|bcs" clang.s
	csel	x9, x9, x10, lo
	csel	x8, x11, x8, lo
$ g++-16 -std=c++23 -O2 -S lower_bound_value.cpp -o gcc.s
$ grep -E "csel|b[.]lo|b[.]hs|bcc|bcs" gcc.s
	bcc	L8

Clang turned the decision into two csel instructions, conditional selects, which pick one of two values without jumping anywhere. GCC turned it into bcc, a conditional branch. A processor guesses which way each branch goes before it knows, so that it can keep working; with random queries it guesses wrong about half the time, and every wrong guess throws work away. A thousand elements fit easily in the caches, so those wrong guesses dominate the cost. Big-O notation says nothing about this, and the same container gave a different ranking with each compiler.

Inserting into a sorted sequence: vector against list

A common argument for std::list is its constant-time insertion in the middle. This program keeps n random numbers in sorted order by inserting each one at its place, once in a vector and once in a list. Each container first walks from the front to the place:

// Keeps n random numbers in sorted order by inserting each one where it belongs, once in a std::vector and once in a
// std::list. Both must first walk to the right position; then the vector shifts the later elements up by one, while
// the list only links in a new node. Times are the fastest of 3 runs.
#include <algorithm>
#include <chrono>
#include <cstdint>
#include <list>
#include <print>
#include <random>
#include <vector>

using Clock = std::chrono::steady_clock;

template <class Container>
double fastest_ms(const std::vector<int>& values, long long& check) {
    double best = 1e300;
    for (int run = 0; run < 3; ++run) {
        auto start = Clock::now();
        Container c;
        for (int v : values) {
            auto pos = std::find_if(c.begin(), c.end(), [v](int x) { return x >= v; });  // walk to the position
            c.insert(pos, v);
        }
        std::chrono::duration<double, std::milli> took = Clock::now() - start;
        best = std::min(best, took.count());
        check = c.front() + c.back();
    }
    return best;
}

int main() {
    std::mt19937 random(7);
    std::println("{:>7} {:>12} {:>12}", "n", "vector ms", "list ms");
    for (int n : {1'000, 3'000, 10'000}) {
        std::vector<int> values;
        for (int i = 0; i < n; ++i) values.push_back(int(random() % 1'000'000));
        long long a = 0, b = 0;
        double v = fastest_ms<std::vector<int>>(values, a);
        double l = fastest_ms<std::list<int>>(values, b);
        std::println("{:>7} {:>12.2f} {:>12.2f}   same result: {}", n, v, l, a == b);
    }
}

from session import run

# sorted_insert.cpp built with -O2 and run with each compiler and its standard library.
run("""
clang++ -std=c++23 -O2 -Wall -Wextra sorted_insert.cpp -o sorted_insert
./sorted_insert
g++-16 -std=c++23 -O2 -Wall -Wextra sorted_insert.cpp -o sorted_insert-gcc
./sorted_insert-gcc
""")

$ clang++ -std=c++23 -O2 -Wall -Wextra sorted_insert.cpp -o sorted_insert
$ ./sorted_insert
      n    vector ms      list ms
   1000         0.11         0.35   same result: true
   3000         0.80         5.59   same result: true
  10000         8.47       499.49   same result: true
$ g++-16 -std=c++23 -O2 -Wall -Wextra sorted_insert.cpp -o sorted_insert-gcc
$ ./sorted_insert-gcc
      n    vector ms      list ms
   1000         0.11         0.38   same result: true
   3000         0.88         6.45   same result: true
  10000        10.14       581.24   same result: true

The vector won at every size with both compilers: about three times as fast at 1,000 numbers, and more than five times as fast at 3,000 and 10,000. Both containers spend most of the time walking to the place, and that walk is linear for both. The vector walks through neighbouring memory, while the list follows a pointer from node to node, and the nodes of a list kept in sorted order lie scattered in memory. The vector then shifts the later elements with one block move, which processors do quickly. A sorted vector could even find the place by binary search, O(log n), which a list cannot do because it has no random access.

The list’s constant-time insertion pays off when the program already holds an iterator to the place, for example one it kept from an earlier search, or when it moves whole runs of nodes from one list to another with splice, which never copies an element. The next lesson covers both.

How to measure your own case

The measurements above follow five rules, and so should yours:

1. Measure an optimised build, with the flags you ship. The examples use -O2; a build without optimisation mostly measures debugging code.
2. Use your real key and value types and your real sizes. Strings compare and hash at a very different speed from integers, and a container that fits in the caches behaves differently from one that does not.
3. Use the results. Each example adds up the values it found and checks that all containers agree; if the results were thrown away, the optimiser could delete the very work being timed.
4. Repeat, and keep the fastest run or look at the spread of many. Other programs only ever add time to a run.
5. Write down the machine and the compiler. The tables here come from one laptop processor, and the ranking changed when only the compiler changed.

The examples time with a few lines of std::chrono, which is enough to see differences of this size. For smaller differences, a benchmarking library such as nanobench, a single header file, handles warm-up, repetitions and the optimiser, and reports how much the runs vary. The C++ Core Guidelines (Per.6) say it in one line: don’t make claims about performance without measurements.

Your turn: eight programs, eight containers

Each of the first eight questions below describes a program. Choose the container you would start with, and compare your reasons with the explanation that appears once you answer. More than one container can work for some of them; the explanations say what each alternative would cost.

Interview questions

Fresher · Why does std::vector have no push_front, while std::deque and std::list do?

The standard offers push_front only on sequence containers that can do it in amortised constant time, and a vector cannot: its elements sit in one block of memory, so adding at the front means moving every element one place up, which is linear in the size. A deque keeps its elements in fixed-size blocks and can add a block in front, and a list just links in a new node, so both add at the front in constant time. A vector can still insert at the front with v.insert(v.begin(), x), which is fine for small vectors or rare insertions. A program that adds at the front often should use a deque, or build the sequence in reverse and call std::ranges::reverse once at the end.

Key takeaways

• Start with std::vector, and choose another container for a reason: work at the front, lookups by key, keys in order, or references that must survive insertions.
• The standard specifies the cost of every operation, not the data structure: map is O(log n), unordered_map is O(1) on average and O(n) at worst, and flat_map finds in O(log n) but inserts in O(n).
• Node-based containers allocate once per element and need several times the memory of the elements themselves: 24 bytes per int in a list, 32 or 40 in a set, depending on the library.
• In the lookup timings, unordered_map was the fastest at every size and std::map the slowest from 10,000 elements up; the sorted vector and flat_map were close to each other.
• The same source code ranked differently with GCC and Clang, because one compiled a decision into a branch and the other into a conditional select. Measure with your compiler, your data and your sizes.