Where does rend point to?

Question

To support STL's notion of half-open ranges, we are allowed to point one-past-the-end of an array. Suppose we have a vector of three elements. If std::vector::iterator is implemented as a pointer, as is usually the case in release builds, then begin and end point to these locations:

    +---+---+---+....
    |   |   |   |   .
    +---+---+---+....
      ^           ^
    begin        end

Where the dots denote the one-past-the-end pseudo-element. Since there is no such thing as a one-before-the-beginning, where exactly would rend point to? Let me illustrate:

    +---+---+---+....
    |   |   |   |   .
    +---+---+---+....
  ^           ^
rend       rbegin

Clearly, the illustration is wrong, because rend is an illegal pointer. So I guess the implementation of std::vector::reverse_iterator can never be a pointer, even in release builds.

Am I right? What would be the most efficient way of implementing reverse_iterator then?

Answer 1

The result of rbegin points to the same as end (one past the end), and the result of rend to the same as begin (the first item). When a reverse iterator is dereferenced, it returns a reference to the previous item in the range.

Answer 2

The std::reverse_iterator interface includes a .base member function that retrieves an iterator equal to the original. I suspect that what they usually do is just cache the original iterator, and offset by 1 in the operator* overload.