Thread: Reversing the traversal of c++0x's range based for

I've recently been playing around with the range based for loop in gcc-4.6, and I had this idea that it'd be nice to be able to use this structure to go through a container in reverse. I've written a utility that allows you to write something like this:

Code:

 1 #include <iostream>                                                                                                        
 2 #include <list>
 3 
 4 #include "reverse.hpp"
 5 
 6 int main()
 7 {
 8     std::list<int> someInts;
 9     for (int i = 0; i != 10; ++i)
10         someInts.push_back(i * i);
11 
12     for (int v : reverse(someInts))
13         std::cout << v << ' ';
14 
15     std::cout << std::endl;
16 
17     return 0;
18 }

Which has the expected output:

Code:

81 64 49 36 25 16 9 4 1 0

Here's reverse.hpp:

Code:

 1 #ifndef REVERSE_HPP                                                                                                        
 2 #define REVERSE_HPP
 3 
 4 template <typename container>
 5 class reverse_wrapper
 6 {
 7 private:
 8     container& c_;
 9 
10 public:
11     reverse_wrapper(container& c) : c_(c) { }
12 
13     decltype(c_.rbegin()) begin() const { return c_.rbegin(); }
14     decltype(c_.rend()) end() const { return c_.rend(); }
15 };
16 
17 template <typename container>
18 class reverse_wrapper<const container>
19 {
20 private:
21     const container& c_;
22 
23 public:
24     reverse_wrapper(const container& c) : c_(c) { }
25 
26     decltype(c_.rbegin()) begin() const { return c_.rbegin(); }
27     decltype(c_.rend()) end() const { return c_.rend(); }
28 };
29 
30 template <typename container>
31 reverse_wrapper<container> reverse(container& c)
32 {
33     return reverse_wrapper<container>(c);
34 }
35 
36 template <typename container>
37 reverse_wrapper<const container> reverse(const container& c)
38 {
39     return reverse_wrapper<const container>(c);
40 }
41 
42 #endif // REVERSE_HPP

I could also write shuffle() for containers with random access iterators with the same idea, although the implementation would have to be a tad more complex. It should be possible to get reverse() to work with static arrays too.

Anyone else think this is cool? Could there be a standard version of it planned that I don't know about?

Originally Posted by nimitzhunter

there is the reverse member functino for list. there is also rbegin() and rend() member functions as well. And checkout the random_shuffle() function from STL's algorithm.

I think you're missing the point that I'm using the range based for loop to go backwards through a container. While the range based for loop simplifies and makes container traversal much more readable, there's no builtin way to do the same thing going in reverse.

If you look closer at reverse.hpp, you'll see that the whole idea is re-routing begin() to rbegin() and end() to rend().

I guess it comes down to whether or not you want to compile extra code just for this.

Originally Posted by whiteflags

I guess it comes down to whether or not you want to compile extra code just for this.

Do you really think that's a significant concern? I could see your point if this was to go in the list, deque, etc. headers, but if it's on its own and you only include it when you use it, I don't see the problem.

It's just the only difference I can think of between what you've posted and what you could do.

Code:

for ( list<int>::reverse_iterator x = someInts.rbegin(); x != someInts.rend(); ++x ) cout << *x << endl;

You have to admit, that requires no more template code than what you are already using by using list and with no change in performance.

You could say the same thing about the range based for loop to begin with though -

why should we have:

Code:

for (int v : someInts) Foo(v);

when we already have:

Code:

for (list<int>::iterator i = someInts.begin(); i != someInts.end(); ++i) Foo(*i);

?

The answer is that the former is so much more readable and less cluttered. The idea behind the code I posted is bringing the advantages of the range based for loop to going through a container in reverse. If you don't see the big deal about the ranged based for loop to begin with, it makes sense that my code doesn't appeal to you.

You could say the same thing about the range based for loop to begin with though -

No you can't. Range based for loops remain useful while not requiring anyone to compile extra code. I'm not saying that range based for loops don't have a point, but I don't think that they replace for loops. If you need to use a different step size, for example, you can't shoehorn range based for loops into that. If you care about performance, you could write a regular for loop to do everything your code does. If you don't care about performance, you could reverse the container and then use the range based for loop. Or you could do what you've done. I'm underwhelmed and most people would be. I'm really sorry.

To suggest that is like being the opposite of whiteflags :-P.

Calling list.reverse(); really does reverse the list. It's a high cost just to go through the elements in reverse order. reverse(list) returns a wrapper around the list which maps begin() and end() to rbegin() and rend(), which is a very small amount of overhead and doesn't modify the list. I have been thinking reverse_access() would be a better name than reverse() for this reason though.

Originally Posted by nimitzhunter

I believe that was what he said.

As I understand it, whiteflags' concern is compile time overhead, as opposed to suggesting we instead introduce lots of extra run time overhead by calling list::reverse(). Hence, in a limited sense, opposite.

Yipee :-P

When I saw "Elysia has replied to [this thread]" in my inbox, I hesitated for a moment because I was worried you'd find something inherently wrong with this idea and I was about to be put to shame.

Originally Posted by Elysia

It's a shame Visual C++ doesn't support range-based foor loops yet.

Except for static arrays, isn't

Code:

for ((type) (name) : (container)) {(body)}

equivalent to:

Code:

for_each((container).begin(), (container).end(), [&] ((type) (name)) -> void {(body)});

?

Would it be possible with visual studio to setup some kind of script to do a substitution for you, and hide the output from you - just pass it to the compiler? I guess it would make errors hard to read though.