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

This is a discussion on Reversing the traversal of c++0x's range based for within the C++ Programming forums, part of the General Programming Boards category; I've recently been playing around with the range based for loop in gcc-4.6, and I had this idea that it'd ...

  1. #1
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174

    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?

  2. #2
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    460
    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.
    "All that we see or seem
    Is but a dream within a dream." - Poe

  3. #3
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    Quote Originally Posted by nimitzhunter View Post
    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().

  4. #4
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,762
    I guess it comes down to whether or not you want to compile extra code just for this.

  5. #5
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    Quote Originally Posted by whiteflags View Post
    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.

  6. #6
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,762
    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.

  7. #7
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    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.

  8. #8
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,762
    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.

  9. #9
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    460
    This would do without all thE extra classes
    Code:
    list.reverse();
    for (int I: list)
       Cout << I;
    "All that we see or seem
    Is but a dream within a dream." - Poe

  10. #10
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    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.

  11. #11
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    460
    I believe that was what he said.
    "All that we see or seem
    Is but a dream within a dream." - Poe

  12. #12
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    Quote Originally Posted by nimitzhunter View Post
    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.

  13. #13
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    23,021
    Well, regardless what others think, I like it. It's a shame Visual C++ doesn't support range-based foor loops yet.
    Now all we need is some way to dump all the common code we use into every new project.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  14. #14
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    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.

    Quote 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.

  15. #15
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    23,021
    Heh. Well, it's possible to do this, but doesn't it defeat the whole purpose of a range-based for loop?
    But at least we have auto, so the iterator part can be killed.
    And I'd rather it be longer than obfuscated.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. why page based I/O can improve performance?
    By George2 in forum C Programming
    Replies: 1
    Last Post: 06-12-2006, 08:42 AM
  2. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21