STL Containers in C++: How to Choose the Right One

Almost every guide to the C++ standard library containers hands you a complexity table and leaves. The table says std::list inserts in O(1) and std::vector inserts in O(n), so building a sorted sequence should favour the list. On the machine used for this article, building a sorted sequence of 20,000 integers took 27 ms with a vector and 742 ms with a list — with the same linear search in both. The table was not wrong. It was answering a different question from the one you asked.

This is the overview page for the container library: what each container is for, a complexity summary you can actually use, a five-step ladder for picking one, and the two measurements that explain why the ladder puts std::vector at the bottom as the default rather than std::list near the top. For a method-by-method treatment of the most common container, see the complete std::vector guide. Every program on this page was compiled and run for this article on Ubuntu 24.04 with GCC 13.3, using g++ -std=c++17 -Wall -Wextra with AddressSanitizer where noted; the examples this refresh replaces no longer build cleanly on a current compiler, so every code block here has been rewritten and run. Every timing, output block and sanitizer report is captured verbatim.

What Are STL Containers in C++?

STL containers are class templates in the C++ standard library that store collections of objects of a single type. They fall into three groups: sequence containers (vector, deque, list, forward_list, array) which keep elements in the order you put them; associative containers (map, set, multimap, multiset) which keep them sorted by key; and unordered associative containers (unordered_map, unordered_set and their multi- variants) which hash keys for average constant-time lookup. Each offers the same basic interface — begin(), end(), size(), empty() — so algorithms written against iterators work with all of them.

That shared interface is the point of the design. A container’s job is to own and organise storage; an iterator’s job is to present that storage as a sequence; an algorithm’s job is to work on sequences without knowing which container produced them. Change the container and the algorithm still compiles, provided the new container’s iterators meet what the algorithm asks for. std::sort needs random access, so it works on a vector and is rejected outright for a list — which is why std::list carries its own sort member.

Choosing a Container: The Short Answer

A first-pass ladder: work down it and stop at the first question you answer yes to. If two options still look plausible, the deciding factors are usually invalidation rules, memory overhead per element, and a measurement of your actual workload.

1. Looking things up by key, and you need them sorted by key? std::map or std::set. Ordered, logarithmic lookup, and you can walk a range.
2. Looking things up by key, with no ordering requirement? std::unordered_map or std::unordered_set. Average constant-time lookup, no ordering, worst case linear if your hash is poor.
3. Size fixed and known at compile time? std::array. No allocation, no capacity bookkeeping, and it still has begin() and end().
4. Adding and removing at both ends? std::deque. Constant time at either end, and it never invalidates references on an end insertion.
5. Anything else — and this is most of the time. std::vector.

std::vector is the default, not the consolation prize. Use something else when you have a reason you can name.

Notice which container is missing. std::list is not on the ladder, and the Why the Complexity Table Is Not Enough section below is the reason.

The Complexity Summary

Two columns of that table are routinely misread.

“Insert in the middle: O(1)” for std::list assumes you already have an iterator there. Getting one costs O(n), and the constant factor on that traversal is the subject of the next section. If you are searching before inserting, the list’s advantage evaporates before you use it.

“O(1) average” for the unordered containers is average, not guaranteed. A hash function that collides badly degrades every operation to linear. The ordered containers carry a logarithmic guarantee rather than an average, which is why std::map is still the right answer when worst-case latency matters more than average throughput.

The per-operation detail is on cppreference for std::vector and std::map, which state the guarantees the standard actually requires.

Why the Complexity Table Is Not Enough

Complexity describes how cost grows. It says nothing about the constant, and on modern hardware the constant is dominated by whether your data is contiguous. Here is the measurement.

The task: build a sorted sequence by inserting N random integers one at a time, each into its correct position. This is the workload every “use a list for frequent insertions” recommendation is imagining.

How this was measured

Reproduce it. Both benchmarks build with:

g++ -O2 -std=c++17 -Wall -Wextra bench.cpp -o bench
g++ --version    # gcc (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0

The harness seeds std::mt19937 with 12345 so the data is identical across containers and runs, discards two warm-up passes, averages five, and accumulates into a sink the optimiser cannot discard. The splice benchmark builds both containers before starting the clock — include construction and the list loses on allocation cost alone, which answers a different question.

The middle column is the control, and it is the one that matters. With the identical linear search in both containers — the same number of comparisons, the same algorithm — the vector is still about 30× faster at N = 20,000. That difference is not algorithmic. It is that scanning a vector is a straight walk through contiguous memory the prefetcher can predict, while scanning a list is a dependent pointer chase where every step must complete before the next address is known.

The fourth column is there because of a claim I got wrong in the first version of this page. std::lower_bound and std::binary_search require only forward iterators, so they compile and run perfectly well on a std::list. What they do not do is help: on a linked list, binary partitioning costs O(n log n) iterator advances where a linear scan costs O(n), and the measurement bears that out — lower_bound on the list was about 1.7× slower than simply scanning it.

So the vector’s second advantage is not that it can be binary-searched and a list cannot. It is that binary search is only worth doing when advancing an iterator is free, which is a property of contiguous storage. Comparing the two columns a working programmer would actually write — vector with binary search against list with linear search — the gap on this workload was about 130×, and roughly a quarter of that is the search strategy rather than the container.

Note the direction of travel. Across the three sizes tested the gap widened with N, which is the opposite of what the complexity table predicts — list’s O(1) insertion should matter more as the sequence grows, not less. That is the clearest possible sign that the table is not modelling the thing that dominates.

None of this makes std::list useless, and it is worth measuring the case where it wins. Moving an entire sequence onto the end of another — splice for the list, insert-and-clear for the vector — with both containers built before the clock starts:

The list time does not grow with N, because a whole-container splice is a handful of pointer writes however many elements are involved. At a million elements that is roughly four orders of magnitude, in std::list‘s favour. This is the shape of problem it was designed for.

So: consider std::list when you need stable iterators and references through modification, constant-time splicing, or repeated edits at a position you already hold. Not because a table said O(1).

Sequence Containers

std::vector — a dynamic array. Contiguous storage, constant-time indexing, amortised constant-time push_back. Reallocation copies or moves every element and invalidates everything, which reserve() avoids when you know the size in advance. This is the container to reach for by default, and the dedicated vector guide covers its methods in full.

std::deque — a double-ended queue, stored as a sequence of fixed-size chunks. Constant time at both ends and constant-time indexing, at the cost of an extra indirection per access and no contiguity guarantee. Its useful and under-advertised property: inserting at either end invalidates iterators but not references or pointers to existing elements.

std::array — a fixed-size array with a container interface. No dynamic allocation of its own — the elements live inside the array object, wherever you put that — and the size is baked into the type. Use it wherever you would have used a C array.

std::list and std::forward_list — doubly and singly linked lists. Covered above. forward_list exists to be as small as a linked list can be: one pointer per node and no size().

Two things are deliberately absent from the list above. std::basic_string is a contiguous sequence container in every technical sense, but it is specialised for text and is usually treated separately. And C++20 and C++23 added container-adjacent facilities worth knowing: std::span is a non-owning view over any contiguous sequence, which is what a function should take when it wants to read a vector without caring that it is one; and std::flat_map and std::flat_set are sorted containers backed by a contiguous vector — the interface of std::map with the cache behaviour measured above. Library support for the flat containers is still landing; neither GCC 13.3 nor 14.2 ships <flat_map> on this machine.

Associative Containers

std::map and std::set keep elements sorted, typically in a red-black tree. Logarithmic lookup, insertion and erasure. Because they are ordered you can ask for ranges — everything between two keys — which the hashed containers cannot answer at all.

std::unordered_map and std::unordered_set hash the key into a bucket. Average constant-time lookup, and usually faster than map in practice for pure lookup workloads. No ordering of any kind — not sorted, and not insertion order either — so iteration order is unspecified and may change when the container rehashes.

Choose on whether you need ordering or range queries. If you do not, the unordered version is usually faster; if you do, there is no contest because the hashed containers cannot do it.

Iterator Invalidation: The Rules That Actually Matter

Invalidation is where container choice turns into undefined behaviour, and the rules are more specific than “modifying a container invalidates iterators.”

std::list insertion invalidates nothing at all. Not the iterators near the insertion point, not any others:

std::list<int> li{1, 2, 3};
auto lit = li.begin();
li.insert(std::next(lit), 99);
std::cout << "list: iterator still valid after insert, reads " << *lit << '\n';
li.erase(std::next(lit));
std::cout << "list: still valid after erasing a different node, reads " << *lit << '\n';

Output:

list: iterator still valid after insert, reads 1
list: still valid after erasing a different node, reads 1

Clean under AddressSanitizer and UndefinedBehaviorSanitizer. Only an iterator to the erased element itself goes bad.

A reallocating std::vector insertion invalidates every iterator, including ones pointing before the insertion point — a detail that is easy to get backwards:

std::vector<int> v{1, 2, 3};
v.shrink_to_fit();
auto vit = v.begin();   // points at the first element
v.push_back(4);         // forces reallocation
std::cout << *vit;      // use-after-free

AddressSanitizer:

==119==ERROR: AddressSanitizer: heap-use-after-free on address 0x502000000010
READ of size 4 at 0x502000000010 thread T0
    #0 0x55e53ea2cd36 in main /home/claude/stl/invalid.cpp:21
freed by thread T0 here:
SUMMARY: AddressSanitizer: heap-use-after-free in main

The old storage was freed when the vector grew. The first element moved, so an iterator to it dangles even though nothing was inserted before it. Reserve enough capacity up front and no reallocation happens:

vector: size 3, capacity 3
vector: no reallocation (capacity 64), iterator reads 1

Do Not Inherit From STL Containers

It is tempting to write class MyVector : public std::vector<std::string> to add a helper or two. Standard containers do not have virtual destructors, so deleting a derived object through a pointer to the container is undefined behaviour — your destructor does not run. On this GCC and libstdc++ build, AddressSanitizer reports it:

class MyVector : public std::vector<std::string> {
    int* extra;
public:
    MyVector() : extra(new int[1000]) {}
    ~MyVector() { delete[] extra; }
};

std::vector<std::string>* p = new MyVector();
delete p;                       // MyVector::~MyVector never runs

==138==ERROR: AddressSanitizer: new-delete-type-mismatch
SUMMARY: AddressSanitizer: new-delete-type-mismatch in operator delete(void*, unsigned long)

Use composition — hold a std::vector as a member and expose what you need. If you want the container’s full interface without inheriting it, a using declaration or a handful of forwarding methods costs less than the bug. If free functions are what you actually want, write free functions: the standard algorithms already work on any container through its iterators.

Key Takeaways

• std::vector is the default container. Reach for something else only when you can name the reason — ordering, keyed lookup, fixed size, or growth at both ends.
• Complexity tables describe growth, not cost. With the same linear search in both, a vector beat a list by roughly 27× at 20,000 elements here, on memory layout — contiguous access, hardware prefetching and no per-element allocation, none of which the complexity table describes.
• std::list‘s O(1) insert assumes you already have the iterator. Finding the position costs O(n), and the traversal is pointer-chasing rather than a contiguous sweep.
• Use std::list for its real properties: insertion invalidates nothing, and splice moves elements between lists without copying. Not because a table said O(1).
• Unordered containers are O(1) average. A bad hash degrades them to linear; std::map‘s O(log n) has no such cliff.
• A reallocating vector insert invalidates iterators pointing before the insertion point too. reserve() up front when you know the size.
• Do not publicly inherit from an STL container. The destructors are not virtual; AddressSanitizer reports a new-delete-type-mismatch when you delete through a base pointer.

Frequently Asked Questions

Conclusion

The container library is small enough to learn properly: five sequence containers, four ordered associative ones, four unordered ones, and a shared iterator interface that makes them interchangeable from an algorithm’s point of view. The ladder near the top of this page will pick the right one for most code you write.

What takes longer to internalise is that the complexity table is a lower bound on understanding rather than the whole of it. It tells you how cost scales; it does not tell you that thirty times the constant factor can hide inside two identical O(n) scans. When a container choice actually matters to your program’s performance, the table narrows the field and a measurement settles it. The rest of our C++ programming guides work the same way, and if you are still building your foundations, the complete guide to C++ programming is the place to start.

What I Could Not Verify

Every measurement here comes from one machine: a single-core Ubuntu 24.04 VM running GCC 13.3 with libstdc++. No other compiler, standard library or hardware was tested, and the vector-versus-list result in particular is a cache-behaviour finding, so it is more hardware-dependent than most — a machine with a different cache hierarchy will produce different ratios, though the ordering should hold. The absolute milliseconds will not transfer. The benchmark measures one workload, sorted insertion, chosen because it is the case most often cited in favour of linked lists; a workload dominated by splicing or by stable references would favour std::list and this page does not measure that. The complexity table states the guarantees the standard requires, not what libstdc++ happens to do. The iterator-invalidation table is compiled from the standard’s rules; the vector and list rows were demonstrated with sanitizers, the deque and unordered_* rows were not independently tested.