Skip to content
Tutorials Center
My learning

Topics

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.

C++
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

C++ One data set, four containers

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.

C++ Adapters and choosing by operation

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::list has O(1) insertion but its nodes are scattered in memory; for small sizes a vector beats it. See container complexity.
  • Iterator invalidation differs: list, map and set keep iterators and references valid on insertion; vector and deque may not. See iterator invalidation.
  • Ordered vs unordered: ordered containers need operator< (or a comparator) and iterate sorted; unordered ones need std::hash and == 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 reserve and emplace_back to 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.