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?

Armipotent

A reverse container adapter, sounds interesting, but I think you'll have to write it yourself. We wouldn't have this problem if the Standard committee would hurry up and adapt range based algorithms instead of explicit iterators. – Woofer

@Seth I know I could write it, but that's not the point. If I do write it, it becomes one of those Utility Functions That Don't Belong Anywhere In Particular(tm), so you end up sprinkling your code with the include of a said utility header and shuffle your build system to share it across projects. By this reasoning, we should still use BOOST_FOREACH instead of range-for. And yes, I'm lazy. – Armipotent

@deft_code: "instead of?" Why would you want to get rid of iterator based algorithms? They're much better and less verbose for cases where you don't iterate from begin to end, or for dealing with stream iterators and the like. Range algorithms would be great, but they're really just syntactic sugar (except for the possibility of lazy evaluation) over iterator algorithms. – Inkerman

@Woofer template<typename T> class reverse_adapter { public: reverse_adapter(T& c) : c(c) { } typename T::reverse_iterator begin() { return c.rbegin(); } typename T::reverse_iterator end() { return c.rend(); } private: T& c; }; It can be improved (adding const versions, etc) but it works: vector<int> v {1, 2, 3}; reverse_adapter<decltype(v)> ra; for (auto& i : ra) cout << i; prints 321 – Lepus

@SethCarnegie: And to add a nice functional form: template<typename T> reverse_adapter<T> reverse_adapt_container(T &c) {return reverse_adapter<T>(c);} So then you can just use for(auto &i: reverse_adapt_container(v)) cout << i; to iterate. – Inkerman

Even though range based for loop is defined as iterating consecutively from begin to end, I think semantically it means that the order of operation is not important. – Empathy

@C.R: I don't think it should mean that, because that would make it unavailable as a concise syntax for loops where order does matter. IMO the conciseness is more important/useful than your semantic meaning, but if you don't value the conciseness ofc your style guide can give it whatever implication you want. That's kind of what parallel_for would be for, with an even stronger "I don't care what order" condition, if it were incorporated into the standard in some form. Of course it could have a range-based syntactic sugar too :-) – Painty

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

Edythedythe

I'm just tired of seeing answers pitching boost in one way or another at this point. – Domela

Even if you don't like seeing boost everywhere, for the year 2011, this was a very appropriate answer. – Autobus

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());
}

Spare

Just a report that this works perfectly on clang 3.7.0 with -std=c++14 – Trey

Few lines of code? Forgive me but that is over ten :-) – Highpriced

Actually, it's 5-13, depending on how you count lines : ) The work-arounds should not be there, as they are part of the library. Thanks for reminding me, btw, this answer needs to be updated for recent compiler versions, where all the extra lines are not needed at all. – Spare

I think you forgot forward<T> in your reverse implementation. – Evora

Hm, if you put this in a header, you're using namespace std in a header, which is not a good idea. Or am I missing something? – Bhakti

True, this should be revised to using std::rbeing, std::rend. Updating the answer, thank you. – Spare

Actually, you shouldn't be writing "using <anything>;" at file scope in a header. You could improve the above by moving the using declarations into the function scope for begin() and end(). – Peroxidize

Concerning std::forward, in this implementation of reversion_wrapper we actually want to capture by reference, because it's a thin wrapper. So pure forwarding is not desired. This is in line with c++ iterators, which are also thin and need their container reference to be alive when in use. There could be an implementation of a reversion_decorator, which would need to close over the captured iterable, and we'd need a pure forwarder in that case for copying rvalues, but that sounds troublesome semantics to me. – Spare

@PriksoNAI That doesn't look like -8 lines to me... ;) – Polinski

This seems like its going to fail badly with something like ``` std::vector<int> func(); for(auto && a : reverse(func()) cout << a; ``` Due to reverse() not keeping the return value of func() alive – Tompkins

Correct. As mentioned earlier, the choice of making thin or not wrappers is up to the developer. There is no universal answer for that. – Spare

Why define the begin and end functions as free, instead of inlining them as const member functions of the reversion_wrapper? I mean, what's wrong with less verbose godbolt.org/z/q575nq6Yv ? – Sheilasheilah

@Tompkins It can be fixed by changing reversion_wrapper to T member and then using std::forward in reverse. Then rvalues will be captured by value and lvalues captured by reference. – Cavil

I have a way to put it all in one line, but you'll have to have an ultra-wide monitor to see it. – Eichelberger

c for (int x: reverse(my_container{}) { /* code here is executed after my_container deallocted. */ } – Pung

Answer 3

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

Aquamarine

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

Osteoplastic

Update: The ranges::view namespace has been renamed to ranges::views. So, use ranges::views::reverse. – Gauge

Answer 5

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))
{
    ...
}

Longsome

IIRC adding anything to namespace std is an invitation to epic fail. – Crambo

I'm not sure about the normative meaning of "epic fail", but overloading a function in the std namespace has undefined behavior per 17.6.4.2.1. – Meissen

It's in C++14 apparently, under this name. – Aqualung

@HostileFork Exactly. He's implementing C++14 on a C++11 compiler. That is progress not epic fail. – Techy

@MuhammadAnnaqeeb The unfortunate bit is that doing so collides exactly. You can't compile with both definitions. Plus the compiler is not required to have the definition not be present under C++11 and only appear under C++14 (the spec doesn't say anything about what's not in the std:: namespace, just what is). So this would be a very likely compilation failure under a standards-compliant C++11 compiler... much more likely than if it were some random name that wasn't in C++14! And as pointed out, it's "undefined behavior"...so failing to compile isn't the worst it might do. – Aqualung

I don't add to std for clarity alone. But, this conversation got me thinking. Would it really cause problems if you added std::reverse_iterator only #if __cplusplus >= 201402L? Theoretically it would work fine pre and post 14 right? As long as you perfectly match the new C++14 implementation. Or is there a downside I'm not thinking of? – Ilarrold

@HostileFork There is no name collision, make_reverse_iterator is not in the std namespace, so it won't clash with C++14 version of it. – Longsome

error C2668: 'make_reverse_iterator': ambiguous call to overloaded function - note: could be 'std::reverse_iterator<std::_Vector_const_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>> make_reverse_iterator<std::_Vector_const_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>>(Iterator)' – Proteus

Answer 6

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

Profant

Answer 7

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.

Aker

Index or a simple rbegin()/rend(). – Cauthen

@AlexisWilke yeah, OP mentioned it himself, but actually: agreed! Especially with std::rbegin/std::rend, it can even be used for arrays – Aker

Answer 8

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

Iotacism

can you please explain more detail of your answer ? – Taimi

this is a reverse range-base loop C++11 class tamplate – Iotacism

Answer 9

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

Enfeoff

Do you mean <boost/foreach.hpp> ? – Nonscheduled

Answer 10

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.

Bumgarner

Answer 11

Seems the best you can do right now is use std::for_each:

map< int, int > m = { { 2,4 }, { 3, 6 } };

// Vanilla iterator
for( map<int, int>::reverse_iterator rit = m.rbegin(); rit != m.rend(); ++rit ) {
  printf( "%d %d\n", rit->first, rit->second );
}

// for_each w/ lambda
std::for_each( m.rbegin(), m.rend(), []( pair<const int, int>& p ) {
  printf( "%d %d\n", p.first, p.second );
});

Tantivy

Answer 12

auto solve() {
    vector<int> nums = { 1 , 2, 3 };
    for (auto it : vector(nums.rbegin(),nums.rend())){
        cout << it << ' ';
    }
}

Miscellany

You're copying the whole vector just to iterate in reverse order. This looks short and easy, but with big vectors it's a really bad idea. – Alonzo