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

Originally Posted by Mozza314

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.

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?

Originally Posted by Mozza314

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.

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';
}

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)?

I mean, it could lead to a runtime failure (reverse_wrapper binds to a temporary).

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

Originally Posted by whiteflags

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.

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.