Algorithms - STL Algorithms

S6.0 What This Teaches

The <algorithm> header provides generic algorithms that work with any range via iterators. This tutorial covers:

Iterators and the begin/end range model
sort, find, find_if
transform, copy_if
accumulate from <numeric>
for_each
The erase-remove idiom

S6.1 Iterators and the Range Model

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

// begin() points to first element; end() points one past last
auto first = v.begin();  // iterator to 3
auto last  = v.end();    // one past 5

// algorithms take a [first, last) half-open range
std::sort(first, last);

Algorithms operate on ranges, not containers. The same algorithm works on vectors, arrays, strings, and any other container that provides iterators.

S6.2 sort

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

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 % 2 < b % 2; }); // evens first

S6.3 find and find_if

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 at index " << std::distance(v.begin(), it) << "\n";

auto even = std::find_if(v.begin(), v.end(), [](int x){ return x % 2 == 0; });
if (even != v.end())
    std::cout << "first even: " << *even << "\n";

S6.4 transform

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

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

The output iterator must point to a range with enough space. Pass std::back_inserter(out) to append to an empty vector instead of writing to a pre-sized one.

S6.5 accumulate and copy_if

#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> evens;
std::copy_if(v.begin(), v.end(), std::back_inserter(evens),
             [](int x){ return x % 2 == 0; });
// evens = {2, 4}

S6.6 The Erase-Remove Idiom

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

// remove returns an iterator to the new logical end
auto new_end = std::remove(v.begin(), v.end(), 2);
v.erase(new_end, v.end());   // erase the "removed" tail
// v = {1, 3, 4, 5}

std::remove does not actually erase elements - it shifts non-matching elements forward. erase is needed to shrink the vector. C++20 provides std::erase and std::erase_if that combine both steps.

S6.7 Example - All Together

// Algorithms - sort, find, transform, accumulate, copy_if, for_each.

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

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

    std::sort(v.begin(), v.end());
    std::cout << "sorted: ";
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";

    auto it = std::find_if(v.begin(), v.end(), [](int x){ return x > 5; });
    std::cout << "first >5: " << *it << "\n";

    std::vector<int> doubled;
    std::transform(v.begin(), v.end(), std::back_inserter(doubled),
                   [](int x){ return x * 2; });
    std::cout << "doubled: ";
    for (int x : doubled) std::cout << x << " ";
    std::cout << "\n";

    int sum = std::accumulate(v.begin(), v.end(), 0);
    std::cout << "sum=" << sum << "\n";

    std::vector<int> evens;
    std::copy_if(v.begin(), v.end(), std::back_inserter(evens),
                 [](int x){ return x % 2 == 0; });
    std::cout << "evens: ";
    for (int x : evens) std::cout << x << " ";
    std::cout << "\n";
    return 0;
}

sorted: 1 2 3 4 5 6 7 8 9
first >5: 6
doubled: 2 4 6 8 10 12 14 16 18
sum=45
evens: 2 4 6 8

S6.8 Exercise

Exercise

Use std::count_if to count how many elements in a vector are divisible by 3.
Use the erase-remove idiom to remove all negative numbers from a vector<int>.
Use std::min_element and std::max_element to find the smallest and largest values in a vector without sorting it.

S6.9 Key Terms

Term	Meaning
iterator	Object that points into a range; supports ++, *, == operations
[first, last)	Half-open range: includes first, excludes last
std::sort	In-place sort of a range; O(n log n)
std::find / find_if	Linear search; returns iterator to first match or end()
std::transform	Apply function to each element, write result to output range
std::accumulate	Fold range with binary operation; in <numeric>
std::copy_if	Copy elements satisfying predicate to output range
std::back_inserter	Output iterator adapter that calls push_back on each write
erase-remove idiom	std::remove + erase() to delete elements by value from a vector