Lambdas and the algorithm library

A range, not a container

The algorithms do not work on a list directly. They work on a pair of iterators naming a range: values.begin() is the first item and values.end() is the position just past the last. That is the half-open range every algorithm assumes, which is why an empty list has begin equal to end.

Because the pair is just two positions, the same algorithms work on a vector, a string, a plain array, and the middle of anything — values.begin() + 1 starts one item in. This is the idea the whole library is built on.

A lambda is a function written inline

A lambda is a small function you write at the point of use: [](int n) { return n > 4; }. The square brackets are the capture list and the parentheses are the parameter list, so the shape is "here is a function, taking an int, answering whether it is over four".

Most lambdas are handed to an algorithm and never named. The alternative is a separate function elsewhere in the file, which splits a rule from the line that needed it. When the rule is genuinely shared, name it; when it belongs to one call, a lambda keeps the two together.

The four algorithms worth knowing first

sort(first, last) puts a range in order, and sort(first, last, rule) uses your own comparison. find_if(first, last, test) answers an iterator to the first item that passes the test. count_if(first, last, test) answers how many pass. transform(first, last, destination, change) writes a changed copy, and when the destination is the same begin, it changes the items in place.

Two things to know before you use them. transform writes into a destination, so using it with begin twice is only safe because the output is the same length as the input. And a lambda that needs a value from outside has to capture it: [limit](int n) { return n > limit; } copies limit into the lambda, while [&limit] would take a reference to it.

Four algorithms in one program

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> values = {5, 2, 9, 2, 7};

    sort(values.begin(), values.end());

    auto found = find_if(values.begin(), values.end(),
                         [](int n) { return n > 4; });
    std::cout << "first over 4: " << *found << '\n';

    int twos = count_if(values.begin(), values.end(),
                        [](int n) { return n == 2; });
    std::cout << "twos: " << twos << '\n';

    std::vector<std::string> names = {"ada", "bob"};
    transform(names.begin(), names.end(), names.begin(),
              [](std::string s) { return s + "!"; });
    for (const std::string& name : names) {
        std::cout << name << ' ';
    }
    std::cout << '\n';
    return 0;
}

Captures, and the lifetime they promise

A capture list decides what the lambda can see. [x] copies x into the lambda at the moment it is created; [&x] stores a reference, so the lambda sees later changes and must not outlive x. [=] and [&] capture everything used, which is convenient in a short algorithm call and risky in a lambda stored for later.

A lambda is an object, so it can be copied and called more than once, and its captures are part of that object. If you need to change a captured copy from inside, mark the lambda mutable; without it the call operator is const. Prefer naming the few values you need — a short capture list documents the dependencies.

The algorithms answer different shapes: find and find_if answer iterators, count and count_if answer numbers, and any_of, all_of and none_of answer bools. accumulate, from <numeric>, folds a range into one value. Matching the algorithm to the answer you need avoids a hand-written loop that exists only to set a flag.

Where the output goes

transform writes its results into a destination range, and the destination is a parameter like any other. Passing values.begin() twice means the output overwrites the input as it goes, which is safe only because each item is read before it is written. Passing a separate squared.begin() leaves the original untouched, which is what you want when both are needed afterwards.

The destination must have room. transform does not resize a vector, so create it with the right size first, and the same is true of copy and replace. The size is your responsibility, not the algorithm.

A range is half-open for the same reason a slice is: the end names the first position you may not read. values.end() - 1 is the last item, and values.begin() == values.end() is how an empty range says there is nothing to do.

Try these next

• Sort names by length, and use the name itself to break ties.
• Count the values above a threshold captured from a variable.
• Use all_of to check that every score is at least zero.