STL Algorithms: Iterator-Based Operations

The <algorithm> header provides ~100 algorithms operating on iterator ranges, enabling generic operations on any container.

Non-Modifying Algorithms

find, find_if, find_if_not

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

auto it = std::find(v.begin(), v.end(), 3);
if (it != v.end()) {
    std::cout << "Found: " << *it << '\\n';
}

auto it2 = std::find_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
// Finds first even number

count, count_if

auto n = std::count(v.begin(), v.end(), 3);
auto even_count = std::count_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });

all_of, any_of, none_of

bool all_positive = std::all_of(v.begin(), v.end(), [](int x) { return x > 0; });
bool has_even = std::any_of(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
bool no_negatives = std::none_of(v.begin(), v.end(), [](int x) { return x < 0; });

Modifying Algorithms

copy, copy_if

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

std::copy(src.begin(), src.end(), dst.begin());

std::vector<int> evens;
std::copy_if(src.begin(), src.end(), std::back_inserter(evens),
             [](int x) { return x % 2 == 0; });

transform

Apply function to each element:

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

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

// Binary transform
std::vector<int> a = {1, 2, 3};
std::vector<int> b = {4, 5, 6};
std::vector<int> sum(3);

std::transform(a.begin(), a.end(), b.begin(), sum.begin(),
               [](int x, int y) { return x + y; });
// sum = {5, 7, 9}

fill, generate

std::vector<int> v(10);
std::fill(v.begin(), v.end(), 42);  // All elements = 42

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

remove, remove_if

Careful: Doesn’t actually remove, just moves elements to end:

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

auto new_end = std::remove_if(v.begin(), v.end(),
                               [](int x) { return x % 2 == 0; });
v.erase(new_end, v.end());  // Actually erase
// v = {1, 3, 5}

// Idiomatic erase-remove:
v.erase(std::remove_if(v.begin(), v.end(),
                       [](int x) { return x < 3; }),
        v.end());

C++20 added std::erase_if for convenience:

std::erase_if(v, [](int x) { return x < 3; });

Sorting and Partitioning

sort, stable_sort, partial_sort

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

std::sort(v.begin(), v.end());  // O(n log n), unstable
// v = {1, 2, 5, 8, 9}

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

std::stable_sort(v.begin(), v.end());  // Preserves relative order of equal elements

nth_element

Partially sorts so that nth element is in correct position:

std::vector<int> v = {5, 2, 8, 1, 9, 3, 7};
std::nth_element(v.begin(), v.begin() + 3, v.end());

// v[3] is the 4th smallest element
// Elements before v[3] are <= v[3]
// Elements after v[3] are >= v[3]
// Relative order not specified

partition

std::vector<int> v = {1, 2, 3, 4, 5, 6};
auto pivot = std::partition(v.begin(), v.end(),
                            [](int x) { return x % 2 == 0; });
// Even numbers before pivot, odd after

Binary Search (on sorted ranges)

lower_bound, upper_bound, equal_range

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

auto lower = std::lower_bound(v.begin(), v.end(), 2);  // First >= 2
auto upper = std::upper_bound(v.begin(), v.end(), 2);  // First > 2

std::cout << std::distance(lower, upper);  // Count of 2's: 3

auto [first, last] = std::equal_range(v.begin(), v.end(), 2);  // C++17

binary_search

bool found = std::binary_search(v.begin(), v.end(), 3);  // O(log n)

Set Operations (on sorted ranges)

std::vector<int> a = {1, 2, 3, 4, 5};
std::vector<int> b = {3, 4, 5, 6, 7};
std::vector<int> result;

std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
                      std::back_inserter(result));
// result = {3, 4, 5}

result.clear();
std::set_union(a.begin(), a.end(), b.begin(), b.end(),
               std::back_inserter(result));
// result = {1, 2, 3, 4, 5, 6, 7}

result.clear();
std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
                    std::back_inserter(result));
// result = {1, 2}

Numeric Algorithms (<numeric>)

accumulate, reduce

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<>());  // 120

// C++17 reduce (parallel)
int sum2 = std::reduce(std::execution::par, v.begin(), v.end());

partial_sum, adjacent_difference

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

std::partial_sum(v.begin(), v.end(), result.begin());
// result = {1, 3, 6, 10, 15}  (cumulative sum)

std::adjacent_difference(v.begin(), v.end(), result.begin());
// result = {1, 1, 1, 1, 1}  (differences)