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?

Whitford

The answer to your question "can I get a reverse_iterator from a forward iterator" is yes and here – Bradstreet

Answer 1

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.

Housebreak

I like your answer. You could be right. I am relatively new to C++ and the STL. And what constitutes good C++ design is something I'm struggling to learn. – Whitford

Although this answer helps BeeBand it doesn't answer the original question for posterity. This answer should instead be a comment to the original post. I would ask BeeBand to consider changing the tick to Mike Seymour's answer. – Erythroblastosis

@Lukasz: If you restrict "the question" to what's in the title, you're right. If you read the whole of the question itself, however, I'd say much less so (at best). – Housebreak

Four years down the road, I'd argue that people find this question because of its title more than because of its contents. – Scarlatti

Another five years later and it's even more so ^ – Tepefy

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.

Nino

(currentbck+1).base() borks when currentbck is an end iterator. Converting between the two is a world of errors waiting to happen. – Rattlesnake

One should not dereference end(). Same logic applies for converting the rend() iterator to a normal iterator. – Brunildabruning

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.

Conveyor

Thanks - I have been using deque's throughout the rest of the app for this very reason. I don't know why I got tunnel vision about iterators :-) – Whitford

That's why you always need a second pair of eyes :) – Conveyor

Beware though: it's quite difficult to test an unsigned integer to know if has reached sub zero value ;) – Pontic

You could use a (forward) iterator, and be careful not to increment it if it's equal to end(), or decrement if equal to end(). And either way, watch for operations which invalidate iterators, since they could also invalidate an index (either because it no longer points to the element you think it does, or because you remove something when the index refers to the end of the deque). – Rattlesnake

Do you mean don't decrement if equal to begin()? Problem with that is, if Advance() does not go to the functional equivalent of rend(), a function like GetCurrentMove() will return begin() when actually all moves have been processed. – Whitford

Yes, that's what I meant, the other thing was nonsense :-). You would have to use a flag to indicate "off the beginning", and special case it everywhere. The trouble is there's no built-in iterator type which can go off both ends of an interval, so GetCurrentMove() doesn't fit nicely with what you're doing. And even an end iterator doesn't point to anything. So you'll have to special-case both ends anyway. Just a suggestion, I don't know whether it will actually work out any better than using an index. – Rattlesnake

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

Pontic

I like this solution and it might be a good learning exercise for me. The reason for storing both iterators is because the "GetCurrentMove() is called from a different place in the app to Advance(). So I need one convenient place to store the "current move". – Whitford

That is normally the role of the iterator, though implementing it as 2 different objects in C++, though it saves some place and mimicks pointer arithmetic, is quite annoying I think. The Iterator above is inspired from Python > a single object maintaining both its current position and the end point. In your application, you don't need to pass the full Action class, you only need to pass the Iterator (or if you were to directly reference the deque iterators, the current position and the end). This way, you promote decoupling :) – Pontic

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.

Asthmatic

Thanks Charles. The problem with going backward is in the Finished() function - I need to knwo when I'm one before the first element ( i.e. have gone past the "rend()" ). – Whitford