views:

2494

answers:

5

I'm writing some cross-platform code between Windows and Mac.

If list::end() "returns an iterator that addresses the location succeeding the last element in a list" and can be checked when traversing a list forward, what is the best way to traverse backwards?

This code workson the Mac but not on Windows (can't decrement beyond first element):

list<DVFGfxObj*>::iterator iter = m_Objs.end();
for (iter--; iter!=m_Objs.end(); iter--)// By accident discovered that the iterator is circular ?
{
}

this works on Windows:

list<DVFGfxObj*>::iterator iter = m_Objs.end();
    do{
        iter--;
    } while (*iter != *m_Objs.begin());

Is there another way to traverse backward that could be implemented in a for loop?

+24  A: 

Use reverse_iterator instead of iterator. Use rbegin() & rend() instead of begin() & end().

Another possibility, if you like using the BOOST_FOREACH macro is to use the BOOST_REVERSE_FOREACH macro introduced in Boost 1.36.0.

Ferruccio
The documentation for iterator and reverse_iterator are almost the same. an iterator is bidirectional so what's the diff?
AlanKley
The difference is that you still do "++Iter" to increment the iterator, vs. "--Iter". Or am i wrong?
steffenj
No, you're right which is a little odd to increment to go backwards but also makes sense. Though the reverse_iterator seems unnecessary given that iterator is bidirectional. The docs for reverse_iterator says it acts on a reversed list; surely it doesn't reverse the list internaly first.
AlanKley
@AlanKey: If you know you're dealing with a list, you might just want to decrement the normal iterator. Reverse iterators come into their own when you're writing generic code - it doesn't need to do anything special to go through a collection backwards - it just needs to be given reverse iterators
Michael Burr
Yes Mike, decrementing the normal iterator was my first approach as illustrated in my two examples. Using that method I wasn't sure the best way to test for the beginning of the list. The behavior proved different between Windows and Mac.
AlanKley
+3  A: 

You probably want the reverse iterators. From memory:

list<DVFGfxObj*>::reverse_iterator iter = m_Objs.rbegin();
for( ; iter != m_Objs.rend(); ++iter)
{
}
Anthony Cramp
Thanks that sounds good. But also seems a waste to create a special reverse_iterator when iterator is suppose to be bi-directional
AlanKley
it should be "...>::reverse_iterator iter = ..."
steffenj
@AlanKley I think the for loop you've put in your question is fine. The reason why I think it works is because the .end() member function returns a sentinel value that is assigned as the value of the next pointer from the last element and also the prev pointer on the first element.
Anthony Cramp
Oops, reread your question ... doesn't work on Windows. I tested the code on a Mac as well.
Anthony Cramp
+2  A: 

As already mentioned by Ferruccio, use reverse_iterator:

for (std::list<int>::reverse_iterator i = s.rbegin(); i != s.rend(); ++i)
ejgottl
+3  A: 

This should work:

list<DVFGfxObj*>::reverse_iterator iter = m_Objs.rbegin();
for (; iter!= m_Objs.rend(); iter++)
{
}
steffenj
+2  A: 

The best/easiest way to reverse iterate a list is (as already stated) to use reverse iterators rbegin/rend.

However, I did want to mention that reverse iterators are implemented storing the "current" iterator position off-by-one (at least on the GNU implementation of the standard library).

This is done to simplify the implementation, in order for the range in reverse to have the same semantics as a range forward [begin, end) and [rbegin, rend)

What this means is that dereferencing an iterator involves creating a new temporary, and then decrementing it, each and every time:

  reference
  operator*() const
  {
_Iterator __tmp = current;
return *--__tmp;
  }

Thus, *dereferencing a reverse_iterator is slower than an normal iterator.*

However, You can instead use the regular bidirectional iterators to simulate reverse iteration yourself, avoiding this overhead:

for ( iterator current = end() ; current != begin() ; /* Do nothing */ )
{
    --current; // Unfortunately, you now need this here
    /* Do work */
    cout << *current << endl;
}

Testing showed this solution to be ~5 times faster for each dereference used in the body of the loop.

Note: Testing was not done with the code above, as that std::cout would have been the bottleneck.

Also Note: the 'wall clock time' difference was ~5 seconds with a std::list size of 10 million elements. So, realistically, unless the size of your data is that large, just stick to rbegin() rend()!

michalmocny