The Standard Algorithms

The <algorithm> and <numeric> headers contain more than a hundred well-tested, efficient functions for searching, sorting, counting, transforming and summarising data. Using them instead of hand-written loops makes code shorter, clearer and less buggy.

The pattern

Classic algorithms take a range as two iterators (begin, end), and often a function — usually a lambda — that customises their behaviour. C++20 adds std::ranges:: versions that take the container directly, which this lesson uses where it reads better (lesson 26 covers ranges).

Searching and counting

C++ 
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> scores{72, 95, 64, 88, 95, 51, 79};

    auto it = std::find(scores.begin(), scores.end(), 88);
    std::cout << "88 at index " << (it - scores.begin()) << '\n';

    auto first_fail = std::find_if(scores.begin(), scores.end(), [](int s) { return s < 60; });
    std::cout << "first fail: " << *first_fail << '\n';

    std::cout << "count of 95: " << std::count(scores.begin(), scores.end(), 95) << '\n';
    std::cout << "passes: " << std::count_if(scores.begin(), scores.end(), [](int s) { return s >= 60; }) << '\n';

    std::cout << std::boolalpha
              << "all positive? " << std::all_of(scores.begin(), scores.end(), [](int s) { return s > 0; })
              << ", any perfect? " << std::any_of(scores.begin(), scores.end(), [](int s) { return s == 100; })
              << '\n';

    auto [lo, hi] = std::minmax_element(scores.begin(), scores.end());
    std::cout << "range " << *lo << "-" << *hi << '\n';
}
Output
88 at index 3
first fail: 51
count of 95: 2
passes: 6
all positive? true, any perfect? false
range 51-95

Sorting

C++ 
#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <vector>

int main() {
    std::vector<int> v{5, 2, 9, 1, 7};
    std::sort(v.begin(), v.end());                       // ascending
    for (int x : v) std::cout << x << ' ';
    std::sort(v.begin(), v.end(), std::greater<>{});     // descending
    std::cout << "| ";
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';

    std::vector<std::string> names{"Chloe", "ana", "Ben"};
    std::ranges::sort(names);                            // ranges version: pass the container
    for (const auto& n : names) std::cout << n << ' ';
    std::cout << '\n';
}
Output
1 2 5 7 9 | 9 7 5 2 1
Ben Chloe ana

std::stable_sort keeps equal elements in their original order; std::partial_sort sorts only the first n; std::nth_element finds the median quickly. Note that "ana" sorts after the capitalised names — comparison is by character code.

Binary search on sorted data

C++ 
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> ids{1043, 1187, 1201, 1356, 1499, 1602};
    std::cout << std::boolalpha << std::binary_search(ids.begin(), ids.end(), 1356) << '\n';
    auto pos = std::lower_bound(ids.begin(), ids.end(), 1400);   // first element >= 1400
    std::cout << "1400 would go before " << *pos << '\n';
}
Output
true
1400 would go before 1499

Transforming and copying

C++ 
#include <algorithm>
#include <cctype>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>

int main() {
    std::vector<double> prices{10.0, 4.5, 20.0};
    std::vector<double> with_tax;
    std::transform(prices.begin(), prices.end(), std::back_inserter(with_tax),
                   [](double p) { return p * 1.2; });
    for (double p : with_tax) std::cout << p << ' ';
    std::cout << '\n';

    std::vector<int> all{3, 8, 12, 5, 6, 9};
    std::vector<int> even;
    std::copy_if(all.begin(), all.end(), std::back_inserter(even), [](int x) { return x % 2 == 0; });
    for (int x : even) std::cout << x << ' ';
    std::cout << '\n';

    std::string s = "Shout";
    std::transform(s.begin(), s.end(), s.begin(), [](unsigned char c) { return std::toupper(c); });
    std::cout << s << '\n';
}
Output
12 5.4 24
8 12 6
SHOUT

std::back_inserter makes an output iterator that calls push_back, so the destination grows as needed.

Numeric algorithms

C++ 
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

int main() {
    std::vector<int> v(6);
    std::iota(v.begin(), v.end(), 1);                              // 1 2 3 4 5 6
    std::cout << "sum " << std::accumulate(v.begin(), v.end(), 0) << '\n';
    std::cout << "product " << std::accumulate(v.begin(), v.end(), 1, std::multiplies<>{}) << '\n';

    std::vector<int> running(v.size());
    std::partial_sum(v.begin(), v.end(), running.begin());
    for (int x : running) std::cout << x << ' ';
    std::cout << '\n';

    std::vector<std::string> words{"a", "b", "c"};
    std::cout << std::accumulate(words.begin(), words.end(), std::string{"letters:"}) << '\n';
}
Output
sum 21
product 720
1 3 6 10 15 21
letters:abc

The starting value decides the type of the result: accumulate(v.begin(), v.end(), 0) sums as int even for a vector of doubles — use 0.0 there.

Removing elements

To remove elements from a container in C++20, use std::erase and std::erase_if. (The older "erase–remove idiom" combined std::remove_if, which only shuffles elements, with the container's erase.)

C++ 
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 2, 3, 3, 3, 4};
    std::erase(v, 3);
    v.erase(std::unique(v.begin(), v.end()), v.end());      // drop adjacent duplicates
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
}
Output
1 2 4

Other useful algorithms

AlgorithmDoes
std::reverse, std::rotateReorder in place
std::fill, std::generateSet every element
std::equal, std::mismatchCompare two ranges
std::set_intersection, std::set_unionCombine sorted ranges
std::shuffleRandom order (lesson 46)
std::clampLimit a value to a range

Try it yourself

Given exam scores, compute the average, the median and how many students passed (≥ 50), using algorithms only.

Try it yourself · main.cpp
Edit the code, copy it into main.cpp, then compile and run it with c++ -std=c++20 -Wall main.cpp -o main && ./main. How to set up a C++ compiler
Output
average 65.7143, median 67, passed 5
PreviousLambdas