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; Originally Posted by Mozza314 As I understand it, whiteflags' concern is compile time overhead. I interpret whiteflag's concern differently: it ...

  1. #16
    Registered User
    Join Date
    Jun 2005
    Posts
    5,852
    Quote Originally Posted by Mozza314 View Post
    As I understand it, whiteflags' concern is compile time overhead.
    I interpret whiteflag's concern differently: it is hard to see that the benefit offered by your code exceeds the investment of effort in writing your code (or, for others) the investment in effort to use it effectively. That has nothing to do with compile-time overhead - it is a concern of programmer productivity.

    That is a valid real-world concern.

    That aside, one thing you need to take into account is that the standard containers provide const and non-const versions of begin(), rbegin(), end(), and rend(). Your code will not compile if the loop and body require non-const iterators from a non-const container.
    Right 98% of the time, and don't care about the other 3%.

  2. #17
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    How does it defeat the purpose of a range-based for loop? Isn't its purpose to simplify the code for iterating through a container? By that measure using a script substitution would be identical. I see your point about obfuscation though.

  3. #18
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    Quote Originally Posted by grumpy
    That aside, one thing you need to take into account is that the standard containers provide const and non-const versions of begin(), rbegin(), end(), and rend(). Your code will not compile if the loop and body require non-const iterators from a non-const container.
    I don't think I understand you correctly. Did you mean non-const iterators from a const container? I wrote the code to handle const containers using template specialization (even though it turned out to be unnecessary, but I digress). Could you post a small code fragment that breaks with my reverse() but is ok when removed?
    Last edited by Mozza314; 02-20-2011 at 04:10 AM. Reason: [code] -> [quote=grumpy]

  4. #19
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,171
    Quote Originally Posted by Mozza314 View Post
    How does it defeat the purpose of a range-based for loop? Isn't its purpose to simplify the code for iterating through a container? By that measure using a script substitution would be identical. I see your point about obfuscation though.
    I meant the for_each algorithm would defeat the purpose of a range-based for loop. It would essentially be the same as a normal loop.
    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.
    For information on how to enable C++11 on your compiler, look here.
    よく聞くがいい!私は天才だからね! ^_^

  5. #20
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Coming back to the original code, are the specializations for const required? If you omit them, won't the container parameter simply be deduced as "const some_container" and everything would already work?

    How's something like this to also support plain arrays. (My compiler doesn't seem to have std::begin, and I don't know if there is supposed to be a std::rbegin, but if the latter doesn't exist, it would take just a bit of more work to make it "boostless".

    Code:
    #include <boost/range.hpp>
    
    template <typename container>
      class reverse_wrapper
      {
      private:
          container& c_;
    
     public:
         typedef decltype(boost::rbegin(c_)) iterator; //required by BOOST_FOREACH
         typedef iterator const_iterator;
         reverse_wrapper(container& c) : c_(c) { }
    
         iterator begin() const { return boost::rbegin(c_); }
         iterator end() const { return boost::rend(c_); }
     };
    
     template <typename container>
     reverse_wrapper<container> reversed(container& c)
     {
         return reverse_wrapper<container>(c);
     }
    
    #include <vector>
    #include <iostream>
    #include <boost/foreach.hpp> //no range for supported here :(
    
    int main()
    {
        std::vector<int> vec{1, 2, 3};
        BOOST_FOREACH(const int& n, reversed(vec)) std::cout << n << '\n';
        const int arr[] = {1, 2, 3, 4, 5, 6, 7};
        BOOST_FOREACH(int n, reversed(arr)) std::cout << n << '\n';
    }
    Last edited by anon; 02-20-2011 at 04:47 AM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  6. #21
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    Quote Originally Posted by Elysia View Post
    I meant the for_each algorithm would defeat the purpose of a range-based for loop. It would essentially be the same as a normal loop.
    A range based for loop is essentially the same as a normal loop too, is it not? Am I missing something?

  7. #22
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    Quote Originally Posted by anon View Post
    Coming back to the original code, are the specializations for const required? If you omit them, won't the container parameter simply be deduced as "const some_container" and everything would already work?
    That's right, I discovered it a while after starting this thread. I'm currently putting together the "boostless" version you mention, I'll post it shortly.

  8. #23
    The larch
    Join Date
    May 2006
    Posts
    3,573
    It appears const_iterator should be typedeffed as iterator (since reverse_wrapper only returns iterators anyway).

    However, it seems it would be an error for reversed to accept temporaries (by adding the const overload)?
    Last edited by anon; 02-20-2011 at 04:47 AM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  9. #24
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    Quote Originally Posted by anon View Post
    It appears const_iterator should be typedeffed as iterator (since reverse_wrapper only returns iterators anyway).

    However, it seems it would be an error for reversed to accept temporaries (by adding the const overload)?
    Oooh it would be an error for reverse() to accept temporaries. Thanks for that, I think I will add a const overload.

  10. #25
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I mean, it could lead to a runtime failure (reverse_wrapper binds to a temporary).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  11. #26
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    Ok updated version:

    reverseDemo.cpp:
    Code:
     1 #include <iostream>                                                                                                        
     2 #include <list>
     3 
     4 #include "reverse_access.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_access(someInts)) // basic usage
    13         std::cout << v << ' ';
    14     std::cout << std::endl;
    15     
    16     const std::list<int> constSomeInts(someInts);
    17     for (int v : reverse_access(constSomeInts)) // const usage
    18         std::cout << v << ' ';
    19     std::cout << std::endl;
    20     
    21     for (int v : reverse_access(std::list<int>(someInts))) // temporary usage
    22         std::cout << v << ' ';
    23     std::cout << std::endl;
    24     
    25     int someIntsStatic[] = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81};
    26     for (int v : reverse_access(someIntsStatic)) // static array usage
    27         std::cout << v << ' ';
    28     std::cout << std::endl;
    29     
    30     const int constSomeIntsStatic[] = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81}; // const static array usage
    31     for (int v : reverse_access(constSomeIntsStatic))
    32         std::cout << v << ' ';
    33     std::cout << std::endl;
    34     
    35     return 0;
    36 }
    output:
    Code:
    81 64 49 36 25 16 9 4 1 0 
    81 64 49 36 25 16 9 4 1 0 
    81 64 49 36 25 16 9 4 1 0 
    81 64 49 36 25 16 9 4 1 0 
    81 64 49 36 25 16 9 4 1 0
    reverse_access.hpp:
    Code:
     1 #ifndef REVERSE_ACCESS_HPP                                                                                                 
     2 #define REVERSE_ACCESS_HPP
     3 
     4 #include <cstddef>
     5 
     6 template <typename container>
     7 class reverse_access_class
     8 {
     9 private:
    10     container& c_;
    11 
    12 public:
    13     reverse_access_class(container& c) : c_(c) { }
    14 
    15     inline decltype(c_.rbegin()) begin() const { return c_.rbegin(); }
    16     inline decltype(c_.rend()) end() const { return c_.rend(); }
    17 };
    18 
    19 template <typename T>
    20 class reverse_access_static_array_class
    21 {
    22 private:
    23     T* s_array_;
    24     std::size_t size_;
    25 
    26     class iterator
    27     {
    28     private:
    29         T* s_array_;
    30         std::size_t index_plus1_; // 0 needs to indicate 1 before the beginning of the array
    31 
    32     public:
    33         iterator(T* s_array, std::size_t index_plus1)
    34         :
    35             s_array_(s_array),
    36             index_plus1_(index_plus1)
    37         {
    38         }
    39 
    40         iterator& operator++() { --index_plus1_; return *this; }
    41         T& operator*() const { return s_array_[index_plus1_ - 1]; }
    42         bool operator!=(const iterator& rhs) const { return index_plus1_ != rhs.index_plus1_; }
    43     };
    44 
    45 public:
    46     reverse_access_static_array_class(T s_array[], std::size_t size)
    47     :
    48         s_array_(s_array),
    49         size_(size)
    50     {
    51     }
    52 
    53     iterator begin() const { return iterator(s_array_, size_); }
    54     iterator end() const { return iterator(s_array_, 0); }
    55 };
    56 
    57 template <typename container>
    58 inline reverse_access_class<container> reverse_access(container& c)
    59 {
    60     return reverse_access_class<container>(c);
    61 }
    62 
    63 template <typename container>
    64 inline reverse_access_class<const container> reverse_access(const container& c)
    65 {
    66     return reverse_access_class<const container>(c);
    67 }
    68 
    69 template <typename T, std::size_t size>
    70 inline reverse_access_static_array_class<T> reverse_access(T (&s_array)[size])
    71 {
    72     return reverse_access_static_array_class<T>(s_array, size);
    73 }
    74 
    75 #endif // REVERSE_ACCESS_HPP
    Last edited by Mozza314; 02-20-2011 at 05:40 AM. Reason: forgot "const" in front of constSomeIntsStatic

  12. #27
    Registered User
    Join Date
    Jan 2008
    Posts
    70
    I would agree with whiteflag that the compile time cost of constructing a templated class is in most cases not worth small amount of syntactic sugar it produces. Maybe without auto I might consider it.

    If you're interested in getting something similar to ranged based for loops in visual studio 2010 you could do something like this. Boost does something like this, but theirs handles a few other cases and takes much longer to compile because of it.

    Code:
    #define CATI(a,b) a##b
    #define CAT(a,b) CATI(a,b)
    #define CTR() __COUNTER__
    
    #define intern_foreach(val,container,endIter,shouldCont)\
      auto endIter = container.end();\
      bool shouldCont = true;\
      for(auto iter = container.begin(); endIter != iter && shouldCont; ++iter )\
      if( shouldCont = false ){}else\
      for( val = *iter; !shouldCont; shouldCont = true)
    #define foreach(val,container)\
      intern_foreach(val,container,CAT(end,CTR()),CAT(contin,CTR()))
    
    //Outputs 1\n2\n3\n
    int main(void)
    {
      vector<array<int,3>> v;
      array<int,3> val = {1,2,3};
      v.push_back(val);
      typedef array<int,3> intArr3;
    
      foreach(intArr3& arr, v)
      {
        foreach( int i, arr )
        {
          printf("%d\n",i);
        }
      }
    }
    Surprisingly in release mode this optimizes to the same assembly as a hand written loop. It does support using break and continue as expected. Unfortunately the double for loop trick causes the debugger to jump around a bit.
    Also note that this won't work on any major compiler besides VC10 because I use both __COUNTER__ and auto. There is a way to not use __COUNTER__ but it is ugly and will increase compile times.
    I have not tested this much so there may be bugs.

  13. #28
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,892
    Quote Originally Posted by whiteflags View Post
    If you need to use a different step size, for example, you can't shoehorn range based for loops into that.
    Sure you can. Boost.Range's strided adapter does exactly that. For that matter, Boost.Range also allows you to filter, and transform in many ways the source range.

    If you care about performance, you could write a regular for loop to do everything your code does.
    Given just a bit of inlining by the compiler, the code has zero runtime overhead. And it's much clearer than the corresponding for-loop once the implementation of reverse() is out of the way.

    If you don't care about performance, you could reverse the container and then use the range based for loop.
    That's not a performance issue, that's a semantics issue. Reversing a container has lasting effects, traversing it in reverse order doesn't.

    I'm underwhelmed and most people would be.
    Don't presume to speak for "most people". I for one think this is a very useful utility, and its only problem is that it's redundant, because it's already available in the Boost.Range library as the reversed adapter.

    Quote Originally Posted by Drac
    I would agree with whiteflag that the compile time cost of constructing a templated class is in most cases not worth small amount of syntactic sugar it produces.
    Code:
    for (auto it = container.rbegin(); it != container.rend(); ++it) {
    }
    Code:
    for (auto& e : reversed(container)) {
    }
    This isn't just syntactic sugar. This is speaking code. Just compare to the forward iteration loops:
    Code:
    for (auto it = container.begin(); it != container.end(); ++it) {
    }
    Code:
    for (auto& e : container) {
    }
    The iterator-based one is very hard to distinguish from its reverse counterpart. The adapted for-range one is very obvious. The code is closer to expressing what you mean, all at zero runtime overhead. And template instantiations aren't *that* expensive.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  14. #29
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,526
    Quote Originally Posted by CornedBee View Post
    That's not a performance issue, that's a semantics issue. Reversing a container has lasting effects, traversing it in reverse order doesn't.
    Yes, and the point I wanted to make in that particular part of my post was that you have to wait for reverse() to complete using that alternative, where with using reverse_iterator you do not necessarily reverse the container so the iterator version, requiring less operations, should take less time.

  15. #30
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    Quote Originally Posted by CornedBee View Post
    its only problem is that it's redundant, because it's already available in the Boost.Range library as the reversed adapter.
    Ooooh I am liking boost adaptors :-D
    http://www.boost.org/doc/libs/1_43_0...roduction.html

    Damn boost makes it hard to make new contributions.

Page 2 of 2 FirstFirst 12
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, 07:42 AM
  2. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09: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