C++ Reference ยท Containers
C++ standard containers overview
A guide to the C++ standard containers: sequence, associative, unordered and adapter types, what each one is good at, and a practical way to choose.
A container is a class template that owns a collection of elements and provides operations to add, find, visit and remove them. The C++ standard library groups them into four families: sequence containers (elements in a user-chosen order), ordered associative containers (sorted by key), unordered associative containers (hashed) and container adapters (a restricted interface on top of another container). C++23 added the flat containers, which store sorted data in contiguous arrays.
Choosing a container is mostly a question of which operations you do most. The default answer is std::vector: its elements are contiguous in memory, which modern CPUs love, and it is hard to beat even where the textbook complexity says a linked structure should win.
std::vector<int> v; // the default choice std::map<std::string, int> m; // sorted keys std::unordered_map<std::string, int> h; // fast lookup by hash
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Choosing a container
| Need | Container |
|---|---|
| Sequence, size known at compile time | std::array |
| Sequence, grows at the end (default) | std::vector |
| Fast push/pop at both ends | std::deque |
| Frequent insertion/removal in the middle with stable iterators | std::list (singly linked: std::forward_list) |
| Unique keys, sorted iteration, range queries | std::set, std::map |
| Unique keys, fastest average lookup, order doesn't matter | std::unordered_set, std::unordered_map |
| Duplicates allowed | std::multiset, std::multimap, std::unordered_multi* |
| Read-mostly sorted data, small and cache-friendly (C++23) | std::flat_set, std::flat_map |
| LIFO, FIFO, priority | std::stack, std::queue, std::priority_queue |
| Non-owning view of contiguous elements | std::span |
Usage notes
- Default to
std::vector. Switch only when you measure a problem or need a specific guarantee. - Complexity is not the whole story. A
std::listhas O(1) insertion but its nodes are scattered in memory; for small sizes a vector beats it. See container complexity. - Iterator invalidation differs:
list,mapandsetkeep iterators and references valid on insertion;vectoranddequemay not. See iterator invalidation. - Ordered vs unordered: ordered containers need
operator<(or a comparator) and iterate sorted; unordered ones needstd::hashand==and iterate in an unspecified order that can change between runs and implementations. - Common interface: most containers provide
begin()/end(),size(),empty(),clear(),swap()and comparison operators, so algorithms work across them. std::vector<bool>is special and not a normal container; see vector<bool>.- Move semantics make returning containers by value cheap; use
reserveandemplace_backto avoid copies. - Adapters do not expose iterators or all of the underlying container's members.
- Allocators: every container takes an allocator as its last template parameter; the
std::pmr::aliases use polymorphic memory resources.