sort, find, count, accumulate and lambdas

Counting, summing, searching and sorting come up in almost every program. Writing a loop for them every time is like carving a new spoon each evening instead of taking one from the drawer. In C++, that drawer is the <algorithm> header with its ready-made functions. They take the range of elements as two iterators, begin() and end(): the first points at the start, the second one past the last element.

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

int main() {
    std::vector<int> v{5, 3, 8, 3};
    std::cout << std::count(v.begin(), v.end(), 3) << ' '
              << std::accumulate(v.begin(), v.end(), 0) << '\n';  // 2 19
    std::sort(v.begin(), v.end());
    for (int x : v) {
        std::cout << x << ' ';  // 3 3 5 8
    }
}

Let's walk through the program line by line:

1. std::count returns the number of elements equal to its third argument: two threes.
2. std::accumulate from the <numeric> header adds up the elements and adds them to the starting value, its third argument 0. The result is 19.
3. std::sort reorders the elements of the vector itself in ascending order and returns nothing. The number of elements stays the same: both threes are still in the vector.

Sorting takes O(n log n), while count and accumulate take O(n).

Searching and predicates

std::find returns an iterator to the first element equal to the value, or end() if there is none. So the result is compared with end() before the element is read:

std::vector<int> v{5, 3, 8, 3};
auto it = std::find(v.begin(), v.end(), 8);
if (it != v.end()) {
    std::cout << *it << '\n';  // 8
}
auto big = std::count_if(v.begin(), v.end(), [](int x) { return x > 4; });
std::cout << big << '\n';  // 2

A predicate is a function that takes an element and returns a bool. A lambda written right in the call is a convenient way to pass one: here the lambda says "yes" for numbers greater than 4. std::count_if counts the elements for which the predicate returns true, and std::find_if finds the first such element.

A custom sort order

The third argument of std::sort is a comparator: a function of two elements that returns true if a must stand before b. Without a comparator, elements are compared with <. With the comparator [](int a, int b) { return a > b; }, the numbers end up in descending order. A true answer from a comparator means "strictly before": for equal elements the comparator returns false.

std::sort may reorder equal elements among themselves. A stable sort, std::stable_sort, keeps them in their original order:

std::vector<std::string> words{"pear", "fig", "kiwi", "apple"};
auto shorter = [](const std::string& a, const std::string& b) {
    return a.size() < b.size();
};
std::stable_sort(words.begin(), words.end(), shorter);
for (const std::string& w : words) {
    std::cout << w << ' ';  // fig pear kiwi apple
}

The words pear and kiwi have the same length, and pear stays first, as in the original vector. After std::sort, kiwi could have ended up first of the two.

Common mistake

The comparator uses <= instead of <:

std::vector<int> v{5, 3, 8, 3};
std::sort(v.begin(), v.end(), [](int a, int b) { return a <= b; });  // ✗

For the two equal threes, this comparator says that each must stand before the other. std::sort requires a strict comparison, so the call with <= is undefined behavior, even though the code compiles without warnings. In the course exercises, such a comparator may stop the program. Write a < b, or a > b for descending order.

Key points

• The functions of <algorithm> take a range as two iterators: begin() and end().
• Compare the result of std::find with end() before reading the element.
• A comparator returns true only if a stands strictly before b: write <, not <=.
• std::stable_sort keeps equal elements in their order, and std::sort does not.