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.
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.
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.
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?
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?
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.
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:
struct range_view {
count_iter first;
count_iter second;
auto begin() const { return first; }
auto end() const { return second; }
};
Now to try it:
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:
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.
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.
