C++11 reverse range-based for-loop

Question

Is there a container adapter that would reverse the direction of iterators so I can iterate over a container in reverse with range-based for-loop?

With explicit iterators I would convert this:

for (auto i = c.begin(); i != c.end(); ++i) { ...

into this:

for (auto i = c.rbegin(); i != c.rend(); ++i) { ...

I want to convert this:

for (auto& i: c) { ...

to this:

for (auto& i: std::magic_reverse_adapter(c)) { ...

Is there such a thing or do I have to write it myself?

Answer 1

Actually Boost does have such adaptor: boost::adaptors::reverse.

#include <list>
#include <iostream>
#include <boost/range/adaptor/reversed.hpp>

int main()
{
    std::list<int> x { 2, 3, 5, 7, 11, 13, 17, 19 };
    for (auto i : boost::adaptors::reverse(x))
        std::cout << i << '\n';
    for (auto i : x)
        std::cout << i << '\n';
}

Answer 2

Actually, in C++14 it can be done with a very few lines of code.

This is a very similar in idea to @Paul's solution. Due to things missing from C++11, that solution is a bit unnecessarily bloated (plus defining in std smells). Thanks to C++14 we can make it a lot more readable.

The key observation is that range-based for-loops work by relying on begin() and end() in order to acquire the range's iterators. Thanks to ADL, one doesn't even need to define their custom begin() and end() in the std:: namespace.

Here is a very simple-sample solution:

// -------------------------------------------------------------------
// --- Reversed iterable

template <typename T>
struct reversion_wrapper { T& iterable; };

template <typename T>
auto begin (reversion_wrapper<T> w) { return std::rbegin(w.iterable); }

template <typename T>
auto end (reversion_wrapper<T> w) { return std::rend(w.iterable); }

template <typename T>
reversion_wrapper<T> reverse (T&& iterable) { return { iterable }; }

This works like a charm, for instance:

template <typename T>
void print_iterable (std::ostream& out, const T& iterable)
{
    for (auto&& element: iterable)
        out << element << ',';
    out << '\n';
}

int main (int, char**)
{
    using namespace std;

    // on prvalues
    print_iterable(cout, reverse(initializer_list<int> { 1, 2, 3, 4, }));

    // on const lvalue references
    const list<int> ints_list { 1, 2, 3, 4, };
    for (auto&& el: reverse(ints_list))
        cout << el << ',';
    cout << '\n';

    // on mutable lvalue references
    vector<int> ints_vec { 0, 0, 0, 0, };
    size_t i = 0;
    for (int& el: reverse(ints_vec))
        el += i++;
    print_iterable(cout, ints_vec);
    print_iterable(cout, reverse(ints_vec));

    return 0;
}

prints as expected

4,3,2,1,
4,3,2,1,
3,2,1,0,
0,1,2,3,

NOTE std::rbegin(), std::rend(), and std::make_reverse_iterator() are not yet implemented in GCC-4.9. I write these examples according to the standard, but they would not compile in stable g++. Nevertheless, adding temporary stubs for these three functions is very easy. Here is a sample implementation, definitely not complete but works well enough for most cases:

// --------------------------------------------------
template <typename I>
reverse_iterator<I> make_reverse_iterator (I i)
{
    return std::reverse_iterator<I> { i };
}

// --------------------------------------------------
template <typename T>
auto rbegin (T& iterable)
{
    return make_reverse_iterator(iterable.end());
}

template <typename T>
auto rend (T& iterable)
{
    return make_reverse_iterator(iterable.begin());
}

// const container variants

template <typename T>
auto rbegin (const T& iterable)
{
    return make_reverse_iterator(iterable.end());
}

template <typename T>
auto rend (const T& iterable)
{
    return make_reverse_iterator(iterable.begin());
}

Answer 3

This should work in C++11 without boost:

namespace std {
template<class T>
T begin(std::pair<T, T> p)
{
    return p.first;
}
template<class T>
T end(std::pair<T, T> p)
{
    return p.second;
}
}

template<class Iterator>
std::reverse_iterator<Iterator> make_reverse_iterator(Iterator it)
{
    return std::reverse_iterator<Iterator>(it);
}

template<class Range>
std::pair<std::reverse_iterator<decltype(begin(std::declval<Range>()))>, std::reverse_iterator<decltype(begin(std::declval<Range>()))>> make_reverse_range(Range&& r)
{
    return std::make_pair(make_reverse_iterator(begin(r)), make_reverse_iterator(end(r)));
}

for(auto x: make_reverse_range(r))
{
    ...
}

Answer 4

If you can use range v3 , you can use the reverse range adapter ranges::view::reverse which allows you to view the container in reverse.

A minimal working example:

#include <iostream>
#include <vector>
#include <range/v3/view.hpp>

int main()
{
    std::vector<int> intVec = {1, 2, 3, 4, 5, 6, 7, 8, 9};

    for (auto const& e : ranges::view::reverse(intVec)) {
        std::cout << e << " ";   
    }
    std::cout << std::endl;

    for (auto const& e : intVec) {
        std::cout << e << " ";   
    }
    std::cout << std::endl;
}

See DEMO 1.

Note: As per Eric Niebler, this feature will be available in C++20. This can be used with the <experimental/ranges/range> header. Then the for statement will look like this:

for (auto const& e : view::reverse(intVec)) {
       std::cout << e << " ";   
}

See DEMO 2

Answer 5

Does this work for you:

#include <iostream>
#include <list>
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
#include <boost/range/iterator_range.hpp>

int main(int argc, char* argv[]){

  typedef std::list<int> Nums;
  typedef Nums::iterator NumIt;
  typedef boost::range_reverse_iterator<Nums>::type RevNumIt;
  typedef boost::iterator_range<NumIt> irange_1;
  typedef boost::iterator_range<RevNumIt> irange_2;

  Nums n = {1, 2, 3, 4, 5, 6, 7, 8};
  irange_1 r1 = boost::make_iterator_range( boost::begin(n), boost::end(n) );
  irange_2 r2 = boost::make_iterator_range( boost::end(n), boost::begin(n) );


  // prints: 1 2 3 4 5 6 7 8 
  for(auto e : r1)
    std::cout << e << ' ';

  std::cout << std::endl;

  // prints: 8 7 6 5 4 3 2 1
  for(auto e : r2)
    std::cout << e << ' ';

  std::cout << std::endl;

  return 0;
}

Answer 6

template <typename C>
struct reverse_wrapper {

    C & c_;
    reverse_wrapper(C & c) :  c_(c) {}

    typename C::reverse_iterator begin() {return c_.rbegin();}
    typename C::reverse_iterator end() {return c_.rend(); }
};

template <typename C, size_t N>
struct reverse_wrapper< C[N] >{

    C (&c_)[N];
    reverse_wrapper( C(&c)[N] ) : c_(c) {}

    typename std::reverse_iterator<const C *> begin() { return std::rbegin(c_); }
    typename std::reverse_iterator<const C *> end() { return std::rend(c_); }
};


template <typename C>
reverse_wrapper<C> r_wrap(C & c) {
    return reverse_wrapper<C>(c);
}

eg:

int main(int argc, const char * argv[]) {
    std::vector<int> arr{1, 2, 3, 4, 5};
    int arr1[] = {1, 2, 3, 4, 5};

    for (auto i : r_wrap(arr)) {
        printf("%d ", i);
    }
    printf("\n");

    for (auto i : r_wrap(arr1)) {
        printf("%d ", i);
    }
    printf("\n");
    return 0;
}

Answer 7

Got this example from cppreference. It works with:

GCC 10.1+ with flag -std=c++20

#include <ranges>
#include <iostream>
 
int main()
{
    static constexpr auto il = {3, 1, 4, 1, 5, 9};
 
    std::ranges::reverse_view rv {il};
    for (int i : rv)
        std::cout << i << ' ';
 
    std::cout << '\n';
 
    for(int i : il | std::views::reverse)
        std::cout << i << ' ';
}

Answer 8

Sorry but with current C++ (apart from C++20) all these solutions do seem to be inferior to just use index-based for. Nothing here is just "a few lines of code". So, yes: iterate via a simple int-loop. That's the best solution.

Answer 9

If not using C++14, then I find below the simplest solution.

#define METHOD(NAME, ...) auto NAME __VA_ARGS__ -> decltype(m_T.r##NAME) { return m_T.r##NAME; }
template<typename T>
struct Reverse
{
  T& m_T;

  METHOD(begin());
  METHOD(end());
  METHOD(begin(), const);
  METHOD(end(), const);
};
#undef METHOD

template<typename T>
Reverse<T> MakeReverse (T& t) { return Reverse<T>{t}; }

Demo.
It doesn't work for the containers/data-types (like array), which doesn't have begin/rbegin, end/rend functions.

Answer 10

You could simply use BOOST_REVERSE_FOREACH which iterates backwards. For example, the code

#include <iostream>
#include <boost\foreach.hpp>

int main()
{
    int integers[] = { 0, 1, 2, 3, 4 };
    BOOST_REVERSE_FOREACH(auto i, integers)
    {
        std::cout << i << std::endl;
    }
    return 0;
}

generates the following output:

4

3

2

1

0