Sunday 12 May 2013

C++11: Iterating range-based for backwards


A few weeks ago we upgraded our toolchain with spangly new C++ compilers. Then we flipped the magical switch unleashing C++11 code features. This is a joyful apocalypse.

It's been fun transitioning to some of the new neater C++11 idioms.

Range-based for is one of the first things we adopted, largely due to the clear readability improvements it brings over tedious iterator type juggling.

Soon we stumbled on a shortcoming of range-based for. It allows you to iterate forwards with little syntax fluff, but not backwards. (We have many collections we "apply" by iterating forwards, and then "revert" by iterating backwards).

It's not too hard to iterate backwards in a reasonably readable way, by writing code like this:
for (const auto &i : backwards(collection))
{
    // ... use i ...
}
The simplest implementation of this is shown below:
template <typename T>
class iterate_backwards
{
public:
    explicit 
iterate_backwards(const T &t) : t(t) {}
    typename T::const_reverse_iterator begin() const { return t.rbegin(); }
    typename T::const_reverse_iterator end()   const { return t.rend(); }
private:
    const T &t;
};
template 
<typename T>
iterate_backwards backwards(const T &t)
{
    return 
iterate_backwards(t);
}
Of course, this is simplistic. It can be enhanced by making the class support C++11's move semantics, and allowing the wrapper function to return forwarded iterate_backwards. However, this wonderful new C++11 machinery serves to hide the simple intent somewhat, and doesn't win us much since this code optimises away neatly.

Perhaps there's a better way to do this? I've seen a few other solutions to this problem, but they don't read anywhere near as neatly, nor are they as straightforward to understand. I'm enjoying this new learning journey.

More iterator fun is to come...

10 comments:

Anonymous said...

Hi, You could also use boost: http://www.boost.org/doc/libs/1_53_0/libs/range/doc/html/range/reference/adaptors/reference/reversed.html

you get something like:
for (auto i : boost::adaptors::reverse(container))
{
// do something with i
}

Pete Goodliffe said...

True.

Without a lot of extra using malarkey, this strikes me as a slightly less readable alternative.

I'd rather not co-opt loads of boost with a using declaration at the top of the file, so this seems rather verbose. I suppose a single "using boost::adaptors::reverse" would work adequately.

Perhaps my argument is bogus, and I should just use the sharp boost tools...

(There's always some fun to be had in reinventing wheels, too, mind.)

Phil Nash said...

I seem to spend more and more time rewriting things that boost already provides.
Not because of NIH or lack of awareness - in most cases we start out using boost but it tends to be slow at runtime (profiled) and drags the build (due to excessive portability requirements and generalisation) - as well as being hard to debug through.
For about 2/3 of what we were using boost for it was fairly easy to write faster and simpler more focused versions.

Your 'backwards' adapter may fall into that category for you - but YMMV, of course.

Anonymous said...

I am porting over some code from C++98 to C++11 using Visual C++ 2012.

I noticed that range based for loop was significantly slower than std::for_each. I have since removed all range based for loops and replaced them with STL ones.

Have you done any benchmarking on your application?

Pete Goodliffe said...

No, I've not benchmarked. That does seem very surprising, though.

Dumb question: did you write

for (auto &i : thing)

or

for (auto i : thing)

That could have had a profound effect.

I'm going to be touching on a load of other benchmarking in another post shortly. Not specifically VC2012, though.

Anonymous said...

I think HTML has swallowed a couple of your template parameters there in iterate_backwards(). Pesky angle brackets!

Anonymous said...

Slightly off topic, but you should be using the new initialization syntax in mp the member initializer list, as in:

t{t} vs. t(t) in the actor.

Anonymous said...

Re: Performance loss using range-based for loop.

I used:
for (thing& t : thing_collection) // no auto
{
...
}

Anonymous said...

Note that this is dangerous as you might end up with a dangling reference, see the C++11 standard, paragraph 6.5.4. It happens when the container is returned as a value from some function and you call

for( const auto& v : backwards( getContainer() ) )
{
// do something...
}

This StackOverflow Q/A also explains it. You'd need to store a copy of the container, but then it becomes inefficient. Sorry :)

Pete Goodliffe said...

Ooooh, that's nasty. Thanks for pointing it out.