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. The programs in the std::list operations section and in “What the Tools Catch” were also built with Clang 18.1.3 against both libstdc++ 13 and libc++ 18, and are in a GitHub repository whose build repeats these checks on each commit.

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.

std::list Member Functions: remove, unique, sort, merge and splice

A std::list cannot use several of the general algorithms the way a std::vector can, and it does not need to. It has member functions that do the same jobs by relinking nodes, and in two cases they do something the general algorithm cannot do at all.

// list_operations.cpp - the operations std::list provides as member functions,
// and why each one exists instead of (or alongside) a generic algorithm.
#include <iostream>
#include <iterator>
#include <list>
#include <string>

static void print(const std::string& label, const std::list<int>& l)
{
    std::cout << label << " (size " << l.size() << "):";
    for (int x : l) std::cout << ' ' << x;
    std::cout << '\n';
}

int main()
{
    std::list<int> l{5, 3, 3, 8, 1, 3, 9};
    l.push_front(7);                         // O(1) at the front, which vector lacks
    l.push_back(2);
    print("start          ", l);

    l.remove(3);                             // erases every 3: the size changes
    print("remove(3)      ", l);

    l.remove_if([](int x) { return x > 8; });
    print("remove_if(>8)  ", l);

    std::list<int> dups{4, 4, 1, 4, 1, 1};
    dups.unique();                           // only *adjacent* duplicates
    print("unique unsorted", dups);
    dups.sort();
    dups.unique();
    print("sort + unique  ", dups);

    l.sort();                                // std::sort cannot take a list
    print("sort           ", l);

    std::list<int> more{0, 4, 6};            // must already be sorted
    l.merge(more);                           // relinks nodes; more is left empty
    print("merge          ", l);
    print("other after    ", more);

    std::list<int> tail{100, 200};
    auto it = std::next(tail.begin());       // points at 200
    l.splice(l.end(), tail, it);             // move one node between lists
    print("splice 200 in  ", l);
    print("tail after     ", tail);
    std::cout << "iterator still valid, now in l: " << *it << '\n';

    l.reverse();
    print("reverse        ", l);
}

Output (identical with GCC 13.3, Clang 18.1.3 with libstdc++, and Clang with libc++ 18):

start           (size 9): 7 5 3 3 8 1 3 9 2
remove(3)       (size 6): 7 5 8 1 9 2
remove_if(>8)   (size 5): 7 5 8 1 2
unique unsorted (size 4): 4 1 4 1
sort + unique   (size 2): 1 4
sort            (size 5): 1 2 5 7 8
merge           (size 8): 0 1 2 4 5 6 7 8
other after     (size 0):
splice 200 in   (size 9): 0 1 2 4 5 6 7 8 200
tail after      (size 1): 100
iterator still valid, now in l: 200
reverse         (size 9): 200 8 7 6 5 4 2 1 0

Each line shows something the generic version does differently:

• remove(3) changed the size from 9 to 6. The general std::remove cannot shrink a container, because it only has iterators; the member function owns the nodes and erases them.
• unique() removes only adjacent duplicates. On 4 4 1 4 1 1 it left 4 1 4 1. Sorting first, then calling unique(), removed every duplicate.
• merge() relinks rather than copies. Both lists must already be sorted. Afterwards the source list is empty: its three nodes now belong to l.
• splice() moved one node between lists, and the iterator to it stayed valid. It still printed 200, now as an element of l. This is the operation behind the splice measurement earlier in this article.

std::forward_list offers the same set with _after names (splice_after, erase_after), because a singly linked node can only reach the node after it.

What list::sort Does Not Do: Move Elements

std::sort puts a vector in order by moving values between positions. list::sort puts a list in order by changing which node points to which, and the values never move. This program sorts the same 1,000 records both ways and counts every copy and move of a Record:

// list_sort_moves.cpp - list::sort reorders nodes; std::sort on a vector moves
// values. Counts element copies and moves, and checks what an iterator held
// across the sort refers to afterwards.
#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include <random>
#include <vector>

static long g_copies = 0, g_moves = 0;

struct Record {
    int key;
    explicit Record(int k) : key(k) {}
    Record(const Record& o) : key(o.key) { ++g_copies; }
    Record(Record&& o) noexcept : key(o.key) { ++g_moves; }
    Record& operator=(const Record& o) { key = o.key; ++g_copies; return *this; }
    Record& operator=(Record&& o) noexcept { key = o.key; ++g_moves; return *this; }
};

static bool by_key(const Record& a, const Record& b) { return a.key < b.key; }

int main()
{
    constexpr int n = 1000;
    std::mt19937 gen(42);                    // the standard fixes mt19937's output sequence
    std::vector<int> keys(n);
    for (int& k : keys) k = static_cast<int>(gen() % 100000);

    std::list<Record> lst;
    std::vector<Record> vec;
    vec.reserve(n);
    for (int k : keys) { lst.emplace_back(k); vec.emplace_back(k); }

    auto lit = lst.begin();                  // first element, before sorting
    auto vit = vec.begin();
    const int first_key = lit->key;

    g_copies = g_moves = 0;
    lst.sort(by_key);
    std::cout << "list::sort   copies " << g_copies << ", moves " << g_moves << '\n';

    g_copies = g_moves = 0;
    std::sort(vec.begin(), vec.end(), by_key);
    std::cout << "std::sort    copies " << g_copies << ", moves " << g_moves << '\n';

    std::cout << "key before sort:            " << first_key << '\n'
              << "list iterator now refers to " << lit->key
              << " (same element, new position "
              << std::distance(lst.begin(), lit) << ")\n"
              << "vector iterator refers to   " << vit->key
              << " (whatever value is now at index 0)\n";
}

Output (GCC 13.3, libstdc++):

list::sort   copies 0, moves 0
std::sort    copies 0, moves 9621
key before sort:            37542
list iterator now refers to 37542 (same element, new position 359)
vector iterator refers to   7 (whatever value is now at index 0)

list::sort performed no copies and no moves; std::sort moved records 9,621 times with libstdc++ and 9,817 times with libc++ 18, where every other line of output was identical. The keys come from std::mt19937, whose output sequence the standard fixes, so both libraries sorted the same data.

The iterator lines show the practical consequence. The list iterator taken before sorting still refers to the record with key 37542; that record is now at position 359. The vector iterator still points at index 0, which now holds a different value. If your program keeps iterators or pointers to elements while it reorders them, a list keeps them meaningful. For records that are expensive to move, the zero-move sort is the other reason to choose one.

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.

Container Adaptors: stack, queue and priority_queue

std::stack, std::queue and std::priority_queue are not separate data structures. Each wraps another container (std::deque by default for the first two, std::vector for the priority queue) and exposes only the operations that fit one access pattern: last-in first-out, first-in first-out, or largest first. They have no iterators, so the selection ladder above still applies to the container underneath. The STL overview shows all three, including a min-heap built with std::greater.

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

What the Tools Catch

Breaking an invalidation rule is undefined behaviour, and undefined behaviour usually does not crash. Two tools are commonly used to catch it: AddressSanitizer (-fsanitize=address, in GCC and Clang) and libstdc++’s debug mode (-D_GLIBCXX_DEBUG, which replaces the containers with checked versions). This program performs five uses of an iterator or reference after the container has grown:

// invalidation_tools.cpp - uses an iterator or reference after the container
// has grown. Run under AddressSanitizer and under libstdc++'s debug mode
// (-D_GLIBCXX_DEBUG) to see which tool reports which case.
//   vector           iterator after push_back reallocates     (invalid)
//   deque-reference  reference after push_back at the end      (valid)
//   deque-iterator   iterator dereferenced after push_back     (invalid)
//   deque-walk       iterator advanced after push_back         (invalid)
//   unordered        iterator after the table rehashes         (invalid)
#include <cstdio>
#include <deque>
#include <string_view>
#include <unordered_map>
#include <vector>

int main(int argc, char** argv)
{
    const std::string_view mode = argc > 1 ? argv[1] : "";

    if (mode == "vector") {
        std::vector<int> v{1, 2, 3};
        auto it = v.begin();
        v.push_back(4);                       // capacity 3 -> reallocation
        std::printf("%d\n", *it);
    } else if (mode == "deque-reference") {
        std::deque<int> d{1, 2, 3};
        int& first = d.front();
        for (int i = 0; i < 100000; ++i) d.push_back(i);
        std::printf("%d\n", first);
    } else if (mode == "deque-iterator") {
        std::deque<int> d{1, 2, 3};
        auto it = d.begin();
        for (int i = 0; i < 100000; ++i) d.push_back(i);
        std::printf("%d\n", *it);
    } else if (mode == "deque-walk") {
        std::deque<int> d{1, 2, 3};
        auto it = d.begin();
        for (int i = 0; i < 100000; ++i) d.push_back(i);
        long sum = 0;
        for (int i = 0; i < 1000; ++i, ++it) sum += *it;
        std::printf("%ld\n", sum);
    } else if (mode == "unordered") {
        std::unordered_map<int, int> u{{1, 10}};
        auto it = u.find(1);
        const auto buckets_before = u.bucket_count();
        for (int i = 2; i < 10000; ++i) u[i] = i;
        std::printf("buckets %zu -> %zu, value %d\n", buckets_before, u.bucket_count(), it->second);
    } else {
        std::fprintf(stderr, "usage: invalidation_tools vector|deque-reference|deque-iterator|deque-walk|unordered\n");
        return 2;
    }
}

Each case was run under three builds of the same source: a plain -O2 build (three runs), AddressSanitizer, and debug mode. GCC 13.3, libstdc++:

The deque rows look contradictory but follow the standard’s rule for deque: inserting at either end invalidates every iterator but no reference. The element did not move, so the reference is valid. The iterator also holds a pointer to the deque’s internal block map, and that map was reallocated. Dereferencing used only the element pointer, so it printed the right value and AddressSanitizer saw a read of live memory. Advancing it crossed a block boundary through the freed map: the plain build crashed and AddressSanitizer reported the read. Debug mode tracks iterators rather than memory, so it reported the first use in both cases.

The unordered row is the same rule again: a rehash invalidates iterators but not references to elements. libstdc++’s nodes did not move, so it->second still printed 10, and neither tool reported anything. The code is still wrong, and only a rule followed in review, not a tool, will catch it.

AddressSanitizer reports invalid memory accesses, not invalid iterators. Use both tools in testing, and treat silence from either as the absence of evidence it could see.

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.
• std::list has member functions for a reason. remove, unique, sort, merge and splice relink nodes: list::sort sorted 1,000 records with zero copies or moves, and iterators followed their elements.
• Sanitizers catch invalid memory, not invalid iterators. AddressSanitizer missed a dereferenced deque iterator and a post-rehash unordered_map iterator; libstdc++’s debug mode caught the first and missed the second.

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 deque and unordered-container rows of the invalidation table are now exercised by invalidation_tools.cpp under AddressSanitizer and libstdc++’s debug mode (see “What the Tools Catch”). Two invalid cases produced no report from AddressSanitizer, and one produced none from either tool; the table states the standard’s rules, and the tools are not a substitute for them. The vector-versus-list and splice timings are still from one machine and were not rerun.

Source Code and Tests

The std::list and invalidation programs on this page are in the stl/containers directory of the MYCPLUS C++ examples repository.

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build
bash tests/run_tests.sh "$PWD/build"
bash tests/sanitizers.sh g++

What the build checks. On Linux with GCC and Clang it builds each program with warnings treated as errors and compares its output with the output shown here, including the std::sort move count. A libc++ job, a macOS job and a Windows job check the outputs every library must agree on, including zero copies and moves for list::sort. A sanitizer job checks that AddressSanitizer and libstdc++’s debug mode report the cases the table says they report, and that neither reports the valid deque reference. The cases no tool reports are printed, not asserted. The benchmark timings earlier in this article are not part of the build.