Skip to main content
Be Bitwise
C++Templates & the STL

STL Algorithms

<algorithm> is a small library of generic operations that talk to containers through iterators. Dozens of them, all reusable.

Sorting

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

cpp
// Binary search (requires sorted container)
bool found = std::binary_search(v.begin(), v.end(), 5);
// Find an element
auto it = std::find(v.begin(), v.end(), 42);
if (it != v.end()) {
std::cout << "Found at index " << (it - v.begin()) << std::endl;
}
// Find with predicate
auto it2 = std::find_if(v.begin(), v.end(), [](int x) { return x > 5; });

Transforming

cpp
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}
Key Concept

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

cpp
#include <numeric>
std::vector<int> v = {1, 2, 3, 4, 5};
int sum = std::accumulate(v.begin(), v.end(), 0); // 15
// With custom operation
int product = std::accumulate(v.begin(), v.end(), 1,
[](int a, int b) { return a * b; }); // 120

Lambdas

Lambdas are anonymous functions. You'll see them paired with algorithms constantly:

cpp
auto is_even = [](int x) { return x % 2 == 0; };
int count = std::count_if(v.begin(), v.end(), is_even);
// Capture variables
int threshold = 3;
auto above = [threshold](int x) { return x > threshold; };

Capture modes:

  • [=] - capture all by value
  • [&] - capture all by reference
  • [x] - capture x by value
  • [&x] - capture x by 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.

Try itReplace the three loops with std::accumulate, std::find and std::count_if, then capture threshold in a lambda.
C++ (GCC 9.2.0)

Removing Elements

The erase-remove idiom:

cpp
std::vector<int> v = {1, 2, 3, 2, 4, 2, 5};
// Remove all 2s
v.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())

1
[0]
2
[1]↑ write
3
[2]
2
[3]
4
[4]
2
[5]
5
[6]
size() = 7
Start: v = {1, 2, 3, 2, 4, 2, 5}. remove first scans for the first 2. It's at index 1, so that slot becomes the write position.
Step 1/8

C++20 cuts the ceremony with std::erase (not in the C++14 runner above):

cpp
std::erase(v, 2); // same result

Challenges

Sort a vector of integers in descending order using std::sort with a custom comparator.

C++ (GCC 9.2.0)