sort, find, count, accumulate and lambdas

Counting, summing, searching and sorting come up in almost every program, and they do not need a hand-written loop each time. The <algorithm> header holds ready-made functions for these tasks. They take the elements as two iterators, begin() and end():

#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
    }
}

std::count returns the number of elements equal to its third argument. std::accumulate from the <numeric> header adds up the elements, starting from the value 0.

std::sort reorders the elements of the vector itself in ascending order and returns nothing. The number of elements stays the same, and both threes are still there. 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. 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 comparator means "strictly before": for equal elements it 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.