Writing your own C++ ranges and views

The Collatz sequence of 27 has 112 values, the last of them 1, and nothing tells you that length without computing every value. Writing your own C++ ranges turns such a sequence into something every loop, algorithm and view accepts, computed as it is read, with two small types: an iteratoriterator: An object that marks a position in a sequence: *it reads the element there and ++it moves to the next one. Every standard container hands out begin(), its first element, and end(), the position just past its last; what else an iterator can do depends on its category. More in “C++ iterators, iterator categories and sentinels”, which produces the elements one at a time, and a sentinelsentinel: An object that marks where a range ends by a condition rather than by a position: an iterator is compared with it to ask whether the end has been reached, as with one that equals any pointer at a '\0'. Since C++20 its type may differ from the iterator's. More in “C++ iterators, iterator categories and sentinels”, which recognises where they end.

To the standard library, anything whose begin() returns an iterator and whose end() returns a sentinel that compares equal to that iterator at the end is a range. A viewview: A range that does not own its elements: it refers to elements stored elsewhere or computes them, is cheap to copy, and does its work only while it is iterated, as std::views::filter and std::views::iota do. More in “C++ views and pipelines: filter, transform, iota” adds a promise about cost: copying or moving it does not depend on how many elements it has. Deriving from std::ranges::view_interface makes a class a view and gives it members such as empty() and front(), and static_assert(std::ranges::forward_range<MyView>) proves at compile time that the type meets the concept you claim, before any code depends on it.

A range is a begin() and an end() that meet at the end

A range is checked with conceptsconcept: A named compile-time test of template arguments, such as std::integral<T>, defined as template <typename T> concept Name = condition;. Used in a template's declaration, it makes the template accept only the types that satisfy it, and a type that fails is reported at the call. More in “C++20 concepts and requires-clauses”, and each concept names a few expressions that must compile:

• std::ranges::range<R>: ranges::begin(r) gives an iterator and ranges::end(r) gives a sentinel for it. Member functions begin() and end() are the usual way to provide them.
• std::sentinel_for<S, I>: the sentinel can be copied and default-constructed, and it == s compiles. The sentinel may be a type of its own, such as std::default_sentinel_t, which carries no data at all.
• std::input_iterator<I>: *it reads an element, ++it steps to the next one, and the iterator names its value_type and difference_type. A nested iterator_concept tag says which category it aims for.
• std::ranges::view<V>: a range that is movable and declared a view, which deriving from view_interface does. Since P2325R3, a view no longer has to be default-constructible.

Writing your own C++ ranges therefore starts with the iterator: everything else follows from what it can do. Each iterator categoryiterator category: The set of operations an iterator supports: input (read each element once, moving forwards), forward, bidirectional, random access and contiguous (the elements sit side by side in memory). Each category adds operations to the one before it, and an algorithm names the weakest it can work with. More in “C++ iterators, iterator categories and sentinels” adds operations, and each one makes more algorithms and views available:

CollatzView, the view of the next section, sits at forward on this ladder: copies of its iterator replay the same values and can be compared, but it cannot step back.

A sentinel ends the Collatz sequence without computing where

The Collatz sequence of a number halves it when it is even and replaces it with 3n + 1 when it is odd, until it reaches 1. Nobody knows in advance where it ends, which makes it a natural case for a sentinel: end() does not have to compute the last position, it only has to recognise it. The iterator stores the current value and a flag that becomes true after it has produced 1, and the sentinel compares equal to an iterator whose flag is set:

// The Collatz sequence of a start value as a view: the iterator computes the next value on ++, and a sentinel ends
// the sequence once it has passed 1. Deriving from view_interface makes it a view and adds front() and empty().
#pragma once
#include <cstdint>
#include <iterator>
#include <ranges>

class CollatzView : public std::ranges::view_interface<CollatzView> {
public:
    class iterator {
    public:
        using iterator_concept = std::forward_iterator_tag;
        using value_type = std::uint64_t;
        using difference_type = std::ptrdiff_t;

        iterator() = default;
        explicit iterator(std::uint64_t start) : value_(start) {}

        std::uint64_t operator*() const { return value_; }
        iterator& operator++() {
            if (value_ == 1) {
                done_ = true;  // 1 was the last value: now the iterator equals the sentinel
            } else {
                value_ = value_ % 2 == 0 ? value_ / 2 : 3 * value_ + 1;
            }
            return *this;
        }
        iterator operator++(int) {
            iterator before = *this;
            ++*this;
            return before;
        }

        bool operator==(const iterator&) const = default;
        bool operator==(std::default_sentinel_t) const { return done_; }

    private:
        std::uint64_t value_ = 1;
        bool done_ = false;
    };

    CollatzView() = default;
    explicit CollatzView(std::uint64_t start) : start_(start) {}

    iterator begin() const { return iterator{start_}; }
    std::default_sentinel_t end() const { return {}; }

private:
    std::uint64_t start_ = 1;
};

// The promises, checked by the compiler: if a requirement is missing, the build stops here.
static_assert(std::forward_iterator<CollatzView::iterator>);
static_assert(std::sentinel_for<std::default_sentinel_t, CollatzView::iterator>);
static_assert(std::ranges::forward_range<CollatzView>);
static_assert(std::ranges::view<CollatzView>);
static_assert(!std::ranges::sized_range<CollatzView>);

// Using CollatzView: printing it, measuring it, and putting it in a pipeline with the standard views.
#include <algorithm>
#include <cstdint>
#include <print>
#include <ranges>
#include "collatz.hpp"

int main() {
    std::println("{}", CollatzView{6});
    CollatzView c{27};
    std::println("27: {} values, largest {}, first {}", std::ranges::distance(c), std::ranges::max(c), c.front());
    auto odd_tens = c | std::views::filter([](std::uint64_t x) { return x % 2 == 1; }) |
                    std::views::transform([](std::uint64_t x) { return x * 10; }) | std::views::take(5);
    std::println("{}", odd_tens);
}

from session import run

# C++20 ranges, so both compilers build the same file.
run("""
clang++ -std=c++23 -Wall -Wextra collatz.cpp -o collatz && ./collatz
g++-16 -std=c++23 -Wall -Wextra collatz.cpp -o collatz && ./collatz
""")

$ clang++ -std=c++23 -Wall -Wextra collatz.cpp -o collatz && ./collatz
[6, 3, 10, 5, 16, 8, 4, 2, 1]
27: 112 values, largest 9232, first 27
[270, 410, 310, 470, 710]
$ g++-16 -std=c++23 -Wall -Wextra collatz.cpp -o collatz && ./collatz
[6, 3, 10, 5, 16, 8, 4, 2, 1]
27: 112 values, largest 9232, first 27
[270, 410, 310, 470, 710]

The sequence of 6 takes eight steps to reach 1, and the sequence of 27 has 112 values with a peak of 9232, numbers that the program computed without storing a single value. Step through the calls that any loop over CollatzView{6} makes, a range-for loop as much as std::println:

Four details make it work:

• begin() and end() are const, so the view can also be iterated through a const reference, the way many functions take their ranges.
• The iterator defines operator== with std::default_sentinel_t, and C++20 derives != and the reversed operand order from it, so one comparison covers every test the loops and algorithms write.
• It also has a default constructor, compares iterators with each other and has a postfix ++ that returns the old position, which is what std::forward_iterator requires in addition to an input iterator.
• std::ranges::distance walks the whole sequence to count it, because nothing knows its size in advance; the static_assert that it is not a sized_range documents that.

A base class makes it a view, and assertions prove its concepts

Because CollatzView is a view, the standard views compose with it: filter, transform and take turned the sequence of 27 into its first five odd values times ten, computed lazily as println asked for them. front() came from view_interfacestd::ranges::view_interface: A class template of <ranges> that a view derives from, passing its own type: it declares the class a view and gives it members such as empty() and front(), built from the class's own begin() and end(), so the class writes none of them., which builds it from begin().

The five assertions at the end of collatz.hpp state what the type promises, and the compiler checks each against the members of CollatzView. Step through them in order:

Five more ideas build on this one. Bidirectional iterators add --it. Random-access iterators add it + n, it[n] and it - it, which give a range its size. A range adaptor closurerange adaptor closure: An object such as std::views::take(2) that takes a range and returns a view, so that r | c means c(r): the form that lets adaptors chain with | into a pipeline. gives an adaptor of your own the | syntax. The debug modedebug mode: A checked build of a standard library, such as libstdc++ with -D_GLIBCXX_DEBUG or libc++'s debug hardening mode, whose containers and iterators check how they are used and stop the program at the first misuse. It is for testing, because it slows code down. More in “std::deque, std::list and iterator invalidation” of GCC’s library checks every step an iterator makes. A borrowed range is one whose iterators stay valid after the range object itself is gone.

Practise: iterators, sentinels and views

These questions cover the range concepts, the Collatz sentinel and the five assertions; each answer explains itself at once.

Forward, bidirectional and random-access views, proved and broken Pro: opens with a Pro, Premium or Ultimate pass

A stride view for libc++, tested against GCC 16's views::stride Pro: opens with a Pro, Premium or Ultimate pass

Borrowed ranges and dangling iterators, reproduced Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• A range is a begin() that returns an iterator and an end() that returns a sentinel comparing equal to it at the end, and the operations of the iterator decide which category on the ladder it reaches.
• A sentinel of its own type, such as std::default_sentinel_t, ends a sequence on a condition, so end() never has to compute where the sequence stops.
• Make begin() and end() const, define iterator_concept, value_type and difference_type, and let one operator== with the sentinel cover every comparison.
• Deriving from std::ranges::view_interface makes the class a view with members such as front(), and static_asserts of the concepts next to the class make a missing operation fail there, before any code uses it.