Iterator and Range-Based Algorithms

In earlier lessons, we saw how we could standardize traversal through potentially any type of container by using iterators or ranges.

Having done that, we gain the benefit of being able to use or create algorithms that work across any of those containers.

The standard library’s <algorithm> header includes over a hundred generally useful algorithms that are based upon iterators and ranges.

Example: Sorting Using Iterators

Once we’ve included the <algorithm> header, we can pass an iterator pair to std::sort(). The algorithm will traverse between those two iterators, putting all of the elements in order:

1#include <vector>
2#include <iostream>
3#include <algorithm>
4
5int main() {
6  std::vector Numbers { 3, 1, 2 };
7  std::sort(Numbers.begin(), Numbers.end());
8  for (auto Num : Numbers) {
9    std::cout << Num << ", ";
10  }
11}

11, 2, 3,

Example: Sorting Using Ranges

Almost all of the iterator-based algorithms in the standard library have a variation that works with ranges. These are available within the std::ranges namespace. For example, the range-based variation of std::sort() is std::ranges::sort().

Rather than an iterator pair, we can call it with a single argument - the range we want to run the algorithm on:

1#include <vector>
2#include <iostream>
3#include <algorithm>
4
5int main() {
6  std::vector Numbers { 3, 1, 2 };
7  std::ranges::sort(Numbers);
8  for (auto Num : Numbers) {
9    std::cout << Num << ", ";
10  }
11}

11, 2, 3,

Applying an Algorithm to a Subrange

Our previous examples sorted our entire container, but we can apply an algorithm to only part of a container.

With iterator-based algorithms, we can do this by passing different iterators as arguments. Below, we sort the middle three elements of our container:

1#include <vector>
2#include <iostream>
3#include <algorithm>
4
5int main() {
6  std::vector Numbers { 3, 5, 1, 2, 4 };
7
8  std::sort(
9    std::next(Numbers.begin(), 1),
10    std::prev(Numbers.end(), 1)
11  );
12
13  for (auto Num : Numbers) {
14    std::cout << Num << ", ";
15  }
16}

13, 1, 2, 5, 4,

We can do the same thing using the overload of range-based algorithms by defining the range using an iterator and a sentinel. In this case, the sentinel is another iterator but, as we covered in the previous lesson, it doesn’t need to be:

1#include <vector>
2#include <iostream>
3#include <algorithm>
4
5int main() {
6  std::vector Numbers { 3, 5, 1, 2, 4 };
7
8  std::ranges::sort(
9    std::next(Numbers.begin(), 1),
10    std::prev(Numbers.end(), 1)
11  );
12
13  for (auto Num : Numbers) {
14    std::cout << Num << ", ";
15  }
16}

13, 1, 2, 5, 4,

Defining Ranges using Sentinels

An alternative way of defining ranges, and why we sometimes need to use them

There are many more ways of generating subranges from a range, which we’ll explore through the rest of this chapter.

Algorithm Container Requirements

Fixing "the constraint was not satisfied" errors

As we covered earlier in the chapter, not all ranges and iterators have the same capabilities. For example, some ranges might support random access, whilst others may only support forward access.

Many algorithms have specific requirements for the ranges and iterators passed to them.

For example, the std::ranges::sort() or std::sort() algorithms require our range or iterators to support random access.

Therefore, it cannot be run on a container such as a linked list:

1#include <forward_list>
2#include <algorithm>
3
4int main() {
5  std::forward_list Numbers { 3, 1, 2 };
6  std::ranges::sort(Numbers);
7}

We can check the requirements of any algorithm from the documentation.

We may often also get useful error messages from the compiler if our container does not meet the requirements.

Below, we see std::ranges::sort() requires the std::ranges::random_access_range concept to be satisfied, but std::forward_list does not meet the requirements:

1error: the concept 'std::ranges::random_access_range<std::forward_list<int>>' evaluated to false - the constraint was not satisfied

1#include <algorithm>
2#include <forward_list>
3#include <iostream>
4
5int main() {
6  std::forward_list Numbers{3, 1, 2, 5, 4};
7  Numbers.sort();
8
9  for (auto Num : Numbers) {
10    std::cout << Num << ", ";
11  }
12}

11, 2, 3, 4, 5,

Algorithm Element Requirements

Beyond container requirements, algorithms may additionally have expectations of the type of objects stored within our container.

For example, using std::ranges::sort() or std::sort() on a collection only makes sense when the type of data within that collection is orderable.

If we create an arbitrary type, and attempt to sort a container of them, the algorithm is not going to know how to do it:

1#include <vector>
2#include <algorithm>
3
4struct SomeType {
5  SomeType(int x) : Value{x} {}
6  int Value;
7};
8
9int main() {
10  std::vector<SomeType> Numbers { 3, 1, 2 };
11  std::ranges::sort(Numbers);
12}

1the associated constraints are not satisfied
2the concept 'std::sortable' evaluated to false

We cover ordering in more detail in a later chapter, but we can make a type compatible with std::sort() by implementing the == and <=> operators:

1#include <vector>
2#include <algorithm>
3#include <iostream>
4
5struct SomeType {
6  SomeType(int x) : Value{x} {}
7  auto operator<=>(const SomeType& Other) const {
8    return Value <=> Other.Value;
9  }
10  bool operator==(const SomeType& Other) const {
11    return Value == Other.Value;
12  }
13
14  int Value;
15};
16
17int main() {
18  std::vector<SomeType> Container{3, 1, 2};
19  std::ranges::sort(Container);
20
21  for (SomeType& Object : Container) {
22    std::cout << Object.Value << ", ";
23  }
24}

11, 2, 3,

The Spaceship Operator and Expression Rewriting

A guide to simplifying our comparison operators using C++20 features

Other algorithms may have different requirements. Some algorithms might require our type to be default constructible or to implement an assignment operator for example.

Algorithm Preconditions

The final requirement that is worth considering is whether or not the algorithm we’re using makes any assumptions that are not enforced by the compiler.

For example, binary search is a very efficient algorithm for finding objects in a container, but it relies on the container being sorted.

As such, the standard library’s implementation of binary search - std::binary_search has that same assumption.

When reading documentation, we must check for these types of requirements carefully, because they’re very difficult to enforce automatically. Instead of a compiler error, we’ll typically just get incorrect behaviors at run time instead.

Below, we use binary search on a container that isn’t sorted, causing our program to have an incorrect output:

1#include <vector>
2#include <algorithm>
3#include <iostream>
4
5int main() {
6  std::vector Container{3, 1, 4, 5, 2};
7
8  bool Found{
9    std::ranges::binary_search(Container, 2)};
10
11  if (!Found) {
12    std::cout << "The container doesn't have 2";
13  }
14}

1The container doesn't have 2

Algorithm Customisations

Depending on the algorithm we’re using, we can often pass additional arguments to customise the behavior.

For example, most range-based algorithms allow us to modify their behavior by providing an additional projection function, which we cover in detail in the next lesson.

Other algorithms, such as std::sort and std::ranges::sort may offer additional parameters specific to their use case.

Example: Customizing the Sort Behaviour of std::sort()

By default, the std::sort() and std::ranges::sort() algorithms use our type’s < operator to determine the ordering. That is, if A < B, then A should come before B after the algorithm completes.

However, these algorithms have overloads that allow us to provide a different comparison function as an additional argument.

This function is going to receive two objects from our collection and should return true if the first object should come before the second object.

Previously, our vector of numbers was arranged in ascending order. Let's provide a lambda that will instead cause the algorithm to sort the objects in descending order:

1#include <vector>
2#include <algorithm>
3#include <iostream>
4
5int main() {
6  std::vector Container{3, 1, 4, 5, 2};
7
8  std::ranges::sort(Container, [](int a, int b) {
9    return a > b;
10  });
11
12  for (int x : Container) {
13    std::cout << x << ", ";
14  }
15}

15, 4, 3, 2, 1,

1[](int a, int b){
2  return a > b;
3}

1std::ranges::sort(Nums, std::ranges::greater{});

With the ability to pass a custom comparison function, we can now sort items of any type, in any order we desire. Let's sort a party of players by their level:

1#include <vector>
2#include <iostream>
3#include <algorithm>
4
5struct Player {
6  std::string Name;
7  int Level;
8};
9
10int main() {
11  std::vector Party {
12    Player {"Legolas", 49},
13    Player {"Gimli", 47},
14    Player {"Gandalf", 53}
15  };
16
17  std::ranges::sort(Party,
18    [](Player& a, Player& b){
19      return a.Level > b.Level;
20    }
21  );
22
23  for (const auto& Player : Party) {
24    std::cout << "[" << Player.Level << "] "
25              << Player.Name << "\n";
26  }
27}

1[53] Gandalf
2[49] Legolas
3[47] Gimli

Summary

In this lesson, we introduced the idea of iterator and range-based algorithms. We learned how these concepts enable standardized traversal and manipulation of data across various container types.

Key Learnings

• The use of iterators and ranges for standardized container traversal.
• Implementing std::sort() with iterator pairs to order elements.
• Utilizing std::ranges::sort() for range-based sorting.
• Applying algorithms to subranges using both iterator-based and range-based methods.
• Understanding container requirements for different algorithms, like the need for random access in std::sort().
• Workarounds for performing tasks on non-compatible containers, such as using std::forward_list's native sort() method to sort a linked list.
• Algorithms may have additional requirements of the type stored within the containers - for example, sort algorithms only work on containers of types that can be ordered.
• The importance of algorithm preconditions, illustrated with std::binary_search.
• Customizing algorithms' behavior using additional arguments, like a custom comparison function in sorting.
• Utilization of standard library comparison functors for common operations.
• Sorting items of any type and order using custom comparison functions in algorithms.

Next Lesson

Projection Functions

Learn to use projection functions to apply range-based algorithms on derived data

ContinueView Course