Lesson 216 +5 XP

<algorithm> Reference

The <algorithm> header is the standard library's toolbox: sort, find, transform, count - all iterating over elements without you writing the loops. Includes names are in the std.

Basics first

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> v = {3, 1, 2};
    sort(v.begin(), v.end());        // v becomes {1, 2, 3}
    for (int x : v) cout << x;
}

Most algorithms take two iterators: begin where to start and end where to stop (exclusive).

The big table

Function	Sample call	What it does
`sort`	`sort(begin, end)`	sorts the range ascending
`reverse`	`reverse(begin, end)`	flips the range
`find`	`find(begin, end, val)`	1st iterator where element equals val, else `end`
`find_if`	`find_if(begin, end, pred)`	1st element passing the predicate, else `end`
`count`	`count(begin, end, val)`	how many elements equal val
`count_if`	`count_if(begin, end, pred)`	how many elements pass the predicate
`min_element`	`min_element(begin, end)`	iterator to the smallest element
`max_element`	`max_element(begin, end)`	iterator to the largest element
`min`	`min(a, b)`	smaller of two values
`max`	`max(a, b)`	larger of two values
`copy`	`copy(first, last, out)`	copies the range to another destination
`accumulate`	`accumulate(first, last, init)`	add values up, starting at init
`unique`	`unique(begin, end)`	removes adjacent duplicates (sort first)
`binary_search`	`binary_search(begin, end, val)`	`true` if val is in a SORTED range
`for_each`	`for_each(begin, end, fn)`	call fn on every element

The signature of most algorithms

Nearly all follow one shape:

algorithm(firstIterator, lastIterator, extraArgs, ...)

The result is typically an iterator into the same range. Check against end() - that is C++'s universal "not found" answer:

auto it = find(v.begin(), v.end(), 99);
if (it != v.end()) {
    cout << "found: " << *it;
}

Predicate functions

find_if and count_if accept a "predicate" - something that returns true/false per element:

bool isEven(int n) { return n % 2 == 0; }
int evens = count_if(v.begin(), v.end(), isEven);

Or write a lambda inline (C++11):

int evens = count_if(v.begin(), v.end(),
                     [](int n) { return n % 2 == 0; });

accumulate

accumulate lives in <numeric>, not <algorithm> - a common gotcha:

#include <numeric>
int sum = accumulate(v.begin(), v.end(), 0);

Notes

binary_search REQUIRES a sorted range; on unsorted data results are undefined. Sort first.
unique removes adjacent duplicates - so sort, then unique, to dedumplicate all duplicates.
min/max, min_element/max_element: the element versions return iterators/values; the value versions return the actual value.
Compare.cpp to the docs as you go; the defaults are great but sort can take a custom comparator: sort(begin, end, greater<int>()).
for_each using a range-for loop instead. std::for_each matters when you need an algorithm in the pipeline.

TL;DR

The pattern: alg(first, last, args) returns an iterator or a count.
"Not found" means returning end.
Sort -> then binary_search; sort -> then unique then binary_search.
count_if/find_if accept a predicate (function or lambda).
accumulate is in <numeric>, not <algorithm>.

<algorithm> Reference