How to Convert a Reverse Iterator to a Forward Iterator

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:

Not storing iterators along with containers
Using algorithms that accept arbitrary iterators
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.

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.

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

How to convert a C++ STL vector iterator to a vector reverse iterator?

Try changing it to for(vector<int>::reverse_iterator r_itr(next(itr)); r_itr != arr.rend(); ++r_itr)

To expand on their working, reverse_iterator is not implemented the same as iterator. The logical and physical address for an iterator are the same but for reverse_iterator, the logical and physical address are not the same. For example: s.end() and s.rbegin() have the same physical address but *s.end() will give you an error but *s.rbegin() will give you the last value of the container s.

The code below will make things clear:

#include <iostream>
#include <set>

using namespace std;

int main()
{
    set<int> S{ 1, 2, 3 };
    
    set<int>::iterator itr = S.find(2);
    cout << *itr << endl;

    set<int>::reverse_iterator r_itr(itr);
    cout << *r_itr << endl;

    cout << itr._Ptr << ' ' << r_itr.base()._Ptr << endl;

    //S.erase(r_itr);       // ERROR!
    S.erase(r_itr.base());

    for (int e : S)
        cout << e << ' ';
}

On my machine, it produced the following output:

2
1
00F85DA8 00F85DA8
1 3

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.

C++ iterator and reverse iterator

You're right that it's an abstraction. The reverse iterator contains a normal iterator that points at the element after the object you would get if you dereferenced it. However, it's not merely an implementation detail. The std::reverse_iterator adapter provides a member function call base which returns the underlying iterator.

The standard defines std::reverse_iterator as an iterator adapter with the following relation to the iterator its adapting:

The fundamental relation between a reverse iterator and its corresponding iterator i is established by the identity: &*(reverse_iterator(i)) == &*(i - 1)

A common use for base is erasing an element from a container, which would be done like so:

it++;
lst.erase(it.base());

If you want to do this while iterating over the container in reverse, you would do:

it++;
std::list<int>::reverse_iterator(lst.erase(it.base()));

Reverse iterate over a std::vector with forward iterators

I may have misunderstood the question, but do you just need:

while (begin != end) {
    --end;
    // do something with *end
}

If you need an iterator that goes backwards, ipc's answer gives you one.

In practice with vector you could probably get away with while (begin != end--), but don't be tempted. It's undefined behavior to decrement an iterator in the case where it's at the start of the vector (i.e. when it's equal to the result of vector::begin()).

This code requires at least a BidirectionalIterator. Fortunately, vector has a RandomAccessIterator, which is even better.

If you genuinely only had a ForwardIterator, then you'd have to iterate over the range and store the iterator values somewhere (like a stack), and then use them in reverse order:

std::stack<Foo::const_iterator> iterators;
while (begin != end) {
    iterators.push(begin);
    ++begin;
}
while (!iterators.empty()) {
    Foo::const_iterator i = iterators.top();
    // do something with *i
    iterators.pop();
}

This code requires at least a ForwardIterator (it will not work with a mere InputIterator).

Get index in vector from reverse iterator

I would use:

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    auto v = std::vector<int> { 1, 2, 3 };
    auto rit = std::find(v.rbegin(), v.rend(), 3);
    if (rit != v.rend()) {
        auto idx = std::distance(begin(v), rit.base()) - 1;
        std::cout << idx;
    } else
        std::cout << "not found!";
}

Live Example.

The reason for the -1 in the distance computation is because of the conversion between reverse and regular iterators in the .base() member:

24.5.1 Reverse iterators [reverse.iterators]

1 Class template reverse_iterator is an iterator adaptor that iterates
from the end of the sequence defined by its underlying iterator to the
beginning of that sequence. The fundamental relation between a reverse
iterator and its corresponding iterator i is established by the
identity: &*(reverse_iterator(i)) == &*(i - 1).

Note: you could also use the above code without the check for v.rend(), and use the convention that idx == -1 is equivalent to an element that is not found. However, that loses the ability to do v[idx], so eventually you would need a check against that as well.

C++ map erase using forward and reverse iterators

First of all, let me reiterate LogicStuff's comment: You should really try to pass in compatible iterators instead.

If you really, really, really have no alternative to doing it the way you are doing it right now, you could use some template functions:

#include <vector>
#include <iostream>

// Used when both iterators have the same type
template <typename T>
void foo(T begin, T end)
{
  for (; begin != end; ++begin)
  {
    std::cout << " " << *begin;
  }
}

// Overload for a forward begin and reverse end
template <typename T>
void foo(T begin, std::reverse_iterator<T> end)
{
  foo(begin, end.base());
}

// Overload for a reverse begin and forward end
template <typename T>
void foo(std::reverse_iterator<T> begin, T end)
{
  foo(begin, std::reverse_iterator<T>(end));
}

int main()
{
  std::vector<int> v { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  foo(v.begin(), v.end()); std::cout << std::endl;
  foo(v.begin(), v.rbegin()); std::cout << std::endl;
  foo(v.rbegin(), v.begin()); std::cout << std::endl;
  foo(v.rbegin(), v.rend()); std::cout << std::endl;
}

See it running on ideone.

Here I convert reverse iterators to forward iterators. This SO post gives you more details about that. But read that post very carefully, there be dragons. My example above just outputs numbers and does not modify the underlying container. And I do not check the validity of the iterators, nor do I do any bounds checking. For your own case, make sure you test all the edge cases (either iterator being at or beyond the beginning/end of your container; off-by-one errors, etc.).

Also, note that in your example code, the call to erase() invalidates the iterator, so you should write the loop body like this:

if (cond) {
  // guarantees to return an iterator to the element following
  // the erased element.
  start = m.erase(start);
} else {
  ++start;
}

Edit: If you require that iterators are always converted to their forward equivalents, you can change the last overload and add another:

template <typename T>
void foo(std::reverse_iterator<T> begin, T end)
{
  foo(end, begin.base()); // Note: order of iteration reversed!
}

template <typename T>
void foo(std::reverse_iterator<T> begin, std::reverse_iterator<T> end)
{
  foo(end.base(), begin.base()); // Note: order of iteration reversed!
}

But be aware that the order of iteration is now reversed: in my example, calling foo(v.rbegin(), v.rend()) printed 9 8 7 ... 1 in the first incarnation, and now it prints 1 2 3 ... 9. Example here.

And again, you'd be off much better if you could feed in compatible iterators instead.