Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Use a regular iterator to iterate backwards, or struggle with reverse_iterator?

Tags:

c++

iterator

stl

I recently learned about the right way to work with reverse iterators in C++ (specifically when you need to erase one). (See this question and this one.)

This is how you're supposed to do it:

typedef std::vector<int> IV;
for (IV::reverse_iterator rit = iv.rbegin(), rend = iv.rend();
     rit != rend; ++rit)
{
  // Use 'rit' if a reverse_iterator is good enough, e.g.,
  *rit += 10;
  // Use (rit + 1).base() if you need a regular iterator e.g.,
  iv.erase((rit + 1).base());
}

But I think thought this is much better (Don't do this, not standards compliant, as MooingDuck points out):

for (IV::iterator it = iv.end(), begin = iv.begin();
     it-- != begin; )
{
  // Use 'it' for anything you want
  *it += 10;
  iv.erase(it);
}

Cons:

  • You tell me. What's wrong with it?
  • It's not standards compliant, as MooingDuck points out. That pretty much overrules any of the possible advantages below.

Pros:

  • Uses a familiar idiom for reverse for-loops
  • Don't have to remember (or explain) the +1
  • Less typing
  • Works for std::list too: it = il.erase(it);
  • If you erase an element, you don't have to adjust the iterator
  • If you erase, you don't have to recompute the begin iterator
like image 855
Dan Avatar asked Dec 05 '09 20:12

Dan


People also ask

What is reverse iterator?

A reverse iterator is made from a bidirectional, or random access iterator which it keeps as a member which can be accessed through base() . To iterate backwards use rbegin() and rend() as the iterators for the end of the collection, and the start of the collection respectively.

How do you reverse a set iterate?

Approach: To traverse a Set in reverse order, a reverse_iterator can be declared on it and it can be used to traverse the set from the last element to the first element with the help of rbegin() and rend() functions. Get the set. Declare the reverse iterator on this set.

How do you iterate a reverse vector?

So, to iterate over a vector in reverse direction, we can use the reverse_iterator to iterate from end to start. vector provides two functions which returns a reverse_iterator i.e. vector::rend() –> Returns a reverse iterator that points to the virtual element before the start of vector.

What is a forward iterator C++?

Forward iterators are iterators that can be used to access the sequence of elements in a range in the direction that goes from its beginning towards its end. Performing operations on a forward iterator that is dereferenceable never makes its iterator value non-dereferenceable.


1 Answers

The reason for reverse iterators is that the standard algorithms do not know how to iterate over a collection backwards. For example:

#include <string>
#include <algorithm>
std::wstring foo(L"This is a test, with two letter a's involved.");
std::find(foo.begin(), foo.end(), L'a'); // Returns an iterator pointing
                                        // to the first a character.
std::find(foo.rbegin(), foo.rend(), L'a').base()-1; //Returns an iterator
                                                 // pointing to the last A.
std::find(foo.end(), foo.begin(), L'a'); //WRONG!! (Buffer overrun)

Use whichever iterator results in clearer code.

like image 68
Billy ONeal Avatar answered Oct 20 '22 17:10

Billy ONeal