9

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
Community
  • 1
  • 1
Dan
  • 5,929
  • 6
  • 42
  • 52
  • You mean besides the fact this is Undefined Behavior and will fail/crash in common situations? Try it with an empty `map`. – Mooing Duck Mar 19 '12 at 18:26
  • care to elaborate in an answer? Is the UB decrementing an input iterator or decrementing past the beginning? Is it UB for all containers? – Dan Mar 19 '12 at 19:58
  • Can't decrement an input or output iterator (I forgot that one, good eye), and you also can't decrement past the beginning for any container. – Mooing Duck Mar 19 '12 at 20:30
  • Well that pretty much settles it huh? I edited the question. – Dan Mar 19 '12 at 20:55
  • I just realized you can't use `std::reverse_iterator` on an input or output iterator either, so that's a moot point. But it's still UB to iterate one before the beginning of any container. – Mooing Duck Mar 20 '12 at 00:19
  • 1
    The "can't decrement past the beginning of a container" issue can be easily avoided by doing `for (...; it != begin; ) { --it; ... }`, no? Why mostly dismiss this question on that basis? – jamesdlin Apr 09 '13 at 10:52

2 Answers2

7

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.

Billy ONeal
  • 104,103
  • 58
  • 317
  • 552
  • Good point that there may be some generic algos that will work on reverse_iterators and there may not be a 'reverse' version of that algo for use on regular iterators. For wstring you could use find_last_of, but if it were some other type of container that's not an option. – Dan Dec 07 '09 at 23:09
  • BTW your second std::find() call returns an iterator pointing to '\'' (the apostrophe). This points to the 'a': std::wstring::iterator iter = (std::find(foo.rbegin(), foo.rend(), 'a') + 1).base(); – Dan Dec 07 '09 at 23:10
3

For what it's worth, Scott Meyers' Effective STL recommends that you just stick with a regular ol' iterator (Item 26).

Wesley Petrowski
  • 1,131
  • 7
  • 11
  • 2
    It also says to avoid explicit loops, and `reverse_iterator` is sometimes necessary to accomplish that. Item 26 is talking about explicit loops only. – Billy ONeal Dec 07 '09 at 01:38
  • Also, this implies that the OP's code is fine, when it is in fact, Undefined Behavior (and will fail in common situations) – Mooing Duck Mar 19 '12 at 18:28