How do you iterate backwards through an STL list?

53,846

Solution 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.

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

Solution 3

You probably want the reverse iterators. From memory:

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

Solution 4

As already mentioned by Ferruccio, use reverse_iterator:

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

Solution 5

This should work:

list<DVFGfxObj*>::reverse_iterator iter = m_Objs.rbegin();
for (; iter!= m_Objs.rend(); iter++)
{
}
Share:
53,846
AlanKley
Author by

AlanKley

I'm an Android developer converted from a Windows Stack Desktop developer. I enjoy developing my personal projects using Flutter

Updated on January 01, 2021

Comments

  • AlanKley
    AlanKley almost 3 years

    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?

  • AlanKley
    AlanKley about 15 years
    The documentation for iterator and reverse_iterator are almost the same. an iterator is bidirectional so what's the diff?
  • steffenj
    steffenj about 15 years
    The difference is that you still do "++Iter" to increment the iterator, vs. "--Iter". Or am i wrong?
  • steffenj
    steffenj about 15 years
    it should be "...>::reverse_iterator iter = ..."
  • AlanKley
    AlanKley about 15 years
    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.
  • Anthony Cramp
    Anthony Cramp about 15 years
    Oops, reread your question ... doesn't work on Windows. I tested the code on a Mac as well.
  • Michael Burr
    Michael Burr about 15 years
    @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
  • AlanKley
    AlanKley about 15 years
    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.
  • Jesse Chisholm
    Jesse Chisholm about 10 years
    Not all "forward" iterators are "bidirectional". It depends on the collection class.
  • mmocny
    mmocny about 10 years
    Looking at this again, Probably you want to just initialize with current = --end(); and leave the increment step inside the for loop. This would also guard against empty array which my version above doesn't. I'll leave the original posted for now since I haven't tested.
  • pavon
    pavon over 9 years
    @AlanKey: The main difference is what the end points mean. iterator::begin() reference the first element, iterator::end() references one past the last element, reverse_iterator::rbegin() references the last element, reverse_iterator::rend() references one before the first element. When iterating with a for loop it is convenient to be able to increment one past the end of the collection in whichever direction you are iterating, making reverse_iterator easier to use than going backwards through a bidirectional iterator.
  • Gerrit-K
    Gerrit-K over 9 years
    I don't think that this would work unless you also change your loop condition. Otherwise you'll be missing the first item (cause the loop wont execute if current == begin())
  • mmocny
    mmocny over 9 years
    First line of the for loop does a decrement, so yes it would, I think. Just write a quick test to try it! Anyway, I no longer think this is the nicest way to use this idiom, and some recent tests I ran no longer show a marked speed improvement to reverse iterators under full optimization. However, its worth still noting whats happening under the hood and testing accordingly!
  • Gerrit-K
    Gerrit-K over 9 years
    I intended to comment on your comment, not the answer, but SO removed the @-part. The code in your answer works perfectly fine, however, I agree it might not be the best out there ;) Edit: quick test