STL Algorithms Quick Reference

#include <algorithm>

// Sort in-place — O(n log n)
std::sort(v.begin(), v.end());                        // ascending
std::sort(v.begin(), v.end(), std::greater<int>{});   // descending
std::sort(v.begin(), v.end(), [](const T& a, const T& b) { return a.key < b.key; });

// Ranges versions (C++20)
std::ranges::sort(v);
std::ranges::sort(v, {}, &Person::age);   // sort by member (projection)

// Stable sort — preserves relative order of equal elements
std::stable_sort(v.begin(), v.end());

// Partial sort — first n elements sorted, rest unordered
std::partial_sort(v.begin(), v.begin() + n, v.end());

// nth element — element that would be at position n if sorted
std::nth_element(v.begin(), v.begin() + n, v.end());
// v[n] is correct; v[0..n-1] ≤ v[n] ≤ v[n+1..end]

// Check if sorted
std::is_sorted(v.begin(), v.end());
std::ranges::is_sorted(v);

// Linear search — O(n)
auto it = std::find(v.begin(), v.end(), value);
auto it2 = std::find_if(v.begin(), v.end(), predicate);
auto it3 = std::find_if_not(v.begin(), v.end(), predicate);

// Binary search — O(log n), requires sorted range
bool found = std::binary_search(v.begin(), v.end(), value);
auto it4 = std::lower_bound(v.begin(), v.end(), value);  // first ≥ value
auto it5 = std::upper_bound(v.begin(), v.end(), value);  // first > value
auto [lo, hi] = std::equal_range(v.begin(), v.end(), value);  // range of equals

// Min/max
auto it6 = std::min_element(v.begin(), v.end());
auto it7 = std::max_element(v.begin(), v.end());
auto [min_it, max_it] = std::minmax_element(v.begin(), v.end());

// Ranges
auto it8 = std::ranges::find(v, value);
auto it9 = std::ranges::find_if(v, pred);
auto min = std::ranges::min_element(v);

// Count
long n = std::count(v.begin(), v.end(), value);
long n2 = std::count_if(v.begin(), v.end(), predicate);

// Test all/any/none
bool all  = std::all_of(v.begin(), v.end(), predicate);
bool any  = std::any_of(v.begin(), v.end(), predicate);
bool none = std::none_of(v.begin(), v.end(), predicate);

// Ranges
auto n3 = std::ranges::count(v, value);
bool all2 = std::ranges::all_of(v, predicate);

#include <algorithm>

// transform — apply function to each element
std::transform(in.begin(), in.end(), out.begin(), func);
std::transform(a.begin(), a.end(), b.begin(), out.begin(), binary_func);

// for_each — apply function for side effects
std::for_each(v.begin(), v.end(), [](int& x) { x *= 2; });

// replace
std::replace(v.begin(), v.end(), old_val, new_val);
std::replace_if(v.begin(), v.end(), predicate, new_val);
std::replace_copy(in.begin(), in.end(), out.begin(), old_val, new_val);

// fill and generate
std::fill(v.begin(), v.end(), value);
std::fill_n(v.begin(), n, value);
std::generate(v.begin(), v.end(), generator_fn);   // calls fn() for each
std::generate_n(v.begin(), n, generator_fn);

// copy
std::copy(in.begin(), in.end(), out.begin());
std::copy_if(in.begin(), in.end(), out.begin(), predicate);
std::copy_n(in.begin(), n, out.begin());
std::copy_backward(in.begin(), in.end(), out.end());  // copy in reverse order

// move
std::move(in.begin(), in.end(), out.begin());

// remove (erase-remove idiom) — moves kept elements to front
auto it = std::remove(v.begin(), v.end(), value);  // doesn't resize!
v.erase(it, v.end());  // actual erase

// remove_if
auto it2 = std::remove_if(v.begin(), v.end(), predicate);
v.erase(it2, v.end());

// C++20 — std::erase / std::erase_if (no idiom needed)
std::erase(v, value);
std::erase_if(v, predicate);  // works for vector, map, set, etc.

// unique — remove consecutive duplicates (sort first for all-unique)
std::sort(v.begin(), v.end());
auto it3 = std::unique(v.begin(), v.end());
v.erase(it3, v.end());

// partition — elements satisfying predicate come first
auto it = std::partition(v.begin(), v.end(), predicate);
// [begin, it) satisfy predicate; [it, end) do not

// stable_partition — preserves relative order
std::stable_partition(v.begin(), v.end(), predicate);

// is_partitioned
bool ok = std::is_partitioned(v.begin(), v.end(), predicate);

// partition_copy — copy to two output ranges
std::partition_copy(in.begin(), in.end(),
    yes_out.begin(), no_out.begin(), predicate);

// All require sorted input ranges

// merge — merge two sorted ranges
std::merge(a.begin(), a.end(), b.begin(), b.end(), out.begin());
std::inplace_merge(v.begin(), v.begin() + n, v.end());  // merge within vector

// set operations
std::set_union(a.begin(), a.end(), b.begin(), b.end(), out.begin());
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), out.begin());
std::set_difference(a.begin(), a.end(), b.begin(), b.end(), out.begin());
std::set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(), out.begin());

// Membership
std::includes(big.begin(), big.end(), small.begin(), small.end());

// Build a max-heap
std::make_heap(v.begin(), v.end());
v.front();  // max element

// Push/pop heap (maintains heap property)
v.push_back(new_val);
std::push_heap(v.begin(), v.end());

std::pop_heap(v.begin(), v.end());  // moves max to back
v.pop_back();

// Sort using heap (heap sort)
std::sort_heap(v.begin(), v.end());  // destroys heap property

#include <numeric>

// Accumulate (fold)
int sum = std::accumulate(v.begin(), v.end(), 0);
int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>{});

// reduce (C++17) — like accumulate but parallelizable
int sum2 = std::reduce(v.begin(), v.end());
int sum3 = std::reduce(std::execution::par, v.begin(), v.end());

// transform_reduce (C++17) — map then reduce
double dot = std::transform_reduce(a.begin(), a.end(), b.begin(), 0.0);
// a[0]*b[0] + a[1]*b[1] + ...

// inclusive/exclusive scan (prefix sum)
std::vector<int> out(v.size());
std::inclusive_scan(v.begin(), v.end(), out.begin());  // out[i] = sum[0..i]
std::exclusive_scan(v.begin(), v.end(), out.begin(), 0); // out[i] = sum[0..i-1]

// adjacent_difference — difference between consecutive elements
std::adjacent_difference(v.begin(), v.end(), out.begin());
// out[0]=v[0], out[i]=v[i]-v[i-1]

// iota — fill with incrementing values
std::iota(v.begin(), v.end(), 0);  // 0, 1, 2, 3, ...
std::iota(v.begin(), v.end(), 10); // 10, 11, 12, 13, ...

// inner_product
int dot2 = std::inner_product(a.begin(), a.end(), b.begin(), 0);

// C++23 fold_left / fold_right
int sum4 = std::ranges::fold_left(v, 0, std::plus{});
int sum5 = std::ranges::fold_right(v, 0, std::plus{});

// next/prev permutation (modifies in place, returns false on wrap)
std::sort(v.begin(), v.end());
do {
    process(v);
} while (std::next_permutation(v.begin(), v.end()));
// iterates through all permutations

// Shuffle
std::mt19937 rng(std::random_device{}());
std::shuffle(v.begin(), v.end(), rng);

// Rotate
std::rotate(v.begin(), v.begin() + n, v.end());  // v[n] becomes v[0]

// Reverse
std::reverse(v.begin(), v.end());
std::reverse_copy(in.begin(), in.end(), out.begin());

#include <execution>

// seq — sequential (default behavior)
std::sort(std::execution::seq, v.begin(), v.end());

// par — parallel (multi-core)
std::sort(std::execution::par, v.begin(), v.end());

// par_unseq — parallel + SIMD vectorized
std::transform(std::execution::par_unseq,
    v.begin(), v.end(), v.begin(), [](int x) { return x * 2; });

// Available for: sort, for_each, transform, reduce, find, count, copy, ...