Standard Library Algorithms

In the previous lesson, we introduced the iterator pattern. We learned that iterators are the universal bridge between how data is stored (containers) and how data is processed (algorithms).

However, so far, the only "algorithm" we have written is a raw for loop.

1// The "Raw Loop" - The assembly language of logic
2for (auto it = v.begin(); it != v.end(); ++it) {
3  if (*it == target) {
4    // ... logic ...
5    break;
6  }
7}

In modern C++, and indeed most software engineering, a raw loop is often considered a "code smell."

A raw loop tells us how something is happening ("increment this counter, check this boolean, dereference this pointer"), but it obscures what is happening. Are we finding an item? Counting items? Transforming them? Filtering them? You have to start deciphering the loop body to figure it out.

For example, if we have some code in one of our functions that is tasked with finding something, we'd rather that be expressed using syntax like find(data, 42) rather than a 5-line loop.

The C++ standard library provides a massive toolkit of algorithms that we can use to replace these loops with named, optimized, and tested functions.

In this lesson, we will walk through a lot of examples of different algorithms, but the algorithms themselves aren't important at this stage. Instead, the key goal is just just to pick up some of the common, recurring themes in how we interact with those algorithms. In particular:

• how we supply algorithms with our data using iterators
• how we can customize the behavior of algorithms by providing functions / lambdas as arguments
• how we get the algorithm results, either through the iterators they return, or the data they write to a memory location

The algorithms in the standard library (mostly found in the <algorithm> and <numeric> headers) are consumers of iterators. They take a pair of iterators representing the range of data to process. These iterators are often those returned by the begin() and end() methods of some container we're working on.

Let's look at one of the most common examples: searching.

Using std::find()

If you want to find a specific value in a container, we can use std::find(). It returns an iterator to the found element, or an iterator that will be equal to the sentinel if the element wasn't found:

1#include <vector>
2#include <algorithm> // Required for std::find
3#include <iostream>
4
5int main() {
6  std::vector<int> data{10, 20, 30, 40, 50};
7
8  // Find the number 30
9  auto it = std::find(data.begin(), data.end(), 30);
10
11  // Check if we found it
12  // Remember: end() is a sentinel. It means "Not Found".
13  if (it != data.end()) {
14    std::cout << "Found " << *it << " at index: "
15              << std::distance(data.begin(), it) << "\n";
16  }
17}

1Found 30 at index: 2

Behind the scenes, std::find() iterates linearly from begin() to end().

Because it is a template, the compiler generates a specialized version of find() for our std::vector<int> iterator. This compiles down to a tight loop of pointer increments and integer comparisons. On modern CPUs, the hardware prefetcher will detect this linear access pattern and pull data into the cache ahead of time, making this operation incredibly fast.

Searching for a specific value like 30 is easy. But what if we want to find "the first number greater than 100"? Or "the first Player object with 0 health"?

Many algorithms allow us to supply custom logic as arguments. Whilst std::find() asks us to provide the value we're searching for, such as 30, std::find_if() lets us provide a function instead.

Below, we define a function that accepts a Player as an argument, and returns true if the Player has low health. We then pass that function to std::find_if() to find the first player in the collection that meets that criteria.

As with the basic std::find(), it will return an iterator to that element, or an iterator equal to players.end() if the search failed:

1#include <algorithm>
2#include <vector>
3
4struct Player {
5  int health{100};
6  int id{0};
7};
8
9bool IsDamaged(const Player& p) {
10  return p.health < 100;
11}
12
13void FindPlayer(const std::vector<Player>& players) {
14  auto it = std::find_if(
15    // Range to search
16    players.begin(), players.end(),
17    
18    // Function defining the search criteria
19    IsDamaged
20  );
21  
22  if (it != data.end()) {
23    // Found one!
24  }
25}

This is a recurring pattern across standard library algorithms. They allow us to provide custom logic by passing functions. The algorithm will call those functions at the appropriate times as part of their process. They will typically provide some elements from our collection as arguments, and ask us to answer a specific question. For example:

• In the find_if() case, the algorithm asks "is this the item you're looking for?". If we return true, the algorithm will stop and return the iterator. If we return false, it will keep searching.
• An algorithm like std::copy_if() lets us copy some elements from one container to another. It will call our function to ask "should this element be included in the set that I copy?"
• In a sorting algorithm like std::sort(), our function will be called with two elements from our collection. The question we need to answer is "should the first argument be ordered before the second?"

Most of the time, our functions are being asked a yes/no question, so they return a bool. Functions that return a bool based on some test or condition applied to their arguments are usually called predicates.

Lambdas

Having an algorithm use a function that is defined elsewhere can be quite annoying. When we call an algorithm, we'd also like to see the logic we're using to control that algorithm without needing to scroll elsewhere in our file.

To help with this, C++11 introduced lambda expressions, which allow us to define anonymous functions directly inside the algorithm call:

1#include <vector>
2#include <algorithm>
3
4struct Player {
5  int health{100};
6  int id{0};
7};
8
9bool IsDamaged(const Player& p) {
10  return p.health < 100;
11}
12
13void FindPlayer(const std::vector<Player>& players) {
14  auto it = std::find_if(
15    players.begin(), players.end(),
16    IsDamaged
17    [](const Player& p) {
18      return p.health < 100;
19    }
20  );
21  
22  if (it != data.end()) {
23    // Found one!
24  }
25}

The syntax [](){} can be broken down into three parts:

1. [] Capture Clause: Defines what variables from the surrounding scope are available inside the lambda.
2. () Parameter List: The arguments the function accepts (just like a normal function).
3. {} Body: The code to execute.

Captures: Context Awareness

The capture clause [] is what makes lambdas powerful. Regular functions cannot see local variables from other functions. Lambdas can, if you ask them to.

Suppose we want to find a player with a specific ID, but that ID is stored in a local variable.

1void FindPlayer(const std::vector<Player>& players, int targetID) {
2  auto it = std::find_if(
3    players.begin(), players.end(),
4    [](const Player& p) {
5      // ERROR: targetID is not accessible inside the lambda
6      return p.id == targetID; 
7    }
8  );
9  
10  // ...
11}

To fix this, we "capture" targetID.

1// Capture 'targetID' by value (make a copy)
2[targetID](const Player& p) { return p.id == targetID; }
3
4// Capture ALL local variables our lambda uses by value
5[=](const Player& p) { return p.id == targetID; }
6
7// Capture ALL local variables our lambda uses by reference (avoids copying)
8[&](const Player& p) { return p.id == targetID; }

In most cases, our lambdas want to capture variables by reference, so we use &.

The Reality of Lambdas

When you write a lambda, the compiler actually generates a unique struct (or class) for you behind the scenes. That struct will overload the () operator, thereby letting its instances behave like functions.

If you capture targetID by value, the compiler adds a member variable int targetID to that struct. When you pass the lambda to std::find_if(), you are passing an instance of that struct.

Because this struct is a unique type, the compiler generates a unique version of std::find_if() specifically for it. This allows the compiler to inline your lambda code directly into the loop. This is why std::sort() with a lambda is often faster than C's qsort with a function pointer - the compiler can see through the abstraction and optimize the comparison away.

Some algorithms modify the data they traverse. The most famous of these is std::sort().

Sorting is one of the most expensive algorithms we use. It has an algorithmic complexity of $O(n \log n)$, but the relatively heavy nature of those operations makes it particularly taxing.

Here's a quick example of sorting a container using std::sort():

1std::vector<int> v{5, 1, 4, 2, 3};
2
3// Sorts in-place (ascending is default)
4std::sort(v.begin(), v.end());
5
6// We can provide a lambda to customize the search behavior
7// Our lambda should return true if a should be ordered before b
8// This call will sort elements in descending order
9std::sort(v.begin(), v.end(), [](int a, int b) {
10  return a > b;
11});

The std::sort() algorithm requires random access iterators. It works great on std::vector and std::array, but if you try to use it on a std::list (which only has bidirectional iterators), it will fail to compile.

Linked lists typically provide their own sorting implementations instead. This includes both std::forward_list and std::list, which provide .sort() methods.

Using std::transform()

This is the C++ equivalent of a "mapping" function. It takes a range of inputs, applies a function to each element, and writes the result to an output range. Our lambda is called for each element in the container, and the value we return from the lambda is saved to the destination.

Below, we populate output with the squared values of input:

1std::vector<int> input{1, 2, 3};
2
3// Important: Must allocate space first!
4std::vector<int> output(input.size()); 
5
6std::transform(
7  input.begin(), input.end(), // Input range
8  output.begin(),             // Output location
9  [](int i) { return i * i; } // Transformation
10);
11
12// output is now {1, 4, 9}

Notice the important comment in the previous example. If a standard library algorithm needs to "output" something other than simple result, we need to provide the memory. This includes algorithms like std::copy(), std::transform(), and std::fill(). They do not create memory - they overwrite memory.

We need to ensure the location we provide to the algorithm has enough space for what it's going to put there.

1std::vector<int> input{1, 2, 3};
2std::vector<int> output; // Empty! 
3
4// CRASH: transform tries to write to invalid memory
5std::transform(input.begin(), input.end(), output.begin(),
6  [](int i) { return i * i; }
7);

To solve this, we have two main options.

Option 1: Resize First

We can manually resize the destination to be large enough.

1std::vector<int> input{1, 2, 3};
2std::vector<int> output;
3
4// Allocate N default-constructed ints
5output.resize(input.size()); 
6
7std::transform(input.begin(), input.end(), output.begin(),
8  [](int i) { return i * i; }
9);

This is efficient because we perform one allocation. However, it requires us to default-construct objects that we are immediately going to overwrite, which can be wasteful if the objects are complex.

Option 2: std::back_inserter

The standard library provides a magical tool called an insert iterator. The std::back_inserter(container) helper returns a special iterator that, when you write to it, calls container.push_back(value). It turns assignment into insertion.

1#include <vector>
2#include <algorithm>
3#include <iterator> // Required for back_inserter
4
5int main() {
6  std::vector<int> input{1, 2, 3};
7  std::vector<int> output;
8  
9  // Safe! Automatically calls output.push_back() for each result
10  std::transform(
11    input.begin(), input.end(),
12    std::back_inserter(output),
13    [](int i) { return i * i; }
14  );
15}

While convenient, std::back_inserter can be slower than resize() because push_back() checks the vector's capacity on every insertion and may trigger multiple reallocations.

If we know how many elements the algorithm will write, or we have a reasonable upper bound, we can reserve() the memory first, then use back_inserter:

1#include <vector>
2#include <algorithm>
3#include <iterator>
4
5int main() {
6  std::vector<int> input{1, 2, 3};
7  std::vector<int> output;
8  
9  // Allocate memory, but size is still 0
10  output.reserve(input.size()); 
11  
12  std::transform(
13    input.begin(), input.end(),
14    std::back_inserter(output),
15    [](int i) { return i * i; }
16  );
17}

Suppose you want to remove all the number 3s from an array. You might find the std::remove() function:

1std::vector<int> v{1, 3, 2, 3, 4};
2std::remove(v.begin(), v.end(), 3);

If we examine the vector after this, we might expect {1, 2, 4}. Instead, we'll get something like {1, 2, 4, 3, 4}. The size of the vector has not changed.

This is a limitation of algorithms that work with iterators rather than directly with containers. The std::remove() function only sees begin() and end(). It does not have access to the std::vector object itself, so it physically cannot call v.erase() or change the size of the container. In fact, it doesn't even know that it's working on a std::vector - remember, the point of the iterator pattern is it allows us to be container-agnostic.

Instead, std::remove() does the best it can with its iterators. It shuffles the non-removed elements to the front of the range and returns an iterator to the "new logical end." The data after that iterator is garbage. But, most of the time, we still need to get rid of that garbage, so lets cover the two main ways.

The Old Fix: The Erase-Remove Idiom

To actually shrink the container after using remove(), we need to use container-specific approaches. In the case of std::vector, that is the erase() method. Below, we erase everything from what std::remove() returned to the current end() of the vector:

1auto new_end = std::remove(v.begin(), v.end(), 3);
2
3// Actually delete the garbage at the end
4v.erase(new_end, v.end());

This two-step dance is called the erase-remove idiom. It is efficient (only one pass to shift elements), but it is ugly and unintuitive.

1#include <vector>
2#include <algorithm>
3#include <iostream>
4
5int main() {
6  std::vector<int> v{1, 2, 3, 4, 5, 6};
7
8  // 1. Move valid elements to front
9  // Returns iterator to the first "garbage" element
10  auto new_logical_end = std::remove_if(v.begin(), v.end(),
11    [](int i) { return i % 2 == 0; } // Remove evens
12  );
13
14  // 2. Physically chop off the tail
15  v.erase(new_logical_end, v.end());
16
17  // v is now {1, 3, 5} (Size is 3)
18}

The New Fix: std::erase() and std::erase_if()

The C++ standards committee recognized that the erase-remove idiom was a significant usability hurdle for such a common task. In C++20, they introduced uniform container erasure functions to solve this.

Instead of the two-step shuffle, we now have std::erase() for removing specific values, and std::erase_if() for removing values based on a predicate.

1#include <vector>
2#include <iostream>
3
4int main() {
5  std::vector<int> v{1, 2, 3, 4, 5, 6, 6};
6  
7  // Remove all 6s
8  std::erase(v, 6);
9  
10  // v is now {1, 2, 3, 4, 5}
11
12  std::erase_if(v, [](int i) {
13    // Remove all evens
14    return i % 2 == 0;
15  });
16
17  // v is now {1, 3, 5}
18}

These functions are available for most standard containers (vector, list, string, map, etc.). They automatically select the most efficient way to remove elements for that specific container type, encapsulating the complexity so you don't have to manage it manually.

We finish this lesson with the biggest structural weakness of the standard library algorithms: they do not compose easily.

Suppose you want to perform a sequence of operations:

1. Filter a vector to keep only even numbers.
2. Transform those numbers by squaring them.
3. Take the first 5 results.

If we use only the tools we have covered in this lesson, things get ugly. The std::copy_if() algorithm writes to a destination. The std::transform() algorithm reads from a source. To connect them, you have to create intermediate storage:

1std::vector<int> input{
2  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
3};
4
5// Step 1: Filter into a temporary
6std::vector<int> temp1;
7temp1.reserve(input.size());
8std::copy_if(
9  input.begin(), input.end(),
10  std::back_inserter(temp1), IsEven
11);
12
13// Step 2: Transform into another temporary
14std::vector<int> temp2;
15temp2.reserve(temp1.size());
16std::transform(
17  temp1.begin(), temp1.end(),
18  std::back_inserter(temp2), Square
19);
20
21// Step 3: Iterate the first 5
22for (int i = 0; i < 5; ++i) { ... }

The multiple allocations makes this code less performant than it can be, and we're filtering and transforming the entire collection even though we're ultimately only interested in the first 5 elements.

If we needed to be efficient, we'd often revert back to raw, low-level loops with all their readability problems.

Ideally, we'd like to have a way to express ideas like "filter then transform then take 5" without the overhead of intermediate storage, or the verbosity of raw loops. We'll learn how to do this in the next lesson.

In this lesson, we started to replace our raw loops with the standard library toolkit. Here are the key takeaways:

1. Algorithms are Consumers: They take iterator pairs - begin(), end() - and process the range efficiently.
2. Standard Library Algorithms: The standard library includes a wide collection of algorithms that can solve most of our needs. Many of them allow or require us to provide additional logic.
3. Lambdas: We use [](){} syntax to write any custom logic the algorithms require.
4. Outputs: When an algorithm outputs data, we generally have to preallocate memory for that data. We can use std::back_inserter to grow containers safely.
5. Cleanups: We used std::erase_if() to neatly remove items from containers.

However, we ended on a sour note. We saw that combining these algorithms requires wasteful temporary memory allocations and unnecessary work, or the verbose syntax of raw loops.

In the next lesson, we will introduce C++20 Ranges. We will learn how to compose algorithms into lazy pipelines, allowing us to write input | filter | transform in a single, highly optimized pass.