Click here to Skip to main content
15,867,895 members
Articles / Programming Languages / C++14

DIY µ-range

Rate me:
Please Sign up or sign in to vote.
5.00/5 (5 votes)
23 May 2018CPOL4 min read 7.9K   5  
It is easier than ever to exploit the range-for loop (and make use of std algorithms) for things other than collections.

Introduction

In C++03, Boost.Range supplies a wonderful abstraction that is better than “regular” STL.  It contains a great deal of template metaprogramming, and the types involved need extensive instrumentation.

Image 1

Since C++11, we have a language feature that uses ranges: a new way to write a for loop.  It also has features like auto and decltype, which should make all that metaprogramming go away.

So, just how little scaffolding do we need to make the for loop do what we want, different from simply going through a collection object?  And, how well does this provide access to standard algorithms as well?

Background

Boost.Range has problems when mixed with the new native features of C++. The upcoming Range.v3 library is still under development, doesn’t work on Microsoft’s compiler, and is extremely complicated.  But, there are a small number of highly useful cases that I want to be able to achieve, and I think it can be done without a heavy library and lots of infrastructure.

Mission

The specific goal is to adapt the for loop to count, like we see in many other languages. That is, rather than producing a succession of values from a container, it will produce the integers in order, with nothing behind it.

count_iter

Here is the absolute minimum needed to make a counting iterator.

C++
struct count_iter {
    int value;
    int operator* () const { return value; }
    auto operator++ ()  { ++value;  return *this; }
};

bool operator== (const count_iter& left, const count_iter& right)
{
    return left.value == right.value;
}

bool operator!= (const count_iter& left, const count_iter& right)
{
    return !(left==right);
}

(actually, I probably did not need the == operator)

So, what can we do with this scrap of a class? Let’s start with a legacy for loop using iterators, approximating what the range-for expands into. This will show which parts work or not, without any more of the project available yet.

C++
void f() {

    count_iter B {1};
    count_iter E {42};

    for (auto it=B;  it != E;  ++it)
        cout << ' ' << *it;
    cout << '\n';
}

The construction is handled by aggregate initialization; there were no constructors written.

In auto it=B, the copy construction is handled by an auto-generated copy constructor.

The use of !=, prefix ++, and * are the (only) things written for the count_iter class.

Unsurprisingly, this explicit use of certain operators works without complaint.  What about other code that takes iterators, I wonder?

C++
int total = std::accumulate (B, E, 0);
cout << "total accumulated is: " << total << '\n';

The accumulate algorithm works just fine.  It probably is written much like the loop above; it does not need to do anything else, and it doesn’t miss any of the infrastructure around iterator types.

Try something a little harder?

C++
auto found = std::find (B, E, 18);
cout << "found 18? " << *found << '\n';

Again, find must work by going through a similar loop. Any algorithm that makes sense at all for an immutable sequence of integers probably works in exactly the same way.

Time to up the stakes:  binary_search relies on the sequence being in order. But, I have not provided any ability to jump around or move backwards. But, the reference says that binary_search works on Forward Iterators.  Presumably, it is not actually a binary search in this case, but stops when it passes where the element would be, since it knows it must be sorted.

So, the implementation uses meta stuff to decide what capabilities the iterator has, and chooses among different implementations.

C++
bool found2 = std::binary_search (B, E, 18);
cout << "binary search? " << found2 << '\n';

And… it will not compile, for deep and mysterious reasons. So, we have reached the limit of what this ultra-minimalizm will achieve. Code can use the provided operators, which are expected to work on any Forward Iterator, and much of the library code indeed just does that. But fancier stuff that requires a more capable iterator or that makes use of some metafunction or another will not work.

I’ll return to this point later; it is not necessary for the mission.

A Range View

In order to have the built-in range-for construct work, it needs something that it can call begin and end on.  That is all?  Minimal enough, and simple:

C++
struct range_view {
    count_iter first;
    count_iter second;
    auto begin() const { return first; }
    auto end() const { return second; }
};

Now to try it:

C++
void g() {

    range_view counter {{1},{42}};

    for (auto i : counter)
        cout << ' ' << i;
    cout << '\n';

}

It works!

Clearly, this is not the best way to make a convenient counter loop, but note that the object can be created in-line:

C++
for (auto i : range_view{{1},{42}}) { ⋯

But it is just a matter of making a suitably handy function that returns a range_view object.

Points of Interest

Clearly, it would be a more significant body of work to make a thing that precisely emulates a constant container filled with consecutive numbers.  But for your own day-to-day work, you don’t need that. For filling a limited and specific use, it can be nearly trivial to make something that mimics an iterator in some way that lets you use std algorithms.  It is quite simple to make the for loop handle your own thing, not just collections.

Another use case I have in mind for a templated range_view is the annoying case where you want the first or last iteration of a loop to be different.  But that’s another story.  The point is, this technique can be a new tool in your general toolbox.

Epilog

The reason std::binary_search did not work is because it could not tell that my thing was a model of Forward Iterator.  To provide that information, we supply the iterator_traits.

C++
template<>
struct std::iterator_traits<count_iter> {
    using difference_type = int;
    using value_type = int;
    using pointer = int;
    using reference = int&;
    using iterator_category = forward_iterator_tag;
};

Fancy-written algorithms will look in here for information.  Most of those traits are obsolete because code can just use auto and decltype, but iterator_category is still important. (You could use metaprogramming to classify it automatically, via the detection idiom. But the standard library does not do that.)

Future Work

I’m working on a “mini-range” header that includes templates evolved from this, and other handy features.

This article was originally posted at https://github.com/jdlugosz/d3

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Senior)
United States United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
-- There are no messages in this forum --