This is the first article in a series discussing some of the underlying properties of C++ ranges and in particular range adaptors. At the same time, I introduce the design of an experimental library which aims to solve some of the problems discussed here.

Background

C++ Ranges are one of the major features of C++20. See my previous post for a detailed introduction. I am a big fan of C++ Ranges and have used them extensively in multiple projects (mostly bioinformatics, data science, …), but I have had difficulty convincing other people of the benefits and have seen many programmers struggle with even basic usage. Furthermore, there have been significant conceptual changes to the Ranges part of ISO standard after initial publication of C++20, showing the volatility of the design and making it even more difficult for non-expert users to understand what’s going on. Even now, there are still controversial discussions within the ISO C++ committee regarding vary basic aspects of C++ Ranges and views.

I see multiple challenges with the current design, that I group into the following three points:

  1. Fundamental range properties. What is a range? What is a view?
  2. Ranges and const.
  3. How adaptors capture the underlying range.

I will write a blog post on each of these points and try to address the problems by showing a different experimental library design. This is the first article in the series.

DISCLAIMER: I have been using Ranges since a long time and consider myself more knowledgeable than most C++ programmers in this area. However, I am also very aware that several people are into this topic a lot deeper than myself, and it is very possible that there are things I haven’t considered. I would further like to stress that I have the utmost respect for the work that was done to get the current state into the standard, and I do not criticise the committee for re-designing certain aspects of views. In fact, I have reversed my own position on several problems multiple times, and I am sure I wouldn’t have come to the conclusions drawn here without the previous iterations of the design.

Range concepts

A quick recap of the range concepts copied from a previous post.

Input ranges have different strengths that are realised through more refined concepts (i.e. types that model a stronger concept, always also model the weaker one):

Concept Description
std::ranges::input_range can be iterated from beginning to end at least once
std::ranges::forward_range can be iterated from beginning to end multiple times
std::ranges::bidirectional_range iterator can also move backwards with --
std::ranges::random_access_range you can jump to elements in constant-time []
std::ranges::contiguous_range elements are always stored consecutively in memory

These concepts are derived directly from the respective concepts on the iterators, i.e. if the iterator of a range models std::forward_iterator, than the range is a std::ranges::forward_range.

For the well-known containers from the standard library this matrix shows which concepts they model:

std::forward_list std::list std::deque std::vector
std::ranges::input_range ✅ ✅ ✅ ✅
std::ranges::forward_range ✅ ✅ ✅ ✅
std::ranges::bidirectional_range ✅ ✅ ✅
std::ranges::random_access_range ✅ ✅
std::ranges::contiguous_range ✅

The important distinction that this post discusses is between single-pass ranges (ranges that model input_range but not forward_range) and multi-pass ranges (those that model forward_range).

Multi-pass ranges | containers

Containers are the ranges everybody already used before Ranges were a thing. It is safe to assume that programmers will extrapolate from their experience with containers, even if they are made aware that containers are just a subset of Ranges in C++20 and beyond. Let’s have a look at what those assumptions might be.

Containers are forward ranges. This is the core property of being a “multi-pass range”, and among other things it guarantees that the iterator returned by begin() is copyable and that incrementing or dereferencing it does not change the container. But these are not the only guarantees with regard to mutability: calling .begin(), .end() and several other member functions is also guaranteed to not change the container.

Iterating over a string by random(?) access.

These properties are not surprising, I assume the mental model most people have for “iterator” in the context of containers is that of an observer object, like the glass that is moved over the letters of an Ouija Board if you are so inclined 🔮🧹🧙 In addition to regular iteration being non-modifying, containers also offer const-iterators through their .begin() const and .end() const members, i.e. they are const-iterable.

Containers are regular types. 1 A std::regular type is a type that is default-constructible, copyable and equality-comparable. None of this is surprising; as the name implies, these are properties most programmers assume by default. Although they are also obvious, it is important to point out the semantics of these operations here: default-constructed containers are empty, copying a container copies all elements, and equality-comparison compares all elements.

Multi-pass ranges | borrowed

Now it is important to point out, that not all multi-pass ranges are containers. An example of a type that is not a container is std::string_view. Under the hood, a std::string_view is just a pointer and a size. However, when using the data structure, the indirection is invisible and it behaves just like a shallow read-only container, in fact it is being advertised as a drop-in replacement for std::string const &. All the container properties discussed in the previous section are present in std::string_view; with the only difference being that copying happens in O(1) (because only the pointer and not the elements are copied).

C++

The string_view is to the string as the shadow is to the text above. The “contents” is the same, but the lifetime of one depends on the other.

While copy is in O(1), equality comparison is still in O(n), i.e. two string views are compared element-wise. This is a conscious design decision that mimics the behaviour of strings/containers. The other option would have been to define equality in terms of the pointer address and size. Some people will argue that this would be more “logical”, because the string_view is more like a pointer and pointers are also compared by their address and not by what they point at. But such a design would have rendered this statement false: std::string_view{"foo"} == std::string_view{"foo"} (because the two literals exist at different addresses), and I think nobody wants that.

Can we generalise what “non-container range” means? We can start by observing that std::string_view consists only of a pointer and a size—which is equivalent to storing two pointers or two iterators. And we also know that all of the semantics of the string_view are implemented in terms of these two elements! Ranges that can be expressed wholly in-terms of their iterators are borrowed ranges, described by the std::ranges::borrowed_range concept. However, we will see later that not all “non-container ranges” are borrowed ranges.

For now, appreciate how elegantly the properties of borrowed ranges can be deduced: They hold no state other than two iterators (or iterator+sentinel or iterator+size), and the iterators of forward ranges are required to be default-constructible and copyable, so the borrowed range is also default-constructible and copyable. In combination with element-wise comparison, this guarantees that ranges “borrowed from” a container can behave very similar to that container, i.e. they are also std::regular types! The only difference is O(1) copy, because there are just two iterators to copy (and copying them is independent of the size of the range).

Single-pass ranges

The next category of ranges is a completely different beast.

Summary

multi-pass ranges
containers		 multi-pass ranges
borrowed		 single-pass ranges
 
category forward_range or better forward_range or better input_range only
example std::vector<int> std::string_view std::generator<int>
iterating¹ w/o side-effects yes yes no
const-iterable yes yes no
default-constructible yes yes no
copyable yes ❘ O(n) yes ❘ O(1) no
equality-comparable yes ❘ O(n) yes ❘ O(n) no 
template <typename Range>
concept complete_forward_range = std::ranges::forward_range<Range> && std::ranges::forward_range<Range const> && std::regular<Range>;

Range adaptors in std::views::

Range adaptors in radr::

  1. Except std::array over an element type that is not regular. This is however not a useful type in the context of range adaptors any way. ↩︎