The bridge between data layout and algorithms. Learn how iterators abstract memory traversal and the hierarchy of capabilities.

The Iterator Pattern

An introduction to the C++ Standard Library's algorithms, lambda expressions, and handling memory safely with insertion iterators.

Standard Library Algorithms

Learn how C++20 Ranges and Views allow us to compose safe, lazy-evaluated data pipelines without sacrificing performance.

C++20 Ranges

Learn how to build readable, lazy-evaluated data pipelines that execute in a single pass, and chain C++20 views together using the pipe operator `|`

View Composition and Pipes

Bridge the gap between iterators and views using `std::ranges::subrange` to turn any pair of iterators into a composable, safe C++20 View.

Subranges and Range Interoperability

TODO Iterators, Ranges, and Views

Understand how C++20 ranges reshape the standard library. Learn to combine algorithms and views for clean, efficient code.

If you're completely new to programming or want a thorough introduction, we recommend starting with our introductory course:

New to Programming?

Iterators, Ranges, and Views

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.


```c++
// The "Raw Loop" - The assembly language of logic
for (auto it = v.begin(); it != v.end(); ++it) {
  if (*it == target) {
    // ... logic ...
    break;
  }
}
```


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

## Algorithms as Consumers


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:


```c++
#include <vector>
#include <algorithm> // Required for std::find
#include <iostream>

int main() {
  std::vector<int> data{10, 20, 30, 40, 50};

  // Find the number 30
  auto it = std::find(data.begin(), data.end(), 30);

  // Check if we found it
  // Remember: end() is a sentinel. It means "Not Found".
  if (it != data.end()) {
    std::cout << "Found " << *it << " at index: "
              << std::distance(data.begin(), it) << "\n";
  }
}
```


```c++
//<o>
Found 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.


## Predicates and Lambdas


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:


```c++
#include <algorithm>
#include <vector>

struct Player {
  int health{100};
  int id{0};
};

bool IsDamaged(const Player& p) {
  return p.health < 100;
}

void FindPlayer(const std::vector<Player>& players) {
  auto it = std::find_if(
    // Range to search
    players.begin(), players.end(),
    
    // Function defining the search criteria
    IsDamaged//<h>
  );
  
  if (it != data.end()) {
    // Found one!
  }
}
```


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:


```c++
#include <vector>
#include <algorithm>

struct Player {
  int health{100};
  int id{0};
};

bool IsDamaged(const Player& p) {//<d>
  return p.health < 100;//<d>
}//<d>

void FindPlayer(const std::vector<Player>& players) {
  auto it = std::find_if(
    players.begin(), players.end(),
    IsDamaged//<d>
    [](const Player& p) {//<h>
      return p.health < 100;//<h>
    }//<h>
  );
  
  if (it != data.end()) {
    // Found one!
  }
}
```


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.


```c++
void FindPlayer(const std::vector<Player>& players, int targetID) {
  auto it = std::find_if(
    players.begin(), players.end(),
    [](const Player& p) {
      // ERROR: targetID is not accessible inside the lambda
      return p.id == targetID; //<e>
    }
  );
  
  // ...
}
```


To fix this, we "capture" `targetID`.


```c++
// Capture 'targetID' by value (make a copy)
[targetID](const Player& p) { return p.id == targetID; }

// Capture ALL local variables our lambda uses by value
[=](const Player& p) { return p.id == targetID; }

// Capture ALL local variables our lambda uses by reference (avoids copying)
[&](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.


## Modifying Algorithms


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()`:


```c++
std::vector<int> v{5, 1, 4, 2, 3};

// Sorts in-place (ascending is default)
std::sort(v.begin(), v.end());

// We can provide a lambda to customize the search behavior
// Our lambda should return true if a should be ordered before b
// This call will sort elements in descending order
std::sort(v.begin(), v.end(), [](int a, int b) {
  return a > b;
});
```


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`:


```c++
std::vector<int> input{1, 2, 3};

// Important: Must allocate space first!
std::vector<int> output(input.size()); //<h>

std::transform(
  input.begin(), input.end(), // Input range
  output.begin(),             // Output location
  [](int i) { return i * i; } // Transformation
);

// output is now {1, 4, 9}
```


## The Output Problem


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.


```c++
std::vector<int> input{1, 2, 3};
std::vector<int> output; // Empty! //<w>

// CRASH: transform tries to write to invalid memory
std::transform(input.begin(), input.end(), output.begin(),//<e>
  [](int i) { return i * i; }
);
```


To solve this, we have two main options.


### Option 1: Resize First


We can manually resize the destination to be large enough.


```c++
std::vector<int> input{1, 2, 3};
std::vector<int> output;

// Allocate N default-constructed ints
output.resize(input.size()); //<h>

std::transform(input.begin(), input.end(), output.begin(),
  [](int i) { return i * i; }
);
```


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.


```c++
#include <vector>
#include <algorithm>
#include <iterator> // Required for back_inserter

int main() {
  std::vector<int> input{1, 2, 3};
  std::vector<int> output;
  
  // Safe! Automatically calls output.push_back() for each result
  std::transform(
    input.begin(), input.end(),
    std::back_inserter(output),//<h>
    [](int i) { return i * i; }
  );
}
```


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`:


```c++
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
  std::vector<int> input{1, 2, 3};
  std::vector<int> output;
  
  // Allocate memory, but size is still 0
  output.reserve(input.size()); //<h>
  
  std::transform(
    input.begin(), input.end(),
    std::back_inserter(output),
    [](int i) { return i * i; }
  );
}
```


## Removing Elements


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


```c++
std::vector<int> v{1, 3, 2, 3, 4};
std::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:


```c++
auto new_end = std::remove(v.begin(), v.end(), 3);

// Actually delete the garbage at the end
v.erase(new_end, v.end());//<h>
```


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.


```c++
#include <vector>
#include <algorithm>
#include <iostream>

int main() {
  std::vector<int> v{1, 2, 3, 4, 5, 6};

  // 1. Move valid elements to front
  // Returns iterator to the first "garbage" element
  auto new_logical_end = std::remove_if(v.begin(), v.end(),
    [](int i) { return i % 2 == 0; } // Remove evens
  );

  // 2. Physically chop off the tail
  v.erase(new_logical_end, v.end());

  // v is now {1, 3, 5} (Size is 3)
}
```


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


```c++
#include <vector>
#include <iostream>

int main() {
  std::vector<int> v{1, 2, 3, 4, 5, 6, 6};
  
  // Remove all 6s
  std::erase(v, 6);
  
  // v is now {1, 2, 3, 4, 5}

  std::erase_if(v, [](int i) {
    // Remove all evens
    return i % 2 == 0;
  });

  // v is now {1, 3, 5}
}
```


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.


## The Composition Problem


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:


```c++
std::vector<int> input{
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
};

// Step 1: Filter into a temporary
std::vector<int> temp1;//<w>
temp1.reserve(input.size());
std::copy_if(
  input.begin(), input.end(),
  std::back_inserter(temp1), IsEven
);

// Step 2: Transform into another temporary
std::vector<int> temp2;//<w>
temp2.reserve(temp1.size());
std::transform(
  temp1.begin(), temp1.end(),
  std::back_inserter(temp2), Square
);

// Step 3: Iterate the first 5
for (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.


## Summary


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.

Lambdas

Function Objects (Functors)

Jonathan Boccara: 105 STL Algorithms in Less Than an Hour

Algorithms library

Effective STL

Replace error-prone for-loops with expressive standard algorithms. We cover the 'Big 4' algorithms, C++ lambda syntax and captures, and the hardware performance of std::sort vs qsort.

C++ Standard Algorithms: Lambdas, std::sort, and std::back_inserter

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

Standard Library Algorithms

Understanding the Basics

Practical Applications

Common Mistakes

Next Steps

Additional Resources

Assessment Preparation

Iterators, Ranges, and Views