Reverse For Loops in C++

Published February 11, 2020

This is a guest post by Carlos Buchart. Carlos is one of the main C++ developers at the Motion Capture Division of STT Systems, author of HeaderFiles (in Spanish) and a Fluent C++ follower.

As we saw when working on dynamic bitsets, it can be useful to traverse a collection backwards, from its last element to its first one.

It would be nice to be able to use C++11 range for loops to iterate backwards. But unfortunately, there is no such reverse range-for: range-for only works forwards.

Let’s see how to traverse a collection backwards by using a range for loop.

In C++20: the `reverse` range adaptor

C++20 will bring ranges to the language, including a range adaptor called std::ranges::views::reverse, or std::views::reverse.

It allows to traverse a collection in reverse order and can be used this way:

for (auto const& x : range | std::views::reverse)
{
    foo(x);
}

Let’s now see how to achieve the same result before C++20.

Reversing a range

The solution shall provide a natural syntax and be as lightweight as possible.

for (auto& x : reverse(range)) {
  foo(x);
}

A first option would be to create a back-to-front copy of the range, but:

It has at least both time and space linear complexity.
It is not compatible (has no effect) in implicitly-sorted containers, such as std::set or std::map.

Another option would be to use reverse iterators instead of making a copy of the range.

A first step to do this is to realise that the following pieces of code are equivalent:

for (auto& x : range) {
  foo(x);
}

and

{
  auto __begin = std::begin(range);
  auto __end = std::end(range) ;
  for ( ; __begin != __end; ++__begin) {
    auto& x = *__begin;
    foo(x);
  }
}

It is easy to see that in order to create the reverse range-for it should be enough to modify the begin and end expressions to use reverse iterators instead. It is worth pointing out that std::begin and std::end will call begin and end members if available.

We can do this by using a wrapper around a reference of the original range:

template<typename T>
class reverse {
private:
  T& iterable_;
public:
  explicit reverse(T& iterable) : iterable_{iterable} {}
  auto begin() const { return std::rbegin(iterable_); }
  auto end() const { return std::rend(iterable_); }
};

Examples of use

The following code shows an example of use in a different context of the original bitset:

template<class M>

void print_map(const M& map)
{
  for (auto pair : map) {
    std::cout << '<' << pair.first << ',' << pair.second << "> ";
  }
  std::cout << ‘\n’;
}

std::map<int, int> twice;
for (int i = 0; i < 10; ++i) {
  twice[i] = 2 * i;
}

print_map(twice);
print_map(reverse(twice));

Output:

<0,0> <1,2> <2,4> <3,6> <4,8> <5,10> <6,12> <7,14> <8,16> <9,18>
<9,18> <8,16> <7,14> <6,12> <5,10> <4,8> <3,6> <2,4> <1,2> <0,0>

The algorithm to increment the dynamic bitset can then be expressed as follows when using the new reverse syntax:

template<class T>
void increment_bitset(T& bits)
{
  for (auto& bit : reverse(bits)) {
    flip(bit);
    if (bit) break;
  }
}

Improvements

One drawback of the reverse class is that, as it makes use of an lvalue reference to the range, it will fail to handle temporary values. Actually, code like this won’t compile at all:

for (auto& x : reverse(create_range())) {
  foo(x);
}

Assuming that create_range returns a range by value.

The solution is to create a copy-version of the wrapper, making use of the move constructor if available (which will also preserve the lightweight requirement):

template<typename T>
class reverse_move {
private:
  T iterable_;
public:
  explicit reverse_move(T&& iterable) : iterable_{std::move(iterable)} {}
  auto begin() const { return std::rbegin(iterable_); }
  auto end() const { return std::rend(iterable_); }
};

for (auto& x : reverse_move(create_range())) {
  foo(x);
}

Each version is mutually exclusive respect the construction argument: reverse cannot be created with an rvalue, and reverse_move cannot be created using an lvalue.

Other alternatives

While the presented solutions do not require any third-party support, it is also true that many projects already have other library dependencies. Following common libraries also provide reverse-ranges: