STL Algorithms Overview
Complete guide to <algorithm> and std::ranges algorithms — sorting, searching, transforming, partitioning, and parallel execution.
STL Algorithmssince C++98Generic functions in <algorithm> that operate on iterator-delimited half-open ranges to sort, search, transform, and partition sequences — decoupled from any specific container type.
Overview
The <algorithm> header exposes over 100 algorithms built on one abstraction: a half-open range [first, last) described by two iterators. The algorithm is indifferent to what those iterators point into — std::vector, a raw array, a std::deque, or a custom container — which is the source of their reusability.
C++20 introduced two upgrades. First, std::ranges::* counterparts that accept range objects directly, eliminating the repetitive .begin()/.end() boilerplate. Second, projections — a callable applied to each element before comparison — letting you sort by a member field without writing a comparator.
// C++98/11: iterator-pair form
std::sort(v.begin(), v.end());
std::sort(v.begin(), v.end(), std::greater<int>{});
// C++20: ranges form — accepts the container directly
std::ranges::sort(v);
std::ranges::sort(v, std::greater{});
// C++20: projection — sort by member without a lambda
std::ranges::sort(people, {}, &Person::age);Execution policies (C++17, <execution>) let the classic std::* iterator-pair algorithms run in parallel or with SIMD vectorisation. The std::ranges::* algorithms do not accept execution policies as of C++23; fall back to the std::* iterator-pair forms when you need std::execution::par.
std::sort has been guaranteed O(n log n) worst-case since C++11 (implementations use introsort — quicksort with a heapsort fallback). Prior to C++11, only average-case O(n log n) was required.
Sorting
std::ranges::sort(v); // C++20
std::ranges::sort(v, std::greater{}); // descending
std::ranges::sort(v, {}, &S::field); // by member projection — C++20
std::ranges::stable_sort(v); // preserves relative order of equals
// partial_sort: only first n positions are fully sorted — O(n log k)
std::ranges::partial_sort(v, v.begin() + 5);
// nth_element: O(n) average — element at pos as if sorted; others are partitioned
std::ranges::nth_element(v, v.begin() + v.size() / 2); // median pivot
bool ok = std::ranges::is_sorted(v);
auto it = std::ranges::is_sorted_until(v); // iterator to first out-of-order elementSearching
// Linear search — O(n)
auto it = std::ranges::find(v, 42);
auto it2 = std::ranges::find_if(v, [](int n){ return n > 10; });
auto it3 = std::ranges::find_if_not(v, pred);
// Binary search — O(log n), range MUST be sorted
bool found = std::ranges::binary_search(v, 42);
auto lo = std::ranges::lower_bound(v, 42); // first element >= 42
auto hi = std::ranges::upper_bound(v, 42); // first element > 42
auto [lo2, hi2] = std::ranges::equal_range(v, 42); // subrange where value == 42
// Subsequence search
auto r = std::ranges::search(haystack, needle); // first occurrence of needle
auto e = std::ranges::find_end(haystack, needle); // last occurrence
std::ranges::search_n(v, 3, 0); // 3 consecutive zeros
// Min / max
auto mn_it = std::ranges::min_element(v);
auto mx_it = std::ranges::max_element(v);
auto [mn, mx] = std::ranges::minmax(v); // returns min_max_result — C++20
std::ranges::clamp(val, lo_val, hi_val); // std::clamp since C++17Predicates
std::ranges::all_of(v, pred);
std::ranges::any_of(v, pred);
std::ranges::none_of(v, pred);
std::ranges::count(v, val);
std::ranges::count_if(v, pred);
std::ranges::contains(v, val); // C++23 only — use find != end in C++20std::ranges::contains requires C++23. In C++20, write std::ranges::find(v, val) != std::ranges::end(v).
Transforming
// copy
std::ranges::copy(src, std::back_inserter(dst));
std::ranges::copy_if(src, std::back_inserter(dst), pred);
std::ranges::copy_n(src.begin(), 5, dst.begin());
std::ranges::copy_backward(src, dst_end);
// transform (map)
std::ranges::transform(v, dst.begin(), [](int n){ return n * 2; });
std::ranges::transform(a, b, dst.begin(), std::plus{}); // binary form
// generate / fill
std::mt19937 rng{std::random_device{}()};
std::uniform_int_distribution<int> dist(0, 100);
std::ranges::generate(v, [&]{ return dist(rng); });
std::ranges::fill(v, 0);
std::ranges::fill_n(v.begin(), 5, -1);
// replace
std::ranges::replace(v, 0, -1);
std::ranges::replace_if(v, pred, -1);
std::ranges::replace_copy(src, dst.begin(), 0, -1);
// reverse / rotate
std::ranges::reverse(v);
std::ranges::rotate(v, v.begin() + 3); // rotate left by 3 positions
std::ranges::rotate_copy(v, v.begin() + 3, dst.begin());Removing
std::ranges::remove shifts surviving elements to the front and returns a subrange representing the dead tail [new_end, old_end). It does not resize the container — you must call erase separately.
// Correct: use the returned subrange to erase the tail
auto tail = std::ranges::remove(v, 0); // C++20 — returns subrange
v.erase(tail.begin(), tail.end());
// C++20 one-liners — strongly prefer for vector/deque/string/list
std::erase(v, 0); // C++20
std::erase_if(v, [](int n){ return n < 0; }); // C++20
// Deduplicate (sort first — unique only removes consecutive duplicates)
std::ranges::sort(v);
auto dup_tail = std::ranges::unique(v); // C++20 — returns subrange
v.erase(dup_tail.begin(), dup_tail.end());Partitioning
std::ranges::partition(v, pred); // relative order not preserved
std::ranges::stable_partition(v, pred); // preserves relative order — O(n log n)
bool ok = std::ranges::is_partitioned(v, pred);
auto mid = std::ranges::partition_point(v, pred); // O(log n) on partitioned rangeSet Operations (sorted ranges)
All set algorithms require both input ranges to be sorted under the same comparator. Violating this precondition is undefined behaviour.
std::ranges::merge(a, b, out_it);
std::ranges::set_union(a, b, out_it);
std::ranges::set_intersection(a, b, out_it);
std::ranges::set_difference(a, b, out_it);
std::ranges::set_symmetric_difference(a, b, out_it);
std::ranges::inplace_merge(v, mid);
bool subset = std::ranges::includes(a, b); // true if every element of b is in aHeap Operations
std::ranges::make_heap(v); // O(n) — establishes max-heap invariant
std::ranges::push_heap(v); // insert v.back() into heap — O(log n)
std::ranges::pop_heap(v); // moves max to v.back(), re-heapifies — O(log n)
std::ranges::sort_heap(v); // O(n log n) — heap must be valid first
bool h = std::ranges::is_heap(v);Permutations
std::ranges::next_permutation(v); // C++20 — advances to next lexicographic permutation
std::ranges::prev_permutation(v);
std::ranges::shuffle(v, rng); // Fisher-Yates; std::shuffle since C++11, ranges since C++20
std::ranges::sample(src, out, n, rng); // reservoir sample; std::sample since C++17, ranges since C++20
std::ranges::is_permutation(a, b);std::random_shuffle was deprecated in C++14 and removed in C++17. Always use std::shuffle (C++11) or std::ranges::shuffle (C++20) with an explicit URBG.
Parallel Execution (C++17)
Only the classic std::* iterator-pair algorithms accept execution policies. std::ranges::* algorithms have no parallel overloads as of C++23.
#include <execution>
std::sort(std::execution::par, v.begin(), v.end());
std::transform(std::execution::par_unseq,
v.begin(), v.end(), dst.begin(), fn);
// Execution policies (C++17 unless noted):
// seq — sequential; identical to omitting a policy
// par — parallel threads
// par_unseq — parallel + SIMD; callable must not lock or allocate
// unseq — SIMD only, single thread (C++20)par_unseq permits the runtime to interleave SIMD lanes across threads. Any callable passed under this policy must be free of locks, memory allocation, and non-vectorisable control flow.
Best Practices
Prefer std::ranges::* in C++20 codebases. Projections replace single-field lambdas, accepting a range object removes iterator boilerplate, and the result types carry richer information (e.g., in_out_result, min_max_result). Fall back to the std::* iterator-pair forms only when you need parallel execution.
Use std::erase / std::erase_if over the erase-remove idiom (C++20+). The two-step pattern is error-prone and the C++20 free functions are available for vector, deque, string, list, forward_list, and the associative containers.
Exploit projections to avoid temporary transforms.
// Unnecessary allocation:
std::vector<std::string> names;
std::ranges::transform(people, std::back_inserter(names), &Person::name);
std::ranges::sort(names);
// Sort the original by field directly — no allocation:
std::ranges::sort(people, {}, &Person::name);Know the complexity contracts. partial_sort is O(n log k) where k is the sorted prefix length — much cheaper than full sort when k ≪ n. nth_element is O(n) average with introselect implementations guaranteeing O(n) worst-case. stable_sort degrades to O(n log² n) when it cannot obtain extra memory.
Common Pitfalls
Calling binary search algorithms on unsorted ranges. binary_search, lower_bound, upper_bound, equal_range, and all set operations have a sorted-input precondition. They will silently produce wrong results — not a crash or an exception.
Forgetting erase after remove or unique. The algorithm only reorders elements; size() and end() are unchanged until you explicitly erase the tail.
// Bug: v retains its original size; the tail holds garbage
std::ranges::remove(v, 0);
// Correct
v.erase(std::ranges::remove(v, 0).begin(), v.end());
// Or prefer the C++20 one-liner:
std::erase(v, 0);Using std::ranges::contains in a C++20 project. It is a C++23 addition. Compilers targeting C++20 will reject it; use std::ranges::find(v, val) != std::ranges::end(v).
Calling std::sort on std::list. std::sort requires random-access iterators; std::list provides only bidirectional iterators. The code will not compile. Use list.sort(), which is a member function.
Using par_unseq with stateful callables. Any mutex, allocation, or non-vectorisable branch inside the callable can deadlock or corrupt state. Under par_unseq the implementation may execute multiple loop iterations in a single thread via SIMD before switching threads.
Ranges algorithms vs classic algorithms
The std::ranges::* overloads are not just syntactic sugar — they carry tighter constraints and richer return types. Every ranges algorithm is constrained via C++20 concepts, so constraint violations produce shorter, more actionable error messages than the wall-of-template-failures you get from classic algorithms.
// C++98/11/14/17 — iterator-pair form
std::sort(v.begin(), v.end());
auto it = std::find(v.begin(), v.end(), 42);
// C++20 — ranges form; accepts any range, returns richer types
std::ranges::sort(v);
auto it2 = std::ranges::find(v, 42); // same iterator semantics
// Ranges algorithms also accept explicit iterator pairs if you need a subrange
std::ranges::sort(v.begin() + 2, v.end());
// The ranges form enforces concepts at the call site:
// passing a non-copyable type to find_if gives a readable error, not 50 lines of SFINAEClassic std::* algorithms remain the only choice for parallel execution (std::execution::par), since std::ranges::* algorithms have no parallel overloads as of C++23.
Projections in ranges algorithms
A projection is a callable that transforms each element before the algorithm uses it for comparison or predicate evaluation. Every ranges algorithm that accepts a comparator also accepts an optional projection, making single-field sorts and searches expressible without a lambda.
// C++20
struct Employee { std::string name; int salary; int dept; };
std::vector<Employee> team = /* ... */;
// Sort by salary descending — no lambda needed
std::ranges::sort(team, std::greater{}, &Employee::salary); // C++20
// Find first employee in dept 3
auto it = std::ranges::find(team, 3, &Employee::dept); // C++20
// Count employees earning over 80 000
int n = std::ranges::count_if(team,
[](int s){ return s > 80'000; },
&Employee::salary); // C++20
// Projections compose with any callable — not just member pointers
auto it2 = std::ranges::max_element(team, {},
[](const Employee& e){ return e.salary + e.dept * 100; }); // C++20The projection is applied to both sides of a comparison automatically. You never write the two-argument comparator [](auto& a, auto& b){ return a.salary < b.salary; } when a projection covers the case.
Algorithm complexity guarantees
The standard mandates worst-case complexity for the most critical algorithms; knowing these numbers prevents accidentally quadratic code. The table below covers the most frequently misunderstood guarantees.
// std::sort — O(n log n) worst-case since C++11 (introsort)
std::ranges::sort(v); // C++20
// std::stable_sort — O(n log n) when extra memory available;
// O(n log² n) when it cannot allocate
std::ranges::stable_sort(v); // C++20
// std::partial_sort — O(n log k); k = distance(first, middle)
// cheaper than sort when you only need the top-k elements
std::ranges::partial_sort(v, v.begin() + 10); // C++20
// std::nth_element — O(n) average (introselect = O(n) worst in practice)
std::ranges::nth_element(v, v.begin() + v.size()/2); // C++20
// std::inplace_merge — O(n log n); O(n) if extra memory available
std::ranges::inplace_merge(v, v.begin() + mid); // C++20
// std::make_heap — O(n); not O(n log n) despite intuition
std::ranges::make_heap(v); // C++20
// std::partition — O(n); std::stable_partition — O(n log n)
std::ranges::partition(v, pred); // C++20
std::ranges::stable_partition(v, pred); // C++20std::lower_bound / upper_bound on a random-access range are O(log n), but on bidirectional or forward iterators they perform O(n) iterator increments even though they perform O(log n) comparisons.
Composing algorithms with views
std::ranges::views (a.k.a. std::views) produce lazy, zero-copy range adaptors that can be fed directly into any ranges algorithm. The composition replaces multi-pass loops with a single declarative pipeline.
#include <ranges> // C++20
std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8};
// Sum of squares of even numbers — no temporaries
auto even_squares = v
| std::views::filter([](int n){ return n % 2 == 0; })
| std::views::transform([](int n){ return n * n; }); // C++20
int total = std::ranges::fold_left(even_squares, 0, std::plus{}); // C++23
// C++20 equivalent:
// int total = std::accumulate(even_squares.begin(), even_squares.end(), 0);
// Sort only the first 10 elements via a materialized subrange
auto front10 = v | std::views::take(10); // C++20
// Note: views::take is lazy; materialize if algorithm needs random-access
std::vector<int> buf(front10.begin(), front10.end());
std::ranges::sort(buf);
// zip two ranges for binary transform (C++23)
auto pairs = std::views::zip(v, v | std::views::reverse); // C++23
std::ranges::for_each(pairs, [](auto p){
auto [a, b] = p;
std::println("{} + {} = {}", a, b, a + b); // C++23
});Views are non-owning. Passing a view to an algorithm that needs to iterate the range more than once (e.g., std::ranges::sort) requires the view to be at least a forward range. Views derived from single-pass input ranges (like std::views::istream) cannot be sorted.
Algorithm return types
Ranges algorithms return structured result types instead of single iterators, making it possible to chain algorithms without losing position information. All result structs live in std::ranges.
// C++20 — copy returns in_out_result{in, out}
auto [in, out] = std::ranges::copy(src, dst.begin());
// in — iterator past the last element read from src
// out — iterator past the last element written to dst
// C++20 — transform (unary) returns in_out_result
auto res = std::ranges::transform(v, dst.begin(), fn);
// res.in — past src end; res.out — past dst write position
// C++20 — transform (binary) returns in_in_out_result
auto res2 = std::ranges::transform(a, b, dst.begin(), std::plus{});
// C++20 — minmax returns min_max_result
auto [lo, hi] = std::ranges::minmax(v);
// C++20 — partition returns in_out_result (begin of second partition)
auto [true_end, false_begin] = std::ranges::partition(v, pred);
// C++20 — remove / unique return borrowed_subrange (the dead tail)
auto tail = std::ranges::remove(v, 0);
v.erase(tail.begin(), tail.end());
// C++20 — mismatch returns in_in_result
auto [p, q] = std::ranges::mismatch(a, b);
// p — iterator into a at first mismatch; q — same for bUsing structured bindings with these result types is idiomatic C++20. Ignoring the return value of remove or unique is one of the most common algorithm bugs (see Common Pitfalls).
Common algorithm patterns
A handful of patterns appear in nearly every real codebase; knowing their canonical form avoids reinventing them. The patterns below combine idioms from the preceding sections.
// --- Pattern 1: deduplicate a vector ---------------------------------
// C++20 preferred:
std::ranges::sort(v);
std::erase(v, /* NOT applicable for unique */); // unique needs two steps
auto [new_end, _] = std::ranges::unique(v); // C++20
v.erase(new_end, v.end());
// One-shot helper (wrap in a function):
// ranges::sort + ranges::unique + erase
// --- Pattern 2: partition then process each half ---------------------
// C++20
auto mid = std::ranges::stable_partition(v, pred).begin();
std::ranges::for_each(std::ranges::subrange(v.begin(), mid), process_true);
std::ranges::for_each(std::ranges::subrange(mid, v.end()), process_false);
// --- Pattern 3: top-k elements without full sort --------------------
// O(n log k) — far cheaper than sort when k << n
std::vector<int> data = /* large dataset */;
std::ranges::partial_sort(data, data.begin() + 5); // C++20
// data[0..4] are the 5 smallest; rest is unspecified order
// --- Pattern 4: sliding window maximum with nth_element --------------
// Get median of each window of size W
std::vector<int> window(W);
for (std::size_t i = 0; i + W <= data.size(); ++i) {
std::ranges::copy(data | std::views::drop(i) | std::views::take(W),
window.begin()); // C++20
std::ranges::nth_element(window, window.begin() + W/2); // O(W) average
medians.push_back(window[W/2]);
}
// --- Pattern 5: merge multiple sorted ranges -------------------------
// C++17
std::vector<int> merged;
merged.reserve(a.size() + b.size());
std::ranges::merge(a, b, std::back_inserter(merged)); // C++20
// For k ranges, use a min-heap or repeated inplace_merge
// --- Pattern 6: erase elements matching a predicate -----------------
// C++20 — preferred over erase-remove idiom
std::erase_if(v, [](int n){ return n % 2 == 0; }); // C++20These patterns cover roughly 80% of day-to-day algorithm usage. For numeric patterns (std::reduce, std::inclusive_scan, std::transform_reduce) see the <numeric> reference page.
See Also
std::rangesadaptors — lazy, composable views over ranges<numeric>—std::accumulate,std::reduce(C++17 parallel),std::iota,std::partial_sum<execution>— execution policy types and requirements- Iterators — iterator categories, concepts, and the requirements each algorithm imposes