C++ Ranges

C++ Ranges

What is a range?

A range is a programmatic abstraction for a sequence of elements, bounded by two iterators(one to the first element of the sequence and one to the last element).

Containers such as std::vector, std::list and std::map are concrete implementations of the range abstraction. The standard algorithms are generic. They are container agnostic. They know nothing about std::vector, std::map or std::list. They handle range abstractions with the help of a pair of iterators. However, this has a shortcoming: we always need a begin() and end() iterator from a container. Here are some examples:

// sort a vector
std::vector v{1, 2, 3, 4, 5};
std::sort(v.begin(), v.end());

// count the even numbers of an array
std::array<int, 5>a{1, 5, 3, 2, 4};
auto even_count = std::count_if(
    a.begin(),
    a.end(),
    [](int const n){ return n % 2 == 0; }
);

There are few cases when we only need to process a part of the container’s elements. In the vast majority of the cases, we need to write v.begin() and v.end() over and over again. Ideally, we would prefer to shorten all this and be able to write the following:

// sort a vector
std::vector v{1, 2, 3, 4, 5};
std::sort(v.begin(), v.end());

// count the even numbers of an array
std::array<int, 5>a{1, 5, 3, 2, 4};
auto even_count = std::count_if(
    a.begin(),
    a.end(),
    [](int const n){ return n % 2 == 0; }
);

On the other hand, we often need to compose multiple operations together. Most of the time that involves many operations and code that is too verbose even when using standard algorithms. Consider the following example: given a sequence of integers, we want to print to the console the square of all even numbers, except the first two, in descending order of their value (not their position in the sequence). There are multiple ways to solve this problem. Here is one possible solution:

std::vector<int> v{1, 5, 3, 2, 8, 7, 6, 4};

// copy only the even elements
std::vector<int> temp;
std::copy_if(v.begin(), v.end(), std::back_inserter(temp), [](int n){
    return n % 2 == 0;
});

// sort the elements
std::sort(temp.begin(), temp.end(), [](int a, int b){ return a > b; });

// remove the first two
temp.erase(temp.begin() + temp.size() - 2, temp.end());

// transform the elements
std::transform(temp.begin(), temp.end(), [](int const n){ return n*n; });

// print each element
std::for_each(temp.begin(), temp.end(), [](int n){ std::println("{}, n"); });

While anyone familiar with standard algorithms can read this code, there are several downsides. Its a lot of code to write and also requires a temporary container with repetitive calls to begin() and end(). All of the computation is done eagerly, so the intermediate results of each step are held in memory.

Most people would easily understand the following version of the previous code and also prefer to write it as such:

std::vector<int> v{1, 5, 3, 2, 8, 7, 6, 4};

using std::ranges = stdr;
using std::ranges::views = stdv;

stdr::sort(v);

auto r = v  | filter([](int n) { return n % 2 == 0; })
            | drop(2)
            | reverse
            | transform([](int n){ return n*n; });

This is what the C++20 standard provides with the help of the ranges library. This has two main components:

• Range algorithms, which enable us to operate on concrete ranges (standard containers or ranges) and not on abstract ranges delimited by a pair of iterators
• Views or range adapters, which represent non-owning iterable sequences. They enable us to compose operations more easily such as in the last example.

Understanding range concepts and views

The term range refers to an abstraction that defines a sequence of elements bounded by start and end iterators. A range, therefore, represents an iterable sequence of elements. However, such a sequence can be defined in several ways:

• With a begin iterator and an end sentinel. Such a sequence is iterated from beginning to the end. A sentinel is an object that indicates the end of the sequence. It can have the same type as the iuterator type or it can be of a differnt type.
• With a start object and a size(number of elements), representing a so-called counted sequence. Such a sequence is iterated \(N\) times (where $N represents the size) from the start.
• With a start and a predicate, representing a so-called conditionally termninated sequence. Such a sequence is iterated from the start until the predicate returns false.
• With only a start value, representing a so-called unbounded sequence. Such a sequence can be iterated indefinitely.

All these kinds of iterable sequences are considered ranges. Because a range is an abstraction, the C++20 library defines a series a of concepts to describe the requirements for range types. These are available in the <ranges> header and the std::ranges namespace. The following table presents a list of range concepts:

Name	Description
range	Defines the requires for a type R to be a range by provdiding a begin iterator and an end sentinel. The iterator and the sentinel can be of different types.
borrowed_range	Defines the requirements for a type R so that a function can take an object of this type by value and return iterators obtained from this object without the danger of dangling.
sized_range	Defines the requirements for a type R to be a range that knows its size in constant time.
common_range	Defines the requirements for a type R to be a range whose iterator and sentinel types are equal.
view	Defines the requirements of type R that is a range to have constant-time, copy, move and assignment opertions.
viewable_range	Defines the requirements for a range type R to be convertible to a view.

Other range concepts such as input_range, output_range, forward_range, bidirectional_range, random_access_range, contiguous_range are modeled after the corresponding iterator concepts.

A view is a lightweight object that applies the transformation only when a new element is requested(iterated) and not hen the view is created. Its key feature is lazy evaluation. It is like a stream. So, views are lightweight objects, with non-owning semantics. They don’t own the underlying data.

There is a series of views provided with C++20 and new views have also been included in C++23. Views are available by including the <ranges> header under the std::ranges namespace, for example, std::ranges::iota_view.

The iota view is part of a special category of views called factories. These factories are views over newly generated ranges. The following factories are available in the ranges library:

Type	Variable	Description
ranges::empty_view	ranges::views::empty	Generates a view with no elements of T type
ranges::single_view	ranges::views::single	Generates a view with a single element of a T type
ranges::iota_view	ranges::views::iota	Generates a view of a sequence of consecutive elements, from a start value to an end value (a bounded view) or indefinitely (an unbounded view)
ranges::basic_iostream_view	ranges::views::istream	Generates a view of the sequence of elements by applying the operator >> repeatedly

Here is a quick example for using iota:

// using iota_view
namespace stdr = std::ranges;
namespace stdv = std::views;

for(auto i : stdr::iota_view(1,10))
    std::print("{}, ", i);

// using stdv::iota
for(auto i : stdv::iota(1,10))
    std::print("{}, ", i);

If you are wondering why empty_view and single_view are useful, the answer should not be hard to find. These are useful in template code that handles ranges where empty ranges or ranges with one element are valid inputs. you don’t want multiple overloads of a function template for handling these special cases; instead, you can pass an empty_view or single_view range. The following snippets show several examples of using these factories.

#include <print>
#include <ranges>

// namespace alias
namespace stdr = std::ranges;
namespace stdv = std::views;

int main()
{
    constexpr stdr::empty_view<int> ev;
    static_assert(stdr::empty(ev));
    static_assert(stdr::size(ev) == 0);
    static_assert(stdr::data(ev) == nullptr);

    constexpr stdr::single_view<int> sv{42};
    static_assert(!stdr::empty(sv));
    static_assert(stdr::size(sv) == 1);
    static_assert(*stdr::data(sv) == 42);
    return 0;
}

Compiler Explorer

For the iota_view, we have already seen a couple of examples with a bounded view. The next snippet shows again an example not only using a bounded view generated with iota but also an unbounded view, also generated with iota:

#include <print>
#include <ranges>
#include <algorithm>

namespace stdr = std::ranges;
namespace stdv = std::views;

int main(){
    auto v1 = stdv::iota(1,10);
    stdr::for_each(v1,[](int n){
        std::println("{}", n);
    });

    auto v2 =   stdv::iota(1)
                | stdv::take(9);

    stdr::for_each(v2,[](int n){
        std::println("{}", n);
    });                
    return 0;
}

Compiler Explorer

The last example utilizes another view called take_view. This produces a view of the first \(N\) elements (in my example \(9\)) of another view (in my example, the unbounded view produced by iota). I will discuss more on this shortly.

There are other standard views that I implore you to check out on cppreference.com. I tried out a few toy examples below:

#include <iostream>
#include <print>
#include <ranges>
#include <vector>
#include <algorithm>
#include <string_view>
#include <iomanip>
#include <tuple>

namespace stdr = std::ranges;
namespace stdv = std::views;

void print(auto data, std::string_view label){
    std::cout << "\n" << label << ": ";
    stdr::for_each(data,[](int n){
        std::print("{}, ", n);
    });
}

int main(){
    auto data = stdr::iota_view(1,9);

    // filter_view 
    // Only include elements satisfying a predicate
    auto filter_data = data | stdv::filter([](int n){
        return n % 3 == 0;
    });
    print(filter_data, "filter");

    // transform_view
    // Applies a mapping element-wise
    auto squares = data | stdv::transform([](int n){
        return n * n;
    });
    print(squares, "squares");

    // take_view
    // Grab the first N elements
    auto first_ten = data | stdv::take(10);
    print(first_ten, "first_ten");

    // take_while_view
    // Grab all elements starting with the first
    // until an element is found that no longer 
    // satisfies the predicate
    auto take_while_rslt = data | stdv::take_while([](int n){
        return n <= 5;
    });
    print(take_while_rslt, "take_while_rslt");

    // drop_view 
    // skip the first N elements
    auto drop_rslt = data | stdv::drop(3);
    print(drop_rslt, "drop_rslt");

    // drop_while_view
    // skip elements until predicate is not met
    auto drop_while_rslt = data | stdv::drop_while([](int n){
        return n <= 3;
    });
    print(drop_while_rslt, "drop_while_rslt");

    // join_view
    // Provides a view of a sequence generated by
    // flattening multiple ranges
    using namespace std::literals;
    auto strings = {
        "C++ "sv, "is "sv, "a "sv, "general-purpose "sv,
        "and "sv, "multi-paradigm "sv, "programming "sv,
        "language"sv
        };
    auto join_result = stdv::join(strings);
    std::cout << "\n" << "join_result: ";
    for(const char c: join_result)
        std::cout << c;

    // join_with_view
    // Provides a view of a sequence generated by 
    // flattening multiple ranges with a delimiter 
    // inserted between the elements of the view.
    std::vector<std::vector<int>> rngs = {{1,2},{3,4},{5,6}};
    auto join_with_rslt = rngs | stdv::join_with(',');
    
    // split_view
    // Provides view of a sequence of ranges produced
    // by splitting a range on a specified delimiter.
    constexpr auto words{"Hey,^_^C++^_^23^_^ranges^_^are^_^awesome!"sv};
    constexpr auto delim{"^_^"sv};
    auto split_rslt = words | stdv::split(delim);

    // reverse_view
    // Provides a view of the elements of the 
    // underlying range in reverse order
    auto reverse_rslt = stdv::reverse(data);
    print(reverse_rslt, "reverse_rslt");

    // keys_view, values_view and elements_view 
    // Provide a view by projecting the first, 
    // second and nth element respectively
    // from a range of tuples.
    const std::vector<std::tuple<std::string, double, bool>> quark_mass_charge
    {
        // name, MeV/c², has positive electric-charge:
        {"up", 2.3, true}, {"down", 4.8, false},
        {"charm", 1275, true}, {"strange", 95, false},
        {"top", 173'210, true}, {"bottom", 4'180, false},
    };

    std::cout << "\nQuark name:  | ";
    auto names = stdv::keys(quark_mass_charge);
    for(auto name : names)
        std::cout << std::setw(9) << name << "|";

    std::cout << "\nMass:        | ";    
    auto masses = stdv::values(quark_mass_charge);
    for(auto mass : masses)
        std::cout << std::setw(9) << mass << "|";

    std::cout << "\nCharge:      | ";    
    auto charges = stdv::elements<2>(quark_mass_charge);
    for(auto charge : charges)
        std::cout << std::setw(9) << charge << "|";        

    // zip_view
    // Create a view of tuples from the elements
    // of an array of integers and a vector of
    // doubles
    std::array<int, 4> a{1, 2, 3, 4};
    std::vector<double> v{10.0, 20.0, 30.0};
    std::cout << "\nzip_result: ";
    for(auto z : stdv::zip(a, v))
        std::print("{} ", z);

    // zip_transform 
    // Create a view with the multiplied elements
    // of an array of integers and vector of doubles
    std::cout << "\nzip_transform_result: ";
    for(auto z : stdv::zip_transform(
        std::multiplies<double>(), a, v
    ))
        std::print("{} ", z);

    // adjacent_view
    // Print the pairs of adjacent elements of a
    // sequence of integers
    std::cout << "\nadjacent_result: ";
    for(auto i : v | stdv::adjacent<3>)
        std::print("{} ", i);

    return 0;
}

Compiler Explorer

Understanding the constrained algorithms

The standard library provides over a hundred general-purpose algorithms. Most of these algorithms have a new constrained version in std::ranges namespace. These algorithms are found in the <algorithm>, <numeric> and <memory> header.

• They have the same name as the existing algorithms.
• They have overloads that allow you to specify a range, either with a begin iterator and an end sentinel, or as a single range argument.
• They have modified return types that provide more information about the execution.
• They support projections to apply to the processed elements. A projection is an entity that can be invoked. It can be a pointer to a member function, a lambda expression, or a function pointer. Such a projection is applied to the range element before the algorithm logic uses the element.

From cppreference.com, the rangified version of the copy_if algorithm has the following overloads:

template< std::input_iterator I, std::sentinel_for<I> S, std::weakly_incrementable O,
          class Proj = std::identity,
          std::indirect_unary_predicate<std::projected<I, Proj>> Pred >
requires std::indirectly_copyable<I, O>
constexpr copy_if_result<I, O>
    copy_if( I first, S last, O result, Pred pred, Proj proj = {} );

template< ranges::input_range R, std::weakly_incrementable O,
          class Proj = std::identity,
          std::indirect_unary_predicate<
              std::projected<ranges::iterator_t<R>, Proj>> Pred >
requires std::indirectly_copyable<ranges::iterator_t<R>, O>
constexpr copy_if_result<ranges::borrowed_iterator_t<R>, O>
    copy_if( R&& r, O result, Pred pred, Proj proj = {} );

The signatures may look cryptic, but it’s easy to code up a few quick examples.

#include <iostream>
#include <ranges>
#include <algorithm>
#include <vector>

namespace stdr = std::ranges;
namespace stdv = std::ranges::views;

int main()
{
    std::vector<int> v{1, 1, 2, 3, 5, 8, 13};
    std::vector<int> o;

    auto filter_odd = [](int n){ return n % 2 == 1; };
    auto e1 = stdr::copy_if(v, std::back_inserter(o), filter_odd);

    int arr[] = {1, 1, 2, 3, 5, 8, 13 };
    auto e2 = stdr::copy_if(arr,
        std::back_inserter(o), filter_odd
    );

    auto rng = stdr::iota_view(1,10);
    auto e3 = stdr::copy_if(r, std::back_inserter(o), filter_odd);
    return 0;
}

Compiler Explorer

These examples show two things: how to copy elements from a std::vector object and an array and how to copy elements from a view(a range adaptor). What they don’t show is projections. I’ll explore some examples on this shortly.

Other constrained algorithms like all_of, any_of, none_of, find, find_if, copy, copy_if, move, copy_backward, move_backward, fill, fill_n, transform, sample, fold_left, fold_right are very useful in coding.

A projection is an invocable entity. It’s basically a function adaptor. It affects the predicate, providing a way to perform function composition. It does not provide a way to change the algorithm. For instance, let’s say we have the following type:

Let’s say we have the following type:

struct Point{
    double x;
    double y;
};

Also, for the purpose of the explanation, let’s consider the following sequence of points:

std::vector<Point> points{
    {1.0, 1.0},
    {-1.0, 1.0},
    {1.0, -1.0},
    {-1.0, -1.0}
}

Projects allow us to perform composition on the predicate. For instance, let’s say we want to copy to a second vector all points below the \(x\)-axis (having a negative \(y\)-coordinate). We can code up the following:

std::vector<Point> points_below_x_axis;
stdr::copy_if(points,
    std::back_inserter(points_below_x_axis),
    [](const Point& point){
        return point.x < 0;
    }
);

However, we can also write equivalently:

std::vector<Point> points_below_x_axis;
stdr::copy_if(points,
    std::back_inserter(points_below_x_axis),
    [](const Point& point){
        return x < 0;
    },
    &Point::x
);

The projection, in this example, is the pointer-to-member expression &Point::x that is applied to each Point element before executing the predicate (which is a lambda expression). This is useful when already have reusable function objects/lambda expressions and you don’t want to write another one for passing different types.

Writing your own range adaptor

The standard library contains a series of range adaptors that can be used for solving many different tasks. However, there are situations where we’d like to write our own custom randge adaptor.

References

• Ranges and Iterators for numerical Problems, Karsten Ahnert at Meeting C++ 2014
• What is a range in C++, Simon Toth, C++ on the Sea, 2024
• A beginner’s guide to C++ Ranges and Views, Hannes Hauswedell
• C++ Code Samples Before and After Ranges, Marius Bancila