C++ Useful Algorithms and Classes

  • Description: A note on std::initializer_list and the most useful <algorithm> and <numeric> functions
  • My Notion Note ID: K2A-B1-15
  • Created: 2018-10-03
  • Updated: 2026-02-28
  • License: Reuse is very welcome. Please credit Yu Zhang and link back to the original on yuzhang.io

Table of Contents

For C++20 Ranges, views, projections, and std::span, see the dedicated note: C++ Ranges, Views, and Span.

1. std::initializer_list

std::initializer_list<T> (C++11, <initializer_list>) allows functions and constructors to accept brace-enclosed lists of values. It enables uniform initialization syntax.

#include <initializer_list>
#include <iostream>
#include <vector>

class DataSet {
    std::vector<int> data_;
public:
    DataSet(std::initializer_list<int> init) : data_(init) {}

    DataSet& operator=(std::initializer_list<int> init) {
        data_.assign(init.begin(), init.end());
        return *this;
    }

    void print() const {
        for (int x : data_) std::cout << x << " ";
        std::cout << std::endl;
    }
};

int main() {
    DataSet ds = {1, 2, 3, 4, 5};
    ds.print();  // 1 2 3 4 5

    ds = {10, 20, 30};
    ds.print();  // 10 20 30

    return 0;
}

Key properties of initializer_list:

  1. Elements are always const (you cannot modify them through the list).
  2. Copying an initializer_list does not copy the underlying elements (it is lightweight).
  3. The underlying array has automatic storage duration (it is a temporary).

2. Sorting and Partitioning

The <algorithm> header provides the standard sorting suite. std::sort, std::stable_sort, std::partial_sort, and std::nth_element require random-access iterators. std::partition requires only forward iterators, and std::stable_partition requires bidirectional iterators.

  1. std::sort(first, last, [cmp]) — Introsort; O(n log n) average and worst case. Not stable.
  2. std::stable_sort(first, last, [cmp]) — Preserves relative order of equal elements. O(n log² n) worst case.
  3. std::partial_sort(first, middle, last, [cmp]) — Sort just enough so that [first, middle) holds the smallest elements in order. Useful for top-k.
  4. std::nth_element(first, nth, last, [cmp]) — Partial sort that puts the kth element in its sorted position; everything before is ≤ and everything after is ≥. O(n) average. The fastest way to find a kth-order statistic.
  5. std::partition(first, last, pred) — Reorder so elements satisfying pred come first. Returns the partition point. Not stable.
  6. std::stable_partition(first, last, pred) — Stable variant.
#include <algorithm>
#include <vector>

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

std::sort(v.begin(), v.end());                                  // 1 2 3 5 7 8 9
std::sort(v.begin(), v.end(), std::greater<int>());             // 9 8 7 5 3 2 1

// Top-3 smallest, in order, in [begin, begin+3)
std::partial_sort(v.begin(), v.begin() + 3, v.end());

// Find median in O(n) average
auto mid = v.begin() + v.size() / 2;
std::nth_element(v.begin(), mid, v.end());

3. Searching

For an unsorted range, use linear scans. For a sorted range, use binary searches.

  1. std::find(first, last, value) — Linear search; returns iterator to first match or last.
  2. std::find_if(first, last, pred) — Linear search by predicate.
  3. std::binary_search(first, last, value) — bool-only; returns true if value is present.
  4. std::lower_bound(first, last, value) — First position where value could be inserted without breaking order (i.e. first >= value).
  5. std::upper_bound(first, last, value) — First position strictly greater than value.
  6. std::equal_range(first, last, value) — Pair of (lower_bound, upper_bound).
#include <algorithm>
#include <vector>

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

auto it1 = std::lower_bound(v.begin(), v.end(), 4);  // points to first 4
auto it2 = std::upper_bound(v.begin(), v.end(), 4);  // points to 5
size_t count_of_4 = it2 - it1;                       // 3

4. Non-Modifying Algorithms

These read but do not write the range.

  1. std::count(first, last, value), std::count_if(first, last, pred) — Count occurrences.
  2. std::all_of(first, last, pred), std::any_of(first, last, pred), std::none_of(first, last, pred) — Predicate quantifiers.
  3. std::for_each(first, last, fn) — Apply a function to each element. (In modern C++, prefer a range-based for loop.)
  4. std::min_element(first, last, [cmp]), std::max_element(first, last, [cmp]), std::minmax_element(first, last, [cmp]) — Extrema in O(n).
  5. std::equal(first1, last1, first2) — Check element-wise equality of two ranges.
  6. std::mismatch(first1, last1, first2) — Find first position where two ranges differ.

5. Modifying Algorithms

These write into a destination range.

  1. std::copy(first, last, d_first), std::copy_if(first, last, d_first, pred) — Copy with optional filter.
  2. std::move(first, last, d_first) — Move (not copy) elements; leaves source elements in valid-but-unspecified state. Note this is the algorithm, not std::move the cast.
  3. std::transform(first, last, d_first, fn) — Apply fn and write the result; can take two input ranges and a binary fn.
  4. std::fill(first, last, value), std::generate(first, last, fn) — Fill with a constant or generator.
  5. std::replace(first, last, old, new), std::replace_if(first, last, pred, new) — In-place replace.
  6. std::remove(first, last, value), std::remove_if(first, last, pred) — Erase-remove idiom: these functions return a new logical end; you must follow up with container.erase(...) to actually shrink the container. (C++20 introduces std::erase and std::erase_if for containers, which combine the two steps.)
  7. std::reverse(first, last), std::rotate(first, middle, last) — Reorder in place.
  8. std::unique(first, last) — Removes consecutive duplicates; combine with std::sort first if you need global uniqueness. Same erase-remove pattern as remove.
// Erase-remove idiom (pre-C++20)
v.erase(std::remove_if(v.begin(), v.end(),
                       [](int x) { return x % 2 == 0; }),
        v.end());

// C++20 equivalent
std::erase_if(v, [](int x) { return x % 2 == 0; });

6. Numeric Algorithms

The <numeric> header provides reductions and prefix sums.

  1. std::accumulate(first, last, init, [op]) — Sequential reduction. Default op is +. For floats, beware that order matters.
  2. std::reduce(first, last, init, [op]) — Like accumulate but unsequenced (parallelizable). Requires op to be associative and commutative.
  3. std::transform_reduce(first, last, init, reduce_op, transform_op) — Map-reduce in one pass.
  4. std::inner_product(first1, last1, first2, init) — Dot product.
  5. std::partial_sum(first, last, d_first) — Prefix sums.
  6. std::adjacent_difference(first, last, d_first) — Differences between adjacent elements.
  7. std::iota(first, last, value) — Fill with value, value+1, value+2, ....
#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

std::vector<int> ids(10);
std::iota(ids.begin(), ids.end(), 0);  // 0, 1, 2, ..., 9

7. Set and Heap Operations

  1. Set operations (require sorted input ranges, output is also sorted): std::set_union, std::set_intersection, std::set_difference, std::set_symmetric_difference, std::includes, std::merge.
  2. Heap operations (operate on a RandomAccessRange representing a max-heap): std::make_heap, std::push_heap, std::pop_heap, std::sort_heap, std::is_heap, std::is_heap_until. These are the building blocks behind std::priority_queue.
#include <algorithm>
#include <vector>

std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
std::make_heap(v.begin(), v.end());           // max-heap
std::cout << v.front() << std::endl;          // 9

v.push_back(10);
std::push_heap(v.begin(), v.end());           // re-sift after push_back

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

C++20 added a separate ranges library — std::ranges::sort(v)-style algorithm overloads, lazy view composition with |, projections, and std::span. Those topics live in their own note: C++ Ranges, Views, and Span.