Neel Mishra
← All Posts
C++ STL Series · Part 4 of 5

Algorithms — Beyond std::sort

March 2026 · 13 min read

The Algorithm Philosophy

The <algorithm> header contains ~100 functions that operate on iterator ranges. They don't know about containers — they only speak iterators. This is the payoff of the iterator abstraction.

The Sorting Family

▶ std::sort Visualization

Watch elements get sorted step by step.

std::sort

Introsort (quicksort + heapsort fallback). Average O(n log n), requires Random Access iterators.

std::vector<int> v = {5, 2, 8, 1, 9};
std::sort(v.begin(), v.end());  // ascending

// With custom comparator — descending
std::sort(v.begin(), v.end(), std::greater<int>{});

std::stable_sort

Preserves relative order of equal elements. Uses merge sort internally — may allocate extra memory.

std::partial_sort

Sort only the first K elements — O(n log k) instead of O(n log n):

std::partial_sort(v.begin(), v.begin() + 3, v.end());
// First 3 elements are the smallest, in sorted order

std::nth_element

Rearranges so that element at the nth position is what would be there in a sorted sequence — O(n) average:

std::nth_element(v.begin(), v.begin() + 2, v.end());
// v[2] is now the median (for a 5-element vector)

Searching

All require the range to be sorted:

std::vector<int> v = {1, 3, 5, 7, 9, 11};

bool found = std::binary_search(v.begin(), v.end(), 7);  // true

auto lo = std::lower_bound(v.begin(), v.end(), 5);  // points to 5
auto hi = std::upper_bound(v.begin(), v.end(), 5);  // points to 7

auto [a, b] = std::equal_range(v.begin(), v.end(), 5);
// a points to 5, b points to 7

std::find / std::find_if

auto it = std::find(v.begin(), v.end(), 7);

auto it2 = std::find_if(v.begin(), v.end(),
    [](int x) { return x > 6; });  // first element > 6

Partitioning

std::partition rearranges elements so those satisfying a predicate come first:

▶ std::partition Animation

Partition: even numbers to the left, odd to the right.

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

auto pivot = std::partition(v.begin(), v.end(),
    [](int x) { return x % 2 == 0; });

// Even numbers are before pivot, odd after
// pivot points to the first odd element
Use case: Partitioning is the core of quicksort and is useful for splitting datasets into "good" and "bad" buckets in one pass.

Heap Operations

STL heaps are max-heaps built on a vector (or any random-access container):

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

std::make_heap(v.begin(), v.end());    // O(n)
// v.front() is now the max: 9

v.push_back(10);
std::push_heap(v.begin(), v.end());    // O(log n)

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

std::sort_heap(v.begin(), v.end());    // turns heap into sorted array

Numeric Algorithms

From <numeric>:

#include <numeric>

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

int sum = std::accumulate(v.begin(), v.end(), 0);  // 15

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

// Prefix sums
std::vector<int> prefix(5);
std::partial_sum(v.begin(), v.end(), prefix.begin());
// prefix = {1, 3, 6, 10, 15}

// Inner product
std::vector<int> w = {2, 3, 4, 5, 6};
int dot = std::inner_product(v.begin(), v.end(), w.begin(), 0);
// 2 + 6 + 12 + 20 + 30 = 70

std::transform

Apply a function to every element and write results to an output range:

std::vector<int> src = {1, 2, 3, 4};
std::vector<int> dst(src.size());

std::transform(src.begin(), src.end(), dst.begin(),
    [](int x) { return x * x; });
// dst = {1, 4, 9, 16}

The Remove-Erase Idiom

std::remove doesn't actually remove — it moves unwanted elements to the end and returns a new logical end. You must erase the tail:

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

auto new_end = std::remove(v.begin(), v.end(), 2);
v.erase(new_end, v.end());
// v = {1, 3, 5}

// C++20 one-liner:
std::erase(v, 2);

Summary