How do you iterate backwards through an STL list?

Question

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?

Answer 1

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.

Answer 2

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()!