Making Your Own Container Compatible With C++20

Making Your Own Container Compatible With C++20 Ranges

March 20, 2021 · Coding · 0 Comments

With some of my spare time lately, I’ve been enjoying learning about some of the new features in C++20. Concepts and the closely-related requires clauses are two great extensions to template syntax that remove the necessity for all the SFINAE junk we used to have to do, making our code both more readable and more precise, and providing much better error messages (although MSVC has sadly been lagging in the error messages department, at the time of this writing).

Another interesting C++20 feature is the addition of the ranges library (also ranges algorithms), which provides a nicer, more composable abstraction for operating on containers and sequences of objects. At the most basic level, a range wraps an iterator begin/end pair, but there’s much more to it than that. This article isn’t going to be a tutorial on ranges, but here’s a talk to watch if you want to see more of what it’s all about.

What I’m going to discuss today is the process of adding “ranges compatibility” to your own container class. Many of the C++ codebases we work in have their own set of container classes beyond the STL ones, for a variety of reasons—better performance, more control over memory layouts, more customized interfaces, and so on. With a little work, it’s possible to make your custom containers also function as ranges and interoperate with the C++20 ranges library. Here’s how to do it.

    Making Your Container an Input Range
        Range Concepts
        Defining Range-Compatible Iterators
        Begin, End, Size
    Accepting Output From Ranges
        Constructor From A Range
        Output Iterators
    Conclusion

Making Your Container an Input Range

At the high level, there are two basic ways that a container class can interact with ranges. First, it can be readable as a range, meaning that we can iterate over it, pipe it into views and pass it to range algorithms, and so forth. In the parlance of the ranges library, this is known as being an input range: a range that can provide input to other things.

The other direction is to accept output from ranges, storing the output into your container. We’ll do that later. To begin with, let’s see how to make your container act as an input range.
Range Concepts

The first decision we have to make is what particular kind of input range we can model. The C++20 STL defines a number of different concepts for ranges, depending on the capabilities of their iterators and other things. Several of these form a hierarchy from more general to more specific kinds of ranges with tighter requirements. Generally speaking, it’s best for your container to implement the most specific range concept it’s able to. This enables code that works with ranges to make better decisions and use more optimal code paths. (We’ll see some examples of this in a minute.)

The relevant input range concepts are:

    std::ranges::input_range: the most bare-bones version. It requires only that you have iterators that can retrieve the contents of the range. In particular, it doesn’t require that the range can be iterated more than once: iterators are not required to be copyable, and begin/end are not required to give you the iterators more than once. This could be an appropriate concept for ranges that are actually generating their contents as the result of some algorithm that’s not easily/cheaply repeatable, or receiving data from a network connection or suchlike.
    std::ranges::forward_range: the range can be iterated as many times as you like, but only in the forward direction. Iterators can be copied and saved off to later resume iteration from an earlier point, for example.
    std::ranges::bidirectional_range: iterators can be decremented as well as incremented.
    std::ranges::random_access_range: you can efficiently do arithmetic on iterators—you can offset them forward or backward by a given number of steps, or subtract them to find the number of steps between.
    std::ranges::contiguous_range: the elements are actually stored as a contiguous array in memory; the iterators are essentially fancy pointers (or literally are just pointers).

In addition to this hierarchy of input range concepts, there are a couple of other standalone ones worth mentioning:

    std::ranges::sized_range: you can efficiently get the size of the range, i.e. how many elements from begin to end. Note that this is a much looser constraint than random_access_range: the latter requires you be able to efficiently measure the distance between any pair of iterators inside the range, while sized_range only requires that the size of the whole range is known.
    std::ranges::borrowed_range: indicates that a range doesn’t own its data, i.e. it’s referencing (“borrowing”) data that lives somewhere else. This can be useful because it allows references/iterators into the data to survive beyond the lifetime of the range object itself.

The reason all these concepts are important is that if I’m writing code that operates on ranges, I might need to require some of these concepts in order to do my work efficiently. For example, a sorting routine would be very difficult to write for anything less than a random_access_range (and indeed you’ll see that std::ranges::sort requires that). In other cases, I might be able to do things more optimally when the range satisfies certain concepts—for instance, if it’s a sized_range, I could preallocate some storage for results, while if it’s only an input_range and no more, then I’ll have to dynamically reallocate, as I have no idea how many elements there are going to be.

The rest of the ranges library is written in terms of these concepts (and you can write your own code that operates generically on ranges using these concepts as well). So, once your container satisfies the relevant concepts, it will automatically be recognized and function as a range!

In C++20, concepts act as boolean expressions, so you can check whether your container satisfies the concepts you expect by just writing asserts for them:

#include <ranges>
static_assert(std::ranges::forward_range<MyCoolContainer<int>>);
// int is just an arbitrarily chosen element type, since we
// can't assert a concept for an uninstantiated template

Checks like this are great to add to your test suite—I’m big in favor of writing compile-time tests for generic/metaprogramming stuff, in addition to the usual runtime tests.

However, when you first drop that assert into your code, it will almost certainly fail. Let’s see now what you need to do to actually satisfy the range concepts.
Defining Range-Compatible Iterators

In order to satisfy the input range concepts, you need to do two things:

    Have begin and end functions that return some iterator and sentinel types. (We’ll discuss these in a little bit.)
    The iterator type must satisfy the iterator concept that matches your range concept.

Each one of the concepts from input_range down to contiguous_range has a corresponding iterator concept: std::input_iterator, std::forward_iterator, and so on. It’s these concepts that contain the real meat of the requirements that define the different types of ranges: they list all the operations each kind of iterator must support.

To begin with, there are a couple of member type aliases that any iterator class will need to define:

    difference_type: some signed integer type, usually std::ptrdiff_t
    value_type: the type of elements that the iterator references

The second one seems pretty understandable, but I honestly have no idea why the difference_type requirement is here. Taking the difference between iterators doesn’t make sense until you get to random-access iterators, which actually define that operation. As far as I can tell, the difference_type for more general iterators isn’t actually used by anything. Nevertheless, according to the C++ standard, it has to be there. It seems that the usual idiom is to set it to std::ptrdiff_t in such cases, although it can be any signed integer type.

(Technically you can also define these types by specializing std::iterator_traits for your iterator, but here we’re just going to put them in the class.)

Beyond that, the requirements for std::input_iterator are pretty straightforward:

    The iterator must be default-initializable and movable. (It doesn’t have to be copyable.)
    It must be equality-comparable with its sentinel (the value marking the end of the range). It doesn’t have to be equality-comparable with other iterators.
    It must implement operator ++, in both preincrement and postincrement positions. However, the postincrement version does not have to return anything.
    It must have an operator * that returns a reference to whatever the value_type is.

One point of interest here is that the default-initializable requirement means that the iterator class can’t contain references, e.g. a reference to the container it comes from. It can store pointers, though.

A prototype input iterator class could look like this:

template <typename T>
class Iterator
{
public:
    using difference_type = std::ptrdiff_t;
    using value_type = T;
    Iterator();                 // default-initializable
    bool operator == (const Sentinel&) const;   // equality with sentinel
    T& operator * () const;     // dereferenceable
    Iterator& operator ++ ()    // pre-incrementable
        { /*do stuff...*/ return *this; }
    void operator ++ (int)      // post-incrementable
        { ++*this; }
private:
    // implementation...
};

For a std::forward_iterator, the requirements are just slightly tighter:

    The iterator must be copyable.
    It must be equality-comparable with other iterators of the same container.
    The postincrement operator must return a copy of the iterator before modification.

A prototype forward iterator class could look like:

template <typename T>
class Iterator
{
public:
    // ...same as the previous one, except:
    bool operator == (const Iterator&) const;   // equality with iterators
    void operator ++ (int)      // post-incrementable
        { Iterator temp = *this; ++*this; return temp; }
};

I’m not going to go through the rest of them in detail; you can read the details on cppreference.
Begin, End, Size

Once your container is equipped with an iterator class that satisfies the relevant concepts, you’ll need to provide begin and end functions to get those iterators. There are three ways to do this: they can be member functions on