18

The documentation for boost's specialized iterator adaptors states that boost::reverse_iterator "Corrects many of the shortcomings of C++98's std::reverse_iterator."

What are these shortcomings? I can't seem to find a description of these shortcomings.

FOLLOW-UP QUESTION:

How does boost::reverse_iterator correct these shortcomings?

Emile Cormier
  • 28,391
  • 15
  • 94
  • 122
  • 1
    It was often a little.....premature. – Edward Strange Jul 08 '10 at 20:27
  • Posting as a comment since I'm just guessing: Early implementations of `std::reverse_iterator<>` sometimes had bugs. Boost may have been simply trying to insulate against that situation. Maybe the comment is more about shortcomings in `reverse_iterator` implementations rather than shortcomings in the standard? – Michael Burr Jul 08 '10 at 20:52

1 Answers1

11

Well, the big problem is that they're not forward iterators, and there's stuff that pretty much expect forward iterators. So, you have to do some funny conversions to get things to work. To name some issues

  1. Some versions of erase() and insert() require iterators rather than reverse iterators. That means that if you're using a reverse iterators and you want to insert() or erase(), you're going to have to use the reverse iterator's base() function to get your hands on a forward iterator. There is no automatic conversion.

  2. base() returns the forward iterator equivalent to the reverse iterator in terms of insertion. That is, insert inserts in front of the current element. The element that the reverse iterator is pointing at, therefore, would be the wrong element to be pointing at if base() gave you an iterator that pointed at the same element. So, it points one forward, and you can use it for insertion.

  3. Because base() returns an iterator pointing at a different element, it's the wrong element to use for erase(). If you called erase() on the iterator from base(), you'd erase one element forward in the container from the element that the reverse iterator points at, so you have to increment the reverse iterator before calling base() in order to get the correct forward iterator to use for erase().

  4. Whether you can even use base() with erase() to correctly erase an element depends entirely on your implementation. It works with gcc, but with Visual Studio they're really just wrapping a forward iterator in a manner that makes it so that it doesn't work to use erase() when dealing with reverse iterators and Visual Studio. I don't recall whether insert() has the same problem, but reverse iterators don't work the same between different implementations of C++ (according to the Visual Studio guys, the standard wasn't clear enough), so it can be kind of hairy to use them for anything other than simply iterating over a container.

There are probably other issues as well, but dealing with any type of iterator other than a non-const, forward iterator in C++ when doing anything other than simply iterating over a container can get a bit hairy - if you can even do it all - because so many functions require non-const forward iterators rather than any other kind of iterator.

If you really want to know the differences between the various iterator types and the issues associated with them, I recommend reading Scott Meyer's Effective STL. It has a great chapter on iterators.

EDIT: As for how Boost's reverse iterator corrects those shortcomings, I'm afraid that I don't have a clue. I'm aware of some of the standard reverse iterator's shortcomings and have been bitten by them in the past, but I've never used Boost much, so I'm not familiar with their reverse iterators at all. Sorry.

Jonathan M Davis
  • 37,181
  • 17
  • 72
  • 102
  • 1
    I'm not sure I see what you're getting at. Code that "expects" forward iterators shouldn't "notice" any difference unless they do things with undefined behavior... – Cogwheel Jul 08 '10 at 20:31
  • 1
    The `std::reverse_iterator` template in C++03 exposes the same category of iterator as the underlying iterator which must be at least a bi-directional iterator, so a reverse_iterator is always at least a bi-di iterator (and hence a forward iterator). – CB Bailey Jul 08 '10 at 20:35
  • 1
    I don't believe you're correct here. I believe that a reverse_iterator is, indeed, a forward iterator. At least I don't see where it violates that concept. – Edward Strange Jul 08 '10 at 20:35
  • A `std::reverse_iterator<>` belongs to the `iterator_category` that it's templated on (as does `boost::reverse_iterator<>`). At least the 2003 standard says so (maybe C++98 forgot this - I don't have my PDF handy...). – Michael Burr Jul 08 '10 at 20:41
  • 3
    Which of the issues that you've described are 'solved' or different for `boost::reverse_iterator`? As far as I could tell from `boost::reverse_iterator` documentation the behaviour of `base()` (and `operator*()`) is the same as for `std::reverse_iterator`. – CB Bailey Jul 08 '10 at 20:48
  • 1
    Please see my follow-up question. – Emile Cormier Jul 08 '10 at 20:50