C++ Reference ยท Algorithms
C++ standard algorithms overview
Overview of the C++ standard algorithms: categories, how iterator ranges work, the std::ranges versions, complexity, and how to choose the right function.
The standard library ships more than a hundred algorithms in <algorithm>, <numeric> and <memory>. They are free functions that work on ranges of elements, not on containers directly. A classic algorithm receives two iterators, first and last, describing the half-open range [first, last), so the same std::sort works on a std::vector, a std::deque, a plain array and a std::string.
Since C++20 almost every algorithm has a second form in std::ranges that takes a whole range (std::ranges::sort(v)), checks its requirements with concepts, accepts projections, and returns richer results. Use the plain std:: versions when you need iterators or an older standard, and the ranges:: versions in new code. Prefer a named algorithm over a hand-written loop: the name says what the code does.
#include <algorithm> std::vector<int> v{3, 1, 2}; std::sort(v.begin(), v.end()); // classic std::ranges::sort(v); // C++20
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
template<class It, class Pred> It std::find_if(It first, It last, Pred pred); // classic template<std::ranges::input_range R, class Proj = std::identity, /*...*/> std::ranges::borrowed_iterator_t<R> std::ranges::find_if(R&& r, Pred pred, Proj proj = {});
| Category | Typical algorithms |
|---|---|
| Searching | find, find_if, search, adjacent_find, binary_search, lower_bound |
| Counting and predicates | count, count_if, all_of, any_of, none_of, equal, mismatch |
| Copying and moving | copy, copy_if, copy_n, move, swap_ranges |
| Transforming | transform, replace, fill, generate, iota, for_each |
| Removing and reordering | remove, unique, reverse, rotate, shuffle, partition |
| Sorting | sort, stable_sort, partial_sort, nth_element, is_sorted |
| Sorted ranges | merge, set_union, set_intersection, includes, equal_range |
| Heaps | make_heap, push_heap, pop_heap, sort_heap |
| Min and max | min, max, minmax, min_element, clamp |
Numeric (<numeric>) |
accumulate, reduce, partial_sum, inner_product, gcd, lcm |
Returns: it depends on the algorithm. Searching functions return an iterator to the result, or last if nothing was found. Counting functions return a count, predicates a bool, and modifying algorithms usually return an iterator to the end of what they wrote.
Usage notes
- Algorithms never change the container's size.
remove,uniqueandcopyonly move or overwrite elements. To shrink the container, callerase(the erase-remove idiom) or usestd::erase/std::erase_if(C++20). - Output ranges must be large enough.
std::copyinto an empty vector writes past the end, which is undefined behavior. Resize first, or usestd::back_inserter. - The range must be valid.
firstandlastmust come from the same container andlastmust be reachable fromfirst. Mixing iterators from two containers is undefined behavior. - Preconditions on sorted data.
binary_search,lower_bound,mergeandset_*require input sorted by the same ordering you pass (oroperator<). Using them on unsorted data gives wrong answers. - Comparators must be strict weak orderings.
<is fine;<=is not. See Writing comparators. - Complexity is part of the standard.
sortis O(n log n) comparisons,findis linear,binary_searchis logarithmic with random access iterators. See Algorithm complexity. - Iterator category matters.
sortneeds random-access iterators, so it cannot sort astd::list(uselist::sort).std::rangesalgorithms check this at compile time with clear errors. - Execution policies (C++17). Many algorithms accept
std::execution::paras the first argument to run in parallel. See Execution policies. - Lambdas make them readable. Capture sparingly, and do not rely on the order in which a predicate is called.