Can I convert a reverse iterator to a forward iterator?

Question

I have a class called Action, which is essentially a wrapper around a deque of Move objects.

Because I need to traverse the deque of Moves both forward and backwards, I have a forward iterator and a reverse_iterator as member variables of the class. The reason for this is becuase I need to know when I have gone one past the "end" of the deque, both when I am going forwards or backwards.

The class looks like this:

class Action
{
public:
    SetMoves(std::deque<Move> & dmoves) { _moves = dmoves; }
    void Advance();
    bool Finished() 
    {
        if( bForward )
            return (currentfwd==_moves.end());
        else
            return (currentbck==_moves.rend());
    }
private:
    std::deque<Move> _moves;
    std::deque<Move>::const_iterator currentfwd;
    std::deque<Move>::const_reverse_iterator currentbck;
    bool bForward;
};

The Advance function is as follows:

void Action::Advance
{
    if( bForward)
        currentfwd++;
    else
        currentbck++;
}

My problem is, I want to be able to retrieve an iterator to the current Move object, without needing to query whether I am going forwards or backwards. This means one function returning one type of iterator, but I have two types.

Should I forget returning an iterator, and return a const reference to a Move object instead?

Answer 1

Reverse iterators have a member base() which returns a corresponding forward iterator. Beware that this isn't an iterator that refers to the same object - it actually refers to the next object in the sequence. This is so that rbegin() corresponds with end() and rend() corresponds with begin().

So if you want to return an iterator, then you would do something like

std::deque<Move>::const_iterator Current() const
{
    if (forward)
        return currentfwd;
    else
        return (currentbck+1).base();
}

I would prefer to return a reference, though, and encapsulate all the iteration details inside the class.

Answer 2

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.

Answer 3

Since std::deque is a random access container (same as std::vector) you are much better off using a single integer index into the deque for both traversals.

Answer 4

It seems to me that you actually have two different behavior in the same class.

Notably, it seems that you can only traverse your collection in one order, otherwise if you were to begin the traversal and then change the bforward argument you would end up with quite a strange situation.

Personally, I am all for exposing both iterators (ie, forward begin, end, rbegin and rend).

You could also return a simple Iterator object:

template <class T>
class Iterator
{
public:
  typedef typename T::reference_type reference_type;

  Iterator(T it, T end) : m_it(it), m_end(end) {}

  operator bool() const { return m_it != m_end; }

  reference_type operator*() const { return *m_it; }

  Iterator& operator++() { ++m_it; return *this; }

private:
  T m_it;
  T m_end;
};

template <class T>
Iterator<T> make_iterator(T it, T end) { return Iterator<T>(it,end); }

Then, you can just return this simple object:

class Action
{
public:
  Action(std::deque<Move> const& d): m_deque(d) {} // const& please

  typedef Iterator< std::deque<Move>::iterator > forward_iterator_type;
  typedef Iterator< std::deque<Move>::reverse_iterator > backward_iterator_type;

  forward_iterator_type forward_iterator()
  {
    return make_iterator(m_deque.begin(), m_deque.end());
  }

  backward_iterator_type backward_iterator()
  {
    return make_iterator(m_deque.rbegin(), m_deque.rend());
  }


private:
  std::deque<Move> m_deque;
};

Or if you want to choose dynamically between forward and backward traversal, you could make Iterator a pure virtual interface and having both forward and backward traversal.

But really, I don't really see the point of storing BOTH forward and backward iterator if it appears that you will only use one :/

Answer 5

Maybe you should rethink your choice of container.

Usually you do not need to use reverse iterators to go backward,

currentfwd--

will go backwards, all though it might not work (which i assume you tried) with dequeue.

What you should really do is model your class here as a decorator of dequeue and implement your own Action iterators. That would be what I would do anyway.