DIY µ-range: The Very Versatile Range View / Iterator Pair

Introduction

A range is simply a pair of iterators. All the standard algorithms take a pair of parameters and you end up writing code like std::accumulate(receipts.begin(),receipts.end(),0) where most of the time, you are simply passing an entire container. A range-enabled version lets me write boost::accumulate(receipts,0).

Having a range abstraction as an object you can use directly is handy for keeping the matching begin/end together when passing them deeper, but the compelling use is the built-in range-for loop! You can use for over a whole container, but you can’t pass it individual begin/end iterators in the case where you want something other than a whole container.

A Pair of Iterators

In Boost.Range 2.0, a std::pair of iterators works as a range. However, this has proven to be problematic as more generic code is range aware, as pairs have uses other than as ranges.

As noted in the first article, it is extremely simple to make a “range view”. It just needs to hold the two iterators and provide begin and end functions. Here is a template that does this:

template <typename B_iter, typename E_iter=B_iter>
struct range_view {
    B_iter first;
    E_iter second;
    auto begin() const { return first; }
    auto end() const { return second; }
    range_view() = delete;
    range_view (B_iter first, E_iter second) : first{first}, second{second} {}
    template <typename R>
    range_view (const R& range) : first{Begin(range), second{End(range)}}  {}
};

// Visual Studio 15.8.0p1 does not support user-defined deduction guides yet.

template <typename R>
auto make_range_view (const R& range)
{
    return range_view {Begin(range), End(range)};
}

Notice that unlike Range 2.0, the begin and end can be of different types. This allows the use of sentinels as ends, an idea that has already been adopted into the built-in range-for loop.

Here is an example usage that shows how the range_view can substitute for a container:

std::vector<int> v1 { 1, 2, 6, 8, 20 };
//    D3::range_view rv1 { v1 };   // needs user-defined deduction guide in order to do that.
auto rv1 = D3::make_range_view(v1);// so use a helper function instead

REQUIRE (  std::equal (Begin(rv1),End(rv1), Begin(v1))  );

for (auto i : rv1) {
    cout << i << ' ';
}
cout << '\n';

So, with the right constructors (or helper functions), it can easily make a view of a container. So what, if it can only do what the container could do already?

The key here is that you can manipulate the view, in ways that would be destructive to the container.

Key Use Case: Off-by-one Loops

Something I find particularly annoying with the current state of the for loop is the case where I want to process each element and do something between each pair of elements; that is, do something after every element except the last one, or equivalently, do something before every element except the first one.

You’ll notice in the previous listing that I just put a space after every element, since the trailing space will be unnoticed. Let’s neaten that up and put commas between elements.

Normally, you would have to add a kludgy state mechanism to handle the first (or last) element differently, or forego the neat range-for and use the laborious classic-for loop over the iterators.

But armed with this simple view, I have an alternative. Print the first element, and then remove it from the view. Then the range-for will handle only the remaining elements.

cout << *rv1.first++;
for (auto i : rv1) {
    cout << ", " << i;
}

Eating the first element before the loop, the range view is then updated to omit that element. Then, a normal for loop handles the rest.

This was simple, and done without any further work on the range_view class. But we do need another feature: Consider that most code would also check if the range is empty: if(rv1.begin() != rv1.end()) ought to be figured out by the generic std::empty, but it’s not defined to work generically with anything that offers a begin and end. So, I’ll add a member function for that.

if (!Empty(rv1)) cout << *rv1.first++;

See my earlier article Avoid the “std 2-step” about the Empty wrapper for std::empty.

But as long as I’m adding that, I might as well expose the same data via operator bool and operator! Now it simplifies to:

if (rv1) cout << *rv1.first++;

Now, look at the rest of the line. Reaching in and using first is simple, and makes it clear which end is being manipulated. But it is especially handy to make the range view object itself act like an iterator. That is, forward all the iterator features to the first. In this example, we now have:

if (rv1) cout << *rv1++;   // first item (if present)
for (auto i : rv1) {       // rest of items
    cout << ", " << i;
}

Use Case: Smarter Iterator

Treating the pair as an iterator might seem like a minor improvement in the previous listing. But the idea of treating the range view as an iterator has some nice generalization. The concept is that the pair should be just like the iterator it is holding (as first) but it also knows where its own end is.

Consider a function that returns an iterator, which happens to be the end iterator to indicate no result.

auto found= find_something (vec.begin(), vec.end());
if (found != vec.end()) { ⋯ do something

The no-result case is awkward and contrary to the way we prefer things in C++, where the contexutal conversion to bool indicates a useful truth value for this exact situation. With a pointer (including smart pointers), you would write something like:

if (auto found= find_something (args)) { ⋯

which furthermore uses the feature of putting the test with the declaration and found is only in scope when it is valid to use. Sure, in C++17, you can now write a separate initializer clause in the if statement:

if (auto found= find_something (vec.begin(), vec.end()); found != vec.end()) { ⋯ do something

but that is nowhere nearly as nice as if the iterator knew if it was the end all by itself.

Updating find_something to use ranges, you normally consider the dual input parameters — now you can pass the whole collection instead. But what about the return result? Make that a range_view referring to part of the input, and you get several benefits.

As we were discussing, it now allows you to use the boolean truth value to test for validity. But, what should the range returned be? If a function finds a range of results, it is natural to return that exact range ready to go, rather than just an iterator to the first item found. This can make some range-enabled algorithms and functions more natural to use. Ranges compose in ways that iterators do not.

if (auto found= find_something (vec)) { ⋯ do something

Notice that this is exactly like the code which returns a (smart) pointer. If iterators are meant to be generalizations of pointers, isn’t that how it ought to be?

If more than one item matched in a sorted vector, the returned range naturally conveys the entire range of matches. There is no ambiguity on the part of the caller looking at the result: incrementing found will produce an empty range if there was only one item.

Summary

Ranges are great. With C++17, you can make use of the range idea in just a few lines of code — no huge infrastructure or metaprogramming needed!

Everything I’ve shown here works with this minimal class:

template <typename B_iter, typename E_iter=B_iter>
struct range_view {
    B_iter first;
    E_iter second;
    auto begin() const { return first; }
    auto end() const { return second; }

    range_view() =delete;
    range_view (B_iter first, E_iter second) : first{first}, second{second} {}
    template <typename R>
    range_view (const R& range) : first{Begin(range), second{End(range)}}  {}

    [[nodiscard]] bool empty() const noexcept { return first == second; }
    bool operator!() const noexcept { return empty(); }
    explicit operator bool() const noexcept { return !empty(); }

    // act like the 'first' when used as an iterator
    auto operator*() const { return *first; }
    range_view& operator++()  { ++first; return *this; }
    range_view operator++(int) { auto temp= *this;  ++first;  return temp; }
};

// Visual Studio 15.8.0p1 does not support user-defined deduction guides yet.

template <typename R>
auto make_range_view (const R& range)
{
    return range_view {Begin(range), End(range)};
}

Future Work

I’m working on a “mini-range” header that includes this and other handy features. This series will document the essential ideas and inner workings, to make a useful range library that is simple and understandable to the average C++ programmer.

History

• 31^st May, 2018: Initial version
• 8^th December, 2021: Article updated