Ranges in C++20

In C++20, the range concept requires that an object has both an iterator, and an end sentinel. This is useful in the context of standard collections, in particular when developing algorithms (i.e. template functions) which operate on collections.

Motivation

Suppose we have a vector of values which we want to sort:

std::vector<int> values = {10, 20, 15, 35, 5};

We can use the std::sort() function as follows:

std::sort(values.begin(), values.end());

Note that you have to pass two arguments, namely the iterator values.begin() and the end sentinel values.end(). It would be nice if we could just pass the collection directly into the sort function.

In C++20, this is possible with the std::ranges namespace. So we can now write:

std::ranges::sort(values);

In order to make this possible, the ranges::sort() function needs to make use of template constrants, namely:

• the object has a begin() method which returns an iterator
• the object has an end() method which returns the end sentinel

Provided both these requirements are satisfied, the algorithm will work and the implementation doesn’t need to know if the actual collection is a vector, list or whatever.

These requirements are formalised by the std::ranges::range concept, which is defined in the C++20 ranges library. Recall that we introduced concepts in this previous post.

Using the ranges concept in template functions

Let’s look at how we would use the range concept to develop our own algorithm:

#include <ranges>

template <typename T> 
requires std::ranges::range<T>
void mySort(T x)
{
    // For demonstration, we'll just wrap the old STL algorithm.
    std::sort(x.begin(), x.end());
}

we can then just call the mySort() function with a single argument:

mySort(values);

Projections

Let’s consider now the problem of sorting an array of objects. Consider the following class to represent student exam results:

class Result
{
public:
    int studentId;
    int score;
};

We can’t simply call std::ranges::sort() as the Result class does not define the < operator. Furthermore, we need to tell the sort function whether we want to sort by studentId or score.

The new std::ranges library allows us to specify a custom comparator as an optional second parameter, e.g.

std::ranges::sort(results,
  [](const Result& x, const Result& y){return x.score < y.score;});

In C++20, we can simplify further by making use of the fact that the std::ranges::sort() function supports projections. This allows us to specify a unary function with which to transform each element of the collection:

std::ranges::sort(
  results, 
  std::ranges::less{},
    [](const Result& x){return x.score;});

The third argument here is our projection which transforms each Result object into its integer valuescore.

We need to supply a comparator in the second argument, but since we have ‘projected’ the elements into integers, we can employ the built-in std::ranges::less comparator.

Even better, since the default template type for the projection is std::ranges::less, we can write {} for the third argument to indicate that we want to use the default constructor. So our code becomes:

std::ranges::sort(
    results, {},
    [](const Result& x){return x.score;});

We can simplify further using the ‘pointer-to-member’ syntax:

std::ranges::sort(results, {},
    &Result::score);

Views

Views are range adaptors. So we can filter elements in a range, or apply a transformation to each element. All of this happens without needing to allocate any new objects or copy collections. The result of a view is itself a range, so views can be chained together or subsequently passed into any of the algorithm in the ranges library.

For example, if we have a vector vec, we can drop the first element of a range:

std::views::drop(vec, 1);

We can reverse the elements:

std::views::reverse(vec);

We can chain together range adaptors using the pipe symbol:

vec | std::views::reverse | std::views::drop(1);

We can use a filter to select only the even elements:

vec | std::views::filter(
    [](auto i) { return 0 == i % 2; });

The great feature of views is that they allow for lazy evaluation.

Conclusion

Ranges provide much-needed functionality for dealing with collections. They bring significant improvements for syntax and readability. Ranges are a great example of C++20 concepts in action.