Skip to content
Tutorials Center
My learning

Topics

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.

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

C++ Counting comparisons

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++ Front insertion costs

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::vector with binary search, or a flat_map, is frequently faster than std::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_factor keep the average near constant. Rehashing is O(n) but amortized away.
  • list::size() is constant time since C++11, but std::list still pays for one heap allocation per element and cannot be indexed.
  • list::splice relinks 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::sort is O(n log n) on random-access ranges. std::list has its own sort member, also O(n log n), because it cannot use std::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.