Algorithms

The <algorithm> and <numeric> headers hold ready-made loops: sort, find, count, and fold a range of values into one result. By the end of this lesson you can call them on a vector, pass your own rule as a lambda, and pick an accumulator type that does not overflow.

Ranges: a begin and an end

Algorithms do not take a container. They take a range: two iterators, v.begin() pointing at the first element and v.end() pointing one past the last. You met this pair with std::max_element in the vector lesson. Every container supplies them, so one std::sort works on a vector, a string or an array.

#include <algorithm>
std::vector<int> temps = {18, -4, 7, 25, 7};

std::sort(temps.begin(), temps.end());          // -4 7 7 18 25
std::count(temps.begin(), temps.end(), 7)       // 2
*std::min_element(temps.begin(), temps.end())   // -4 (dereference the iterator)
auto it = std::find(temps.begin(), temps.end(), 99);
it == temps.end()                               // true: 99 is absent

find hands back end() when nothing matches, so compare against it before using *it.

Lambdas: your rule, written inline

A lambda is an unnamed function written where it is used: [capture](parameters) { body }. Empty [] means it uses only its parameters. The _if algorithms take one as a predicate, a function that answers true or false:

std::vector<std::string> words = {"map", "vector", "set", "string"};
long n = std::count_if(words.begin(), words.end(),
    [](const std::string& w) { return w.size() > 3; });      // 2

std::sort(temps.begin(), temps.end(),
    [](int a, int b) { return a > b; });                     // 25 18 7 7 -4

A sort comparator returns true when a must come before b.

accumulate: folding a range into one value

std::accumulate(first, last, seed, op) starts a running value at seed and replaces it with op(running, element) for each element. Without op it adds. To keep only some elements, return the running value unchanged when an element does not qualify:

#include <numeric>
std::vector<int> prices = {4, 12, 30, 7};
long long big = std::accumulate(prices.begin(), prices.end(), 0LL,
    [](long long run, int p) { return p > 10 ? run + p : run; });
// run: 0 -> 0 (4) -> 12 (12) -> 42 (30) -> 42 (7)      big == 42

The seed also fixes the type of the running value. Seed with 0 and every step is squeezed back into an int:

std::vector<int> m = {2000000000, 2000000000};
std::accumulate(m.begin(), m.end(), 0)     // -294967296  (wrong)
std::accumulate(m.begin(), m.end(), 0LL)   // 4000000000  (right)

Two arithmetic traps

Multiply before widening. int a = 60000; long long bad = a * a; computes the product in int first, overflows, and stores -694967296. Write 1LL * a * a: the long long on the left promotes the whole product, giving 3600000000.

Remainder of a negative. In C++ -7 % 2 is -1, not 1. Test evenness with n % 2 == 0, which is right for every sign. A test like n % 2 != 1 wrongly accepts -7 as even.

Common mistakes

• Squaring in int. x * x with x = 50000 overflows and prints a negative number instead of 2500000000. Widen one factor first.
• Seeding with 0. Two squares of 40000 fit in a long long but not in an int, so an int seed prints -1094967296 instead of 3200000000.
• Testing % 2 != 1. -3 then counts as even, and -3 -5 4 prints 50 instead of 16.
• Forgetting the filter. Adding every element's square sums the odd squares too.

Your exercise

Print the sum of the squares of the even numbers in a line of integers. The starter reads the numbers into a std::vector<int> and prints total; you compute total, with a loop or with std::accumulate and a lambda. The likely bug is overflow: the values are int, but their squares are not.