C++ / ITERATORS, ALGORITHMS, AND RANGES
The algorithms header and its vocabulary
Read any algorithms-header name and predict its signature: the _if, _copy, _n, stable_ and is_ affixes, the fixed argument order, and what each return value means.
What you will learn
- Decode a name from its affixes: _if, _copy, _n, stable_, is_, _until, _backward
- Spell not-found as a comparison against the last iterator you passed in
- Use the iterator returned by a _copy algorithm to count or chain the output
- Read InputIt, RandomIt and UnaryPred in a signature as hard requirements
Understanding The algorithms header and its vocabulary
The algorithms header is not a hundred unrelated functions. It is a small set of verb stems - find, count, copy, fill, replace, remove, unique, reverse, rotate, partition, merge, sort - crossed with a fixed set of affixes, and every one of them speaks in iterators rather than containers. Ranges are half-open: first points at an element, last points one past the last one, so an empty range is simply first == last and no algorithm needs a special case for nothing-to-do. Because a pair of iterators says nothing about the container that owns them, nothing in this header can grow, shrink or reallocate anything; the most a mutating algorithm can do is move values around and tell you where the interesting boundary ended up.
Four affixes carry most of the weight. _if swaps a value argument for a predicate, and it exists as a separate name because an element type can itself be callable, so one overload set could not always tell whether you meant compare-equal-to-f or call-f. _copy leaves the input untouched and writes through a destination iterator (reverse versus reverse_copy), _n replaces the second iterator with a count (copy versus copy_n), and stable_ adds a promise that equivalent elements keep their relative order, usually paid for with a temporary buffer. The remaining affixes are just as regular: is_ asks a yes-or-no question, _until returns the position where a property first fails, _backward writes from the far end toward the near one, _if_not negates a predicate you already have, and the argument order never varies - input range, then any destination iterator, then plain values, then the callable last.
Return values are part of the same vocabulary and come in families. A search hands back an iterator to the hit, or last itself when there is no hit, because there is no null iterator to return; that is why failure is expressed by comparing the result with the end you passed in. A writing algorithm returns one past the last element it wrote, which is how you measure the output or start a second call where the first stopped, while a rearranging algorithm returns the new boundary between the groups it created. Even the template parameter names in a signature are information: InputIt, ForwardIt, BidirIt, RandomIt, OutputIt, UnaryPred and Compare tell you the weakest iterator the algorithm will accept and how many arguments your callable is going to receive.
Learning the algorithms header means learning its grammar rather than memorising its inventory.
<algorithm>
<iostream>
<vector>
int main() {
std::vector<int> v{4, 8, 15, 16, 23, 42};
// value form compares with ==, the _if form takes a predicate
auto at23 = std::find(v.begin(), v.end(), 23);
auto odd = std::find_if(v.begin(), v.end(), [](int x) { return x % 2 != 0; });
auto gone = std::find(v.begin(), v.end(), 99);
std::cout << std::boolalpha;
std::cout << "find(23) index: " << (at23 - v.begin()) << '\n';
std::cout << "find_if(odd) index: " << (odd - v.begin()) << '\n';
std::cout << "find(99) == end(): " << (gone == v.end()) << '\n';
// _copy leaves v alone and returns one past the last element written
std::vector<int> out(v.size());
auto written = std::replace_copy_if(v.begin(), v.end(), out.begin(),
[](int x) { return x > 20; }, 0);
std::cout << "written: " << (written - out.begin()) << '\n';
std::cout << "out:";
for (int x : out) std::cout << ' ' << x;
std::cout << '\n';
// _n replaces the second iterator with a count
std::vector<int> head(3);
std::copy_n(v.begin(), 3, head.begin());
std::cout << "head:";
for (int x : head) std::cout << ' ' << x;
std::cout << '\n';
}Names in the algorithms header are compositional - stem plus affix, iterators in, iterator out - so the name of a function tells you its signature and its return meaning.
Worked examples
What stable_ buys and what the boundary iterator means
Shows the stable_ prefix as an ordering promise and the returned iterator as the split point of two half-open ranges.
<algorithm>
<iostream>
<string>
<vector>
int main() {
std::vector<std::string> names{"ada", "grace", "alan", "guido", "anita"};
auto mid = std::stable_partition(names.begin(), names.end(),
[](const std::string& s) { return s[0] == 'a'; });
std::cout << "split index: " << (mid - names.begin()) << '\n';
std::cout << "kept:";
for (auto it = names.begin(); it != mid; ++it) std::cout << ' ' << *it;
std::cout << "\nrest:";
for (auto it = mid; it != names.end(); ++it) std::cout << ' ' << *it;
std::cout << '\n';
}Example explained
Line 1stable_partition pushes every name beginning with a to the front, and the stable_ prefix is the promise that ada, alan and anita keep their original relative order; plain partition makes no such promise.
Line 2The returned mid is the boundary, so the two groups are the half-open ranges [begin, mid) and [mid, end) - the same convention the algorithm was handed on the way in.
Line 3mid - names.begin() turns that boundary into the index 3, which is only possible because vector iterators support subtraction.
Line 4The predicate takes one element by const reference and returns bool; it is expected to be side-effect free, and stable_partition may allocate a temporary buffer in order to keep its ordering guarantee.
Four return shapes from one predicate
Demonstrates that the family a name belongs to determines whether you get a bool, a count, an iterator, or a pair of iterators.
<algorithm>
<iostream>
<vector>
int main() {
std::vector<int> temps{18, 21, 19, 24, 17, 22};
auto warm = [](int t) { return t >= 18; };
std::cout << std::boolalpha;
std::cout << "all_of: " << std::all_of(temps.begin(), temps.end(), warm) << '\n';
std::cout << "any_of: " << std::any_of(temps.begin(), temps.end(), warm) << '\n';
std::cout << "count_if: " << std::count_if(temps.begin(), temps.end(), warm) << '\n';
auto cold = std::find_if_not(temps.begin(), temps.end(), warm);
std::cout << "first cold at index " << (cold - temps.begin())
<< ", value " << *cold << '\n';
auto mm = std::minmax_element(temps.begin(), temps.end());
std::cout << "min " << *mm.first << ", max " << *mm.second << '\n';
}Example explained
Line 1all_of, any_of and none_of return bool: they answer a question and deliberately hand back no position, which is why the false gives no hint that 17 was the offender.
Line 2count_if returns the iterator's difference_type, a signed integer, so comparing its result straight against temps.size() produces a signed/unsigned warning.
Line 3find_if_not is the ready-made negation of a predicate you already have, and dereferencing its result is safe here only because a cold reading exists, so cold is not end().
Line 4minmax_element belongs to the small family returning a pair of iterators, so each half needs a dereference; it also promises the first of several equal minima and the last of several equal maxima.
Important notes
A Compare argument must mean strictly before, not before-or-equal. Build one from <= and two equivalent elements each compare before the other, which breaks the strict weak ordering the whole header assumes and puts you in undefined behaviour.
This header holds only part of the vocabulary: reductions such as accumulate live in numeric, ready-made comparators such as std::greater in functional, and output adaptors such as back_inserter in iterator.
Common mistakes
Passing a lambda to std::find, or a bare value to std::find_if. find compares elements with ==, so the compiler tries to compare an int against a closure type and you get pages of template errors from inside the header rather than a clear wrong-function message.
Dereferencing the iterator a search returned without first comparing it against the end iterator. On failure the algorithm hands back last, and reading through the end of a vector is undefined behaviour that often prints a believable number instead of crashing.
Expecting a _copy algorithm to make room in the destination. Calling replace_copy_if into out.begin() when out is empty writes through an iterator that owns no storage and corrupts memory; size the destination up front or pass an inserting output iterator.
Try it yourself
Change, predict, then run
Start from std::vector<int> v{3, -1, 4, -1, 5, -9, 2} and use only count_if, find_if and replace_copy_if to print how many values are negative, the index of the first negative, and a copy in which every negative became 0. Then swap find_if for find_if_not and predict the index it prints before you run it.
Open the C++ workspaceCheck your understanding
Why does the standard give the predicate version of find its own name, find_if, instead of simply adding another overload of find?
- Because overload resolution cannot always separate a value from a predicate: an element type can itself be callable, which would leave a single name ambiguous
- Because find_if stops at the first match while find is required to scan the whole range
- Because find needs random access iterators while find_if works with input iterators
- Because a function template cannot accept a lambda unless the name advertises it
Show answer
If the elements were themselves callable objects, find(first, last, f) could plausibly mean the element equal to f or the first element for which f is true, so the predicate form needed a distinct name - the same reason count_if, remove_if and replace_if exist. Early exit is not the difference: plain find also stops at its first match, and both versions accept the same input iterators.