Using Token Sequences to Iterate Ranges

Summary

There was a StackOverflow question recently that led me to want to write a new post about Ranges. Specifically, I wanted to write about some situations in which Ranges do more work than it seems like they should have to. And then what we can do to avoid doing that extra work. I’ll offer solutions — one sane one, which you can already use today, and one pretty crazy one, which is using a language feature we’re still working on designing, which may not even exist in C++29.The ProblemFor the purposes of this post, I’m just going to talk about the very simple problem of:for (auto elem : r) { use(elem); } In the C++ iterator model, this desugars into something like:auto __it = r.begin(); auto __end = r.end(); while (__it != __end) { use(*__it); ++__it; } I used a while loop here deliberately, because it’s a simpler construct and it lets me write the advance step last.Now, if you want to customize the behavior of a range, those are your entry points right there. You can change what the initialization phase does (begin() and end()), you can change the check against completeness (__it != __end), you can change the read operation (*__it), and you can change the advance operation (++__it). That’s it. You can’t change the structure of the loop itself.That alone is enough to offer a pretty large wealth of functionality. It’s a very powerful abstraction.The Ranges library has a bunch of range adaptors which customize this behavior. Some of them very neatly slot into this set of customization points. views::transform just changes what *__it does. views::drop just changes what r.begin() does. These adaptors have no overhead.Now, it might not be surprising to learn that an adaptor like views::join has some overhead. views::join really wants to write two nested loops, but it can’t — it has to flatten the iteration somehow. Or views::concat, which wants to write N loops instead of just one, but it can’t do that either. But there are a few adapters which seem like they should slot int...