C++ Reference ยท Algorithms
C++ algorithm complexity guarantees
What the C++ standard guarantees about the cost of algorithms: comparisons, swaps, iterator requirements, amortized time, and a cheat sheet from find to sort.
The C++ standard does not just say what each standard algorithm does; it also says how much work it may do. These complexity guarantees are part of the contract. They are stated as a number of specific operations (comparisons, applications of a predicate, swaps, assignments) in terms of N, the length of the range, and not as seconds. That is why you can reason about performance before you write any benchmark, and why a conforming library cannot quietly replace an O(n log n) sort with an O(nยฒ) one.
The guarantees also depend on the iterator category. std::lower_bound does O(log n) comparisons on any forward iterator, but it only makes O(log n) iterator steps on random-access iterators; on a std::list it still walks O(n) nodes. Reading a complexity guarantee therefore means reading two things: what is counted, and what the iterators cost.
std::find(v.begin(), v.end(), x); // at most N comparisons std::sort(v.begin(), v.end()); // O(N log N) comparisons, worst case (C++11) std::lower_bound(v.begin(), v.end(), x); // O(log N) comparisons, v must be sorted
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.
Syntax
There is no syntax: the guarantee is written in the description of each algorithm. These are the common phrasings.
| Phrase in the standard | Meaning |
|---|---|
| "Exactly N applications" | Always N calls of the predicate or function. for_each, transform, count. |
| "At most N applications" | Stops early when possible. find, all_of, any_of. |
| "At most N log N comparisons" | sort, stable_sort has "N log N, or N logยฒ N without extra memory". |
| "O(log N) comparisons" | lower_bound, upper_bound, binary_search, equal_range, push_heap, pop_heap. |
| "Linear" or "at most N-1" | adjacent_find, unique, is_sorted, merge, min_element, make_heap (3N). |
| "Amortized constant" | Cost averaged over many calls; vector::push_back. |
Returns: not applicable.
Errors / undefined behavior: a predicate or comparator that is not consistent can break the complexity guarantee as well as the result, and with some algorithms causes undefined behavior (see Writing comparators).
Usage notes
- Cheat sheet.
find,count,copy,fill,reverse,rotate,remove,unique,accumulate: O(n).sort,stable_sort,partial_sort(O(n log k)): O(n log n).nth_element: O(n) on average.binary_searchfamily: O(log n) comparisons.mergeand set operations: O(n + m). Heap functions:make_heapO(n),push_heapandpop_heapO(log n),sort_heapO(n log n). std::sortis O(n log n) in the worst case since C++11. Before that implementations could be quadratic on adversarial input.stable_sortuses extra memory when available to reach O(n log n); without it, O(n logยฒ n).- Iterator category changes the real cost.
std::distanceandstd::advanceare O(1) for random-access iterators but O(n) otherwise. A "logarithmic"lower_boundonstd::liststill performs O(n) iterator increments. Preferstd::set::lower_boundor sorted vectors for lookups. - Containers have their own guarantees:
vector::insertin the middle is O(n),list::spliceis O(1),unordered_map::findis O(1) on average and O(n) worst case. See Container complexity. - Hidden costs. The guarantee counts operations of the element type. Sorting a
vector<std::string>makes O(n log n) string comparisons, each of which can cost O(length). Sorting large objects moves a lot of data; sorting indices or pointers can be faster. - Expected versus worst case.
nth_elementandunordered_mapare average-case linear/constant. Do not use them where an attacker can choose the input without considering the worst case. - Stable and in-place do not always go together.
stable_sortandinplace_mergeallocate memory for speed and may throwstd::bad_allocon failure, falling back to slower code when allocation fails. - Measure. Big-O hides constants and caches: for small n a linear scan of a
vectoroften beatsstd::set. Count with a lambda as the first example does, or benchmark. - Parallel algorithms keep the same operation counts as upper bounds (with some slack) but divide the work between threads. See Execution policies.