UUsseeffuull AAllggoorriitthhmmss

Sorting · Searching · Transform · Numeric · Reordering · C++20 Ranges

C++17 · Advanced Reference

The <algorithm> Library

Iterator-based design

Every standard algorithm operates on a range defined by two iterators:[first, last) — the first iterator points to the first element, the last points one past the end. This uniform interface means every algorithm works on vectors, arrays, strings, lists, and any custom container.

Algorithm categories

1.Sorting — sort, stable_sort, partial_sort, nth_element
2.Searching — find, find_if, binary_search, lower/upper_bound
3.Transforming — transform, for_each, replace, fill, generate
4.Reordering — reverse, rotate, shuffle, partition, unique
5.Numeric — accumulate, iota, partial_sum, inner_product
6.Querying — count, count_if, any_of, all_of, none_of

Key rules

1.Algorithms never change container size — use erase-remove idiom to actually remove elements.
2.Most algorithms require a valid range — first <= last. Violating this is UB.
3.Sorted-range algorithms (binary_search, lower_bound) require a sorted input.
4.Prefer standard algorithms over raw loops — they express intent, and the compiler can vectorize them more reliably.

C++20 ranges algorithms work directly on containers: std::ranges::sort(v) instead of std::sort(v.begin(), v.end()).

Sorting

#include <algorithm>
std::vector<int> v = {5, 2, 8, 1, 9, 3};

// ── Sort ──────────────────────────────────────────────────────
std::sort(v.begin(), v.end());                     // ascending
std::sort(v.begin(), v.end(), std::greater<int>()); // descending
std::sort(v.begin(), v.end(), [](int a, int b){ return a > b; });

// Sort objects by a field
struct Person { std::string name; int age; };
std::sort(people.begin(), people.end(),
  [](const Person& a, const Person& b){ return a.age < b.age; });

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

// ── Partial sort — only sort first k elements ─────────────────
std::partial_sort(v.begin(), v.begin()+3, v.end()); // smallest 3 sorted
// Useful when you only need the top-N results

// ── nth_element — O(n) partition, not full sort ───────────────
std::nth_element(v.begin(), v.begin()+2, v.end());
// v[2] is now the element that WOULD be at index 2 if sorted
// elements before v[2] are ≤ v[2], elements after are ≥ v[2]

// ── Check if sorted ───────────────────────────────────────────
std::is_sorted(v.begin(), v.end());   // true / false

sort	Introsort (quicksort + heapsort + insertion). O(n log n) worst case. Not stable.
stable_sort	Merge sort. O(n log n). Preserves relative order of equal elements. Use when order matters.
partial_sort	Sort only the first k elements. O(n log k). Use for top-N queries.
nth_element	O(n) average. Places the k-th element correctly; others are partitioned but not sorted. Use for median.

Use a lambda comparator for complex sorts. The comparator must be a strict weak ordering: irreflexive, asymmetric, transitive. Returning true for equal elements is undefined behavior.

Searching

std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};  // must be sorted for binary search

// ── Linear search (unsorted) — O(n) ──────────────────────────
auto it = std::find(v.begin(), v.end(), 5);
if (it != v.end()) std::cout << "found at index " << (it - v.begin());

// Find by predicate
auto it2 = std::find_if(v.begin(), v.end(), [](int x){ return x > 5; });

// ── Binary search (sorted) — O(log n) ────────────────────────
bool found = std::binary_search(v.begin(), v.end(), 5);  // true/false only

// lower_bound: first element >= value
auto lo = std::lower_bound(v.begin(), v.end(), 5);  // points to 5

// upper_bound: first element > value
auto hi = std::upper_bound(v.begin(), v.end(), 5);  // points to 6

// equal_range: [lower_bound, upper_bound) — all elements == value
auto [first, last] = std::equal_range(v.begin(), v.end(), 5);
std::distance(first, last);   // count of matching elements

// ── Min / max ─────────────────────────────────────────────────
auto [minIt, maxIt] = std::minmax_element(v.begin(), v.end());
std::min({3, 1, 4, 1, 5});   // initializer_list overload — 1
std::clamp(x, lo, hi);        // clamp x to [lo, hi]

find / find_if	Linear O(n). find_if takes a predicate. Both return end() if not found.
binary_search	O(log n) on sorted range. Returns bool only — use lower_bound to get the position.
lower_bound	First element >= value. Use to find insertion point in a sorted range.
equal_range	Returns [lower, upper) pair — all elements equal to value. std::distance gives the count.
std::clamp	Returns lo if x < lo, hi if x > hi, else x. Replaces std::max(lo, std::min(x, hi)).

Transform · Fill · Generate · Replace

std::vector<int> v = {1, 2, 3, 4, 5};
std::vector<int> out(v.size());

// ── transform — apply function to each element ───────────────
std::transform(v.begin(), v.end(), out.begin(),
  [](int x){ return x * x; });           // {1, 4, 9, 16, 25}

// Binary transform — combine two ranges
std::vector<int> a = {1,2,3}, b = {10,20,30};
std::transform(a.begin(), a.end(), b.begin(), out.begin(),
  [](int x, int y){ return x + y; });    // {11, 22, 33}

// ── for_each — side effects on each element ──────────────────
std::for_each(v.begin(), v.end(), [](int& x){ x *= 2; });  // modifies in-place

// ── fill / generate ──────────────────────────────────────────
std::fill(v.begin(), v.end(), 0);          // all zeros
std::fill_n(v.begin(), 3, 99);            // first 3 = 99

int n = 0;
std::generate(v.begin(), v.end(), [&n]{ return n++; }); // 0,1,2,3,4

// ── replace ──────────────────────────────────────────────────
std::replace(v.begin(), v.end(), 0, -1);   // replace all 0s with -1
std::replace_if(v.begin(), v.end(),
  [](int x){ return x < 0; }, 0);          // replace negatives with 0

transform	Maps each element through a function into an output range. Output range must be pre-sized.
for_each	Like transform but for side effects — use a reference parameter to modify in-place.
generate	Fills a range by calling a generator function repeatedly. Great for sequences and test data.
replace_if	Replaces elements matching a predicate. Simpler than transform when just replacing values.

Reordering

std::vector<int> v = {1, 2, 3, 4, 5, 6};

// ── reverse ──────────────────────────────────────────────────
std::reverse(v.begin(), v.end());          // {6,5,4,3,2,1}

// ── rotate — shift elements left by n positions ──────────────
std::rotate(v.begin(), v.begin()+2, v.end());  // {3,4,5,6,1,2}

// ── shuffle — randomize order ────────────────────────────────
#include <random>
std::mt19937 rng(std::random_device{}());
std::shuffle(v.begin(), v.end(), rng);

// ── partition — split by predicate ───────────────────────────
auto mid = std::partition(v.begin(), v.end(),
  [](int x){ return x % 2 == 0; });   // evens first, then odds
// mid points to first odd element

// ── unique — remove consecutive duplicates ────────────────────
std::sort(v.begin(), v.end());
auto newEnd = std::unique(v.begin(), v.end());
v.erase(newEnd, v.end());   // actually remove them

// ── copy / move ───────────────────────────────────────────────
std::copy(v.begin(), v.end(), out.begin());          // copy range
std::copy_if(v.begin(), v.end(), out.begin(),
  [](int x){ return x > 3; });                       // filtered copy
std::move(v.begin(), v.end(), out.begin());          // move range

rotate	Rotates elements left so that v.begin()+n becomes the new first. Returns the new position of the old first element.
shuffle	Uniformly random permutation. Always pass a seeded std::mt19937 — rand() is not uniform.
partition	Reorders so matching elements come first. Returns iterator to first non-matching. Not stable.
unique	Removes consecutive duplicates. Must sort first to remove all. Returns new logical end — erase to shrink.

Numeric Algorithms

#include <numeric>
std::vector<int> v = {1, 2, 3, 4, 5};

// ── accumulate — fold / reduce ───────────────────────────────
int sum  = std::accumulate(v.begin(), v.end(), 0);         // 15
int prod = std::accumulate(v.begin(), v.end(), 1,
             std::multiplies<int>());                       // 120
std::string joined = std::accumulate(words.begin(), words.end(),
  std::string{}, [](auto a, const auto& b){ return a + " " + b; });

// ── iota — fill with sequential values ───────────────────────
std::vector<int> idx(10);
std::iota(idx.begin(), idx.end(), 0);   // {0,1,2,...,9}

// ── inner_product — dot product ──────────────────────────────
int dot = std::inner_product(a.begin(), a.end(), b.begin(), 0);

// ── partial_sum — running total ──────────────────────────────
std::partial_sum(v.begin(), v.end(), out.begin());  // {1,3,6,10,15}

// ── adjacent_difference — consecutive differences ────────────
std::adjacent_difference(v.begin(), v.end(), out.begin()); // {1,1,1,1,1}

// ── C++17: reduce (parallel-friendly accumulate) ─────────────
#include <execution>
int s = std::reduce(std::execution::par, v.begin(), v.end());

accumulate	Sequential fold — applies binary op left-to-right. Start value is required and sets the result type.
iota	Fills range with val, val+1, val+2, ... Essential for generating index sequences.
partial_sum	Prefix sum — element i of output is sum of input[0..i]. Use for cumulative distributions.
reduce (C++17)	Like accumulate but order of operations is unspecified — enables parallel execution with execution policies.

C++20 Ranges & Views

// C++20: Ranges — algorithm + lazy view composition
#include <ranges>
#include <algorithm>

std::vector<int> v = {1,2,3,4,5,6,7,8,9,10};

// ── Range algorithms — no begin()/end() needed ────────────────
std::ranges::sort(v);
std::ranges::reverse(v);
auto it = std::ranges::find(v, 5);

// ── Views — lazy, composable, zero-copy ──────────────────────
namespace rv = std::views;

// Filter + transform pipeline (nothing computed until iterated)
auto even_squares = v
  | rv::filter([](int x){ return x % 2 == 0; })
  | rv::transform([](int x){ return x * x; });

for (int x : even_squares) std::cout << x << " ";  // 4 16 36 64 100

// Other useful views
v | rv::take(3)               // first 3 elements
v | rv::drop(2)               // skip first 2
v | rv::reverse               // reversed (lazy)
rv::iota(1, 11)               // {1,2,...,10} — no vector needed
rv::iota(0) | rv::take(5)     // infinite range, take first 5

ranges::sort(v)	No begin/end needed — takes the container directly. Cleaner call sites.
views::filter	Lazy — only evaluates elements when iterated. No intermediate container.
views::transform	Lazy map. Compose with \| to build pipelines without allocating.
views::iota	Generates an infinite (or finite) sequence. Combine with take to limit.
pipe operator \|	Composes views left-to-right. Each stage is lazy — the entire pipeline runs in one pass.

Ranges views are zero-cost abstractions. A filter | transform pipeline iterates the data exactly once and allocates no intermediate containers — equivalent to a hand-written loop with an if-statement inside.