Get a Reverse Iterator from a Forward Iterator Without Knowing the Value Type

Get a reverse iterator from a forward iterator without knowing the value type

The STL has std::reverse_iterator<Iterator>:

template <class RandomAccessIterator>
void mySort(RandomAccessIterator first, RandomAccessIterator last) 
{
  typedef std::reverse_iterator<RandomAccessIterator> RIter;
  RIter riter(last);
  RIter rend(first);
  for ( ; riter != rend; ++riter) {
    // Do stuff
  }
}

An important note:

Notice however that when an iterator
is reversed, the reversed version does
not point to the same element in the
range, but to the one preceding it.
This is so, in order to arrange for
the past-the-end element of a range:
An iterator pointing to a past-the-end
element in a range, when reversed, is
changed to point to the last element
(not past it) of the range (this would
be the first element of the range if
reversed). And if an iterator to the
first element in a range is reversed,
the reversed iterator points to the
element before the first element (this
would be the past-the-end element of
the range if reversed).

Can I convert a reverse iterator to a forward iterator?

This is exactly the sort of problem that prompted the design of STL to start with. There are real reasons for:

1. Not storing iterators along with containers
2. Using algorithms that accept arbitrary iterators
3. Having algorithms evaluate an entire range instead of a single item at a time

I suspect what you're seeing right now is more or less the tip of the iceberg of the real problems. My advice would be to take a step back, and instead of asking about how to deal with the details of the design as it currently stands, ask a somewhat more general question about what you're trying to accomplish, and how best to accomplish that end result.

For those who care primarily about the question in the title, the answer is a heavily qualified "yes". In particular, a reverse_iterator has a base() member to do that. The qualifications are somewhat problematic though.

The demonstrate the problem, consider code like this:

#include <iostream>
#include <vector>
#include <iterator>

int main() { 
    int i[] = { 1, 2, 3, 4};
    std::vector<int> numbers(i, i+4);

    std::cout << *numbers.rbegin() << "\n";
    std::cout << *numbers.rbegin().base() << "\n";
    std::cout << *(numbers.rbegin()+1).base() << "\n";

    std::cout << *numbers.rend() << "\n";
    std::cout << *numbers.rend().base() << "\n";
    std::cout << *(numbers.rend()+1).base() << "\n";
}

Running this at this particular moment on my particular machine produces the following output:

4
0
4
-1879048016
1
-1879048016

Summary: with rbegin() we must add one before converting to a forward iterator to get an iterator that's valid -- but with rend() we must not add one before converting to get a valid iterator.

As long as you're using X.rbegin() and X.rend() as the parameters to a generic algorithm, that's fine--but experience indicates that converting to forward iterators often leads to problems.

In the end, however, for the body of the question (as opposed to the title), the answer is pretty much as given above: the problem stems from trying to create an object that combines the collection with a couple of iterators into that collection. Fix that problem, and the whole business with forward and reverse iterators becomes moot.

Check whether a reverse iterator has crossed forward iterator or not

The code:

std::vector<int> test_vector{0, 1, 2, 3};
std::vector<int>::iterator left_it = test_vector.begin();
std::vector<int>::reverse_iterator right_it = test_vector.rbegin();
while (std::distance(left_it, right_it.base() - 1) > 0) {
  ++left_it;
  ++right_it;
}
std::cout << "Iterators crossed" << std::endl;
std::cout << "*left_it = " << *left_it << ", *right_it = " << *right_it << std::endl;

Output:

Iterators crossed
*left_it = 2, *right_it = 1

We use std::distance in combination with std::reverse_iterator::base() to determine the relative positions of the two iterators. If the distance is zero, the iterators have reached the same element; if the distance is negative, they have crossed.

(Note: the negative case requires C++11 or later, calling std::distance with the first parameter "after" the second was undefined behavior before C++11).

---

Explanation:

In order to get a basis on which to compare reverse iterators to forward iterators, we need to use the std::reverse_iterator::base() function. However, due to an implementation trick (see below for why) used by reverse iterators, this gives you a result that's one element to the right of what you might expect.

To demonstrate briefly, we can iterate through a vector and check the offset of the current address from the address of the vector's first element. First forwards, we have:

std::vector<int> test_vector{0, 1, 2, 3};
for (auto it = test_vector.begin(); it != test_vector.end(); ++it) {
  std::cout << &*it - &test_vector.front() << " ";
}

which outputs the following as expected.

0 1 2 3

If we go backwards, the output is reversed:

for (auto rit = test_vector.rbegin(); rit != test_vector.rend(); ++rit) {
  std::cout << &*rit - &test_vector.front() << " ";
}

yields

3 2 1 0

However, if we check the address of the std::reverse_iterator::base() iterator instead, we see something different:

for (auto rit = test_vector.rbegin(); rit != test_vector.rend(); ++rit) {
  std::cout << &*rit.base() - &test_vector.front() << " ";
}

yields

4 3 2 1

So, we need to subtract 1 from the address of the .base() iterator to get the correct corresponding forwards iterator. This is confirmed by the line from the documentation given below (however, I found their explanation unclear and difficult to grasp, which is why I decided to experiment tangibly):

That is &*(rit.base() - 1) == &*rit.

I couldn't possibly summarize this better than Mankarse's comment does:

A simple way of thinking about iterators is that they are cursors at
positions between elements. A forwards iterator will produce the
element after the cursor when dereferenced, a reverse iterator will
produce the element before the cursor when dereferenced. Equivalent
forwards and reverse iterators are cursors that are at the same
position.

---

Why off by one?

It may seem strange to you that reverse iterators have this innate off-by-1 discrepancy. It seems as though when a reverse iterator is at position i, it's actually pointing to the element at position i-1, i.e. the element before i.

There's an innate asymmetry in iterators that can explain this. Consider forward iterators: what are the "earliest" and "latest" iterators we can have?

The earliest iterator is the iterator pointing to the first element, while the latest iterator points after the last element of the collection.

When we iterate in reverse, we need this same functionality in reverse. Our earliest reverse iterator should point directly to the last element, and our latest reverse iterator must point before the first element (or from a reversed perspective, after the first element). These are the basic semantics that allow us to iterate through the collection and know when we have visited every element.

We now see the natural correspondence between the forward and reverse views induces this off-by-one effect. If we envision our collection sequenced from left to right, the last element lies at the second to rightmost position visited in forwards order but the rightmost position visited in reverse order. However, the first element lies at the leftmost position in forwards order and the second to leftmost position in reverse order.

Here is a concrete example. When our reverse iterator's base corresponds to position 0, that indicates it has already gone past the beginning (or the reverse end) and is done iterating. So it points to the element at position 0
one step earlier, which occurs when its base is at position 1. However, the forward iterator simply references the element at position 0 when it is at position 0.

Getting a vector::reverse_iterator from a vector::iterator?

You can construct a reverse iterator from an iterator. The important thing to remember is that when you do that it goes back one element when doing so. If you do:

std::vector<int>::reverse_iterator rit(foo.begin());

foo.begin points at the first element where rit will point to one before the first element. With that you for loop could become

std::vector<int> tab {1, 2, 3, 4, 5, 6, 7}; // C++11 needed here, if I recall correctly

for(std::vector<int>::iterator i(tab.begin()) ; i != tab.end() ; ++i) {
    for(std::vector<int>::reverse iterator j(i + 1) ; j != tab.rend() ; ++j) {
        std::cout << *j;
    }
    std::cout << std::endl;
}

Is there any iterator wrapper for forward and reverse iterators?

The following function incrementMax is a generic solution with C++14 and over.
This function increments the first one of ...args storing the maximum value.

This function first generates value array values of f(*iterator)s and then find the position idx corresponding to the maximum value.
The function increment increments the iterator specified by it.
This function uses the array arr of the void function increment_impl and calls the index-th one of it:

template<int N, class Tuple>
void increment_impl(Tuple& t)
{
    ++std::get<N>(t);
}

template<class Tuple, std::size_t... Is>
void increment(Tuple& t, std::size_t index, std::index_sequence<Is...>)
{
    using void_f = void(*)(Tuple&);
    static constexpr void_f arr[] = { &increment_impl<Is, Tuple>... };

    arr[index](t);
}

template<class F, class ...Args>
void incrementMax(F f, Args& ...args)
{
    const auto values = { f(*args)... };
    const auto it = std::max_element(std::begin(values), std::end(values));
    const auto idx = std::distance(std::begin(values), it);

    auto t = std::forward_as_tuple(args...);
    increment(t, idx, std::make_index_sequence<sizeof...(Args)>{});
}

This is an usage example:

DEMO

DEMO (6 elements case)

struct S
{
    int x;
};

int main()
{
    std::vector<S> v = {{1}, {2}, {3}, {4}, {5}};
    auto forward1 = v.begin();    // 1
    auto forward2 = forward1+1;   // 2
    auto reverse1 = v.rbegin()+1; // 4, maximum
    auto reverse2 = v.rbegin()+2; // 3

    // 1243
    std::cout << forward1->x << forward2->x << reverse1->x << reverse2->x << std::endl;    

    // do ++reverse1;
    incrementMax([](const S& s){ return s.x; }, forward1, forward2, reverse1, reverse2);

    // 1233
    std::cout << forward1->x << forward2->x << reverse1->x << reverse2->x << std::endl;    

    return 0;
}

Can reverse iterators be used in place of forward iterator parameters?

You know what, reverse-iterators can be forward-iterators too!

Specifically, the term reverse-iterator means that they go reverse to the "natural" direction.

The term forward-iterator names a concept, which guarantees among others that you can make a copy of an iterator, and copy and original can be independently used to iterate the sequence, and look at the elements, however often you want.

Take a good look at it, and you will see that while both are based on the concept iterator, and while they add different additional requirements, those are not contradictory.

Actually, whenever you have a reverse-iterator, they are normally automatically derived by decorating a bidirectional iterator (which is a forward-iterator), though that is not quite a requirement.

Why can I not convert a reverse iterator to a forward iterator?

You could write a helper function. One particularity of reverse_iterator is that base() gives a forward iterator that is next from the value that the reverse iterator dereferences to. This is because a reverse iterator physically points to the element after the one it logically points to. So to have the forward iterator to the same item as your reverse_iterator, you'll need to decrement the result of base() by one, or you could increment the reverse iterator first, then take the .base() of that.

Both examples are shown below:

#include <iostream>
#include <vector>
#include <iterator>

//result is undefined if passed container.rend()
template <class ReverseIterator>
typename ReverseIterator::iterator_type make_forward(ReverseIterator rit)
{
    return --(rit.base()); // move result of .base() back by one.
    // alternatively
    // return (++rit).base() ;
    // or
    // return (rit+1).base().
}

int main()
{
    std::vector<int> vec(1, 1);
    std::vector<int>::reverse_iterator rit = vec.rbegin();
    std::vector<int>::iterator fit = make_forward(rit);
    std::cout << *fit << ' ' << *rit << '\n';
} 

Warning: this behavior is different from that of the reverse_iterator(iterator) constructor.

---

Related Topics