C++ Reference ยท Containers
C++ container complexity
A Big-O table for the C++ standard containers: access, search, insert and erase costs for vector, deque, list, map, unordered_map and more.
Every standard container makes promises about how many steps an operation takes as the container grows. These promises are part of the standard, so you can rely on them when you choose a container. The table below lists the guarantees that matter most in daily work.
"Amortized constant" means that a single call can occasionally be expensive (a vector reallocating, a hash table rehashing), but a long series of calls averages out to constant time per call. Big-O says nothing about the constant factor: a contiguous std::vector often beats a node-based container with a better formula, because of CPU caches.
std::vector<int> v; // push_back: amortized O(1) std::set<int> s; // insert: O(log n) std::unordered_set<int> h; // insert: O(1) average, O(n) worst case
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.
The table
| Container | Access by index | Search | Insert / erase at end | Insert / erase at front | Insert / erase in middle |
|---|---|---|---|---|---|
vector |
O(1) | O(n) | amortized O(1) | O(n) | O(n) |
array |
O(1) | O(n) | not possible | not possible | not possible |
deque |
O(1) | O(n) | O(1) | O(1) | O(n) |
list |
no | O(n) | O(1) | O(1) | O(1) given an iterator |
forward_list |
no | O(n) | O(n) at end | O(1) | O(1) after an iterator |
set, map |
no | O(log n) | O(log n) | O(log n) | O(log n) |
unordered_set, unordered_map |
no | O(1) average, O(n) worst | O(1) average | O(1) average | O(1) average |
flat_set, flat_map |
no | O(log n) | O(n) | O(n) | O(n) |
priority_queue |
top O(1) | no | push, pop O(log n) | n/a | n/a |
Usage notes
- Contiguous wins in practice. For up to thousands of elements a sorted
std::vectorwith binary search, or aflat_map, is frequently faster thanstd::map, because neighbors in memory share cache lines. - Hash containers have a bad worst case. All keys landing in one bucket makes a lookup O(n). A good hash function and
max_load_factorkeep the average near constant. Rehashing is O(n) but amortized away. list::size()is constant time since C++11, butstd::liststill pays for one heap allocation per element and cannot be indexed.list::splicerelinks nodes between lists without copying or moving any element; splicing one element is O(1), and splicing a range costs time proportional to the range length when it comes from a different list.- Sorting.
std::sortis O(n log n) on random-access ranges.std::listhas its ownsortmember, also O(n log n), because it cannot usestd::sort. - Iterator invalidation is a separate promise: see Iterator invalidation.
- Measure. Complexity guides the choice, but profile before you tune; the constant factors differ by orders of magnitude.