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

1. std::initializer_list

  • std::initializer_list<T> (C++11, <initializer_list>) — functions/ctors accept brace-enclosed lists. Enables uniform init 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:

  1. Elements always const — can't modify through the list.
  2. Copy doesn't copy underlying elements — lightweight.
  3. Underlying array has automatic storage duration (temporary).

2. Sorting and Partitioning

  • <algorithm> provides the sorting suite.
  • sort, stable_sort, partial_sort, nth_element need random-access iterators.
  • partition needs forward; stable_partition needs bidirectional.
  1. std::sort(first, last, [cmp]) — Introsort; O(n log n) avg + worst. Not stable.
  2. std::stable_sort(first, last, [cmp]) — preserves relative order of equals. O(n log² n) worst.
  3. std::partial_sort(first, middle, last, [cmp]) — sort just enough so [first, middle) holds smallest in order. For top-k.
  4. std::nth_element(first, nth, last, [cmp]) — puts kth element in sorted position; before all ≤, after all ≥. O(n) avg. Fastest kth-order statistic.
  5. std::partition(first, last, pred) — reorder so pred elements come first. Returns 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

  • Unsorted → linear scans. Sorted → binary searches.
  1. std::find(first, last, value) — linear; iterator to first match or last.
  2. std::find_if(first, last, pred) — linear by predicate.
  3. std::binary_search(first, last, value) — bool only; true if present.
  4. std::lower_bound(first, last, value) — first position where value could insert without breaking order (first >= value).
  5. std::upper_bound(first, last, value) — first strictly greater than value.
  6. std::equal_range(first, last, value) — pair (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

  • Read but don't write range.
  1. std::count(first, last, value), std::count_if(first, last, pred) — count occurrences.
  2. std::all_of, std::any_of, std::none_of — predicate quantifiers.
  3. std::for_each(first, last, fn) — apply fn to each. Modern → range-for loop preferred.
  4. std::min_element, std::max_element, std::minmax_element — extrema in O(n).
  5. std::equal(first1, last1, first2) — element-wise equality of two ranges.
  6. std::mismatch(first1, last1, first2) — first position where two ranges differ.

5. Modifying Algorithms

  • Write into destination range.
  1. std::copy(first, last, d_first), std::copy_if(...) — copy with optional filter.
  2. std::move(first, last, d_first) — move (not copy); source elements valid-but-unspecified. The algorithm, not std::move the cast.
  3. std::transform(first, last, d_first, fn) — apply fn, write result. Binary form for 2 input ranges.
  4. std::fill(first, last, value), std::generate(first, last, fn) — fill with constant or generator.
  5. std::replace, std::replace_if — in-place replace.
  6. std::remove(first, last, value), std::remove_if(...) — erase-remove idiom: returns new logical end; must follow with container.erase(...) to shrink. C++20 → std::erase/std::erase_if combine both.
  7. std::reverse, std::rotate — reorder in place.
  8. std::unique(first, last) — removes consecutive duplicates; sort first for global uniqueness. Same erase-remove pattern.
// 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

  • <numeric> — reductions + prefix sums.
  1. std::accumulate(first, last, init, [op]) — sequential reduction. Default op = +. For floats, order matters.
  2. std::reduce(first, last, init, [op]) — like accumulate but unsequenced (parallelizable). Requires op associative + 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 ops (sorted input + sorted output): set_union, set_intersection, set_difference, set_symmetric_difference, includes, merge.
  2. Heap ops (on RandomAccessRange = max-heap): make_heap, push_heap, pop_heap, sort_heap, is_heap, is_heap_until. 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 separate ranges library — std::ranges::sort(v) overloads, lazy view composition with |, projections, std::span. See C++ Ranges, Views, and Span.