Can I convert a reverse iterator to a forward iterator?

Question

Hi,

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?

best wishes,

BeeBand

Answer 1

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.

Answer 2

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 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 :/