STL Algorithms
<algorithm> is a small library of generic operations that talk to containers through iterators. Dozens of them, all reusable.
Sorting
#include <algorithm>#include <vector>
std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};std::sort(v.begin(), v.end()); // ascending// v = {1, 1, 2, 3, 4, 5, 6, 9}
// Custom comparator (descending)std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });Searching
// Binary search (requires sorted container)bool found = std::binary_search(v.begin(), v.end(), 5);
// Find an elementauto it = std::find(v.begin(), v.end(), 42);if (it != v.end()) { std::cout << "Found at index " << (it - v.begin()) << std::endl;}
// Find with predicateauto it2 = std::find_if(v.begin(), v.end(), [](int x) { return x > 5; });Transforming
std::vector<int> input = {1, 2, 3, 4};std::vector<int> output(input.size());
std::transform(input.begin(), input.end(), output.begin(), [](int x) { return x * x; });// output = {1, 4, 9, 16}STL algorithms are generic. Hand them a container with the right iterator category and they'll work. std::sort wants random-access iterators, so vectors, arrays, deques, and raw C arrays are fine. std::list is excluded, which is why it ships its own .sort() member. Decoupling algorithms from containers like this is the central design move of the whole STL.
Accumulate and Reduce
#include <numeric>
std::vector<int> v = {1, 2, 3, 4, 5};int sum = std::accumulate(v.begin(), v.end(), 0); // 15
// With custom operationint product = std::accumulate(v.begin(), v.end(), 1, [](int a, int b) { return a * b; }); // 120Lambdas
Lambdas are anonymous functions. You'll see them paired with algorithms constantly:
auto is_even = [](int x) { return x % 2 == 0; };
int count = std::count_if(v.begin(), v.end(), is_even);
// Capture variablesint threshold = 3;auto above = [threshold](int x) { return x > threshold; };Capture modes:
[=]- capture all by value[&]- capture all by reference[x]- capturexby value[&x]- capturexby reference
Time to practise. Each block in main is a hand-written loop that one algorithm call can replace. Swap them out one at a time and make sure the output doesn't change.
Removing Elements
The erase-remove idiom:
std::vector<int> v = {1, 2, 3, 2, 4, 2, 5};
// Remove all 2sv.erase(std::remove(v.begin(), v.end(), 2), v.end());// v = {1, 3, 4, 5}std::remove can't change a vector's size; it only sees iterators. So it slides the values you're keeping towards the front and returns an iterator to the new logical end. erase is what actually shrinks the vector. Step through it below and note what's left past the returned iterator before erase runs.
v.erase(std::remove(v.begin(), v.end(), 2), v.end())
C++20 cuts the ceremony with std::erase (not in the C++14 runner above):
std::erase(v, 2); // same resultChallenges
Sort a vector of integers in descending order using std::sort with a custom comparator.