-- v.begin()            -- v.end()
      |                       |
      v                       v
     --- --- --- --- --- ---  -  
    | o | o | o | o | o | o | x |
     --- --- --- --- --- ---  -  

  -  --- --- --- --- --- --- 
| x | o | o | o | o | o | o |
  -  --- --- --- --- --- --- 
  ^                       ^
  |                       |
   -- v.rend()             -- v.rbegin()

(ASCII copied, and edited, from this answer, which is actually prompted me to ask the present question.)

I do see the advantage of having that &*rit == &*(rit.base() - 1), because this way I can take the rit.base() for any reverse iterator rit and I'll always get a valid iterator.

But at the same time

• I cannot dereference v.rbegin().base(); I have to remember subtracting 1 first, *(v.rbegin().base() - 1),
• and I cannot dereference v.rend().base() - 1 exactly because I can't dereference v.rend() .

What if the design was that &*rit == &*rit.base()?

• We couldn't call v.rend().base(), true, but that simply corresponds to not being able to dereference v.rend().base() - 1 in the current design;
• We wouldn't be able to get v.end() directly from a reverse iterator, not even the closest one, b.rbegin(), but that simply to the - 1 we have to add to rit.base() in the current design to get a forward iterator to the same element as the reverse.

What I mean is that it seems to me that whether the design decision was that &*rit == &*(rit.base() - 1) (as it was) or that &*rit == &*rit.base(), we'd have had the same amount of convenience

• rit.base() is always ok in the actual design,
• - 1 is not generally needed in the alternative design

and inconvenience

• can't dereference all valid rit.base()s in the actual design,
• need to 1 v.rbegin() to get v.end() in the alternative design,

just in opposite situations.

So my question is: is there a definitive advantage in making the choice that has indeed been made? Or was it just a flipped coin?

CodePudding user response：

It is not a design decision, it is a necessity.

A reverse iterator is not a magical thing that is somehow able to iterate a range in reverse. It is a facade that builds on top of things that are already present.

When you have a collection with 6 entries (like in your picture), then all you have is exactly 7 usable iterator values, nothing more (6 are dereferencable, one is the end iterator value). That is all that the reverse iterator can build on.

Since there is no one-before-the-beginning iterator (like the second picture makes one think), there is no other option for the reverse iterator than to map rbegin() to end() and rend() to begin(). That is, you have (rbegin() i).base() == end() - i

That, in turn, necessitates that the dereferencable iterators (the first 6 starting at rbegin()) must actually dereference iterator .base()-1. There is no other way to implement a reverse iterator.

CodePudding user response：

In the current design, all of this works as expected:

std::make_reverse_iterator(it).base() == it;
auto rbegin = std::make_reverse_iterator(end);
auto rend   = std::make_reverse_iterator(begin);

In your alternative design, it wouldn't be possible for all of them to hold. If base &*rit == &*rit.base() then

• either you must construct with an offset:

  auto last      = std::prev(end)
  auto rbegin    = std::make_reverse_iterator(last);
  auto pastbegin = std::prev(begin);         // not allowed!
  auto rend      = std::make_reverse_iterator(pastbegin);
  

  This would require introducing the concept of iterator to "before first element" which doesn't exist. std::prev(begin) isn't allowed in the current design, and allowing it would make it impossible to have reverse iterators for arrays whose iterators are pointers, because the language prohibits creation of pointers before the first element.

• or you must offset after construction

  auto rpastbegin = std::make_reverse_iterator(end);
  auto rbegin     = std::next(rpastbegin);
  auto rlast      = std::make_reverse_iterator(begin);
  auto rend       = std::next(rlast);
  

  This approach requires introduction of past begin only for reverse iterators. Since they aren't pointers, that might be possible in theory, but this would necessitate extra overhead to represent more iterator states than the base iterator has.

  Neither alternative is particularly convenient to use.