Where does rend point to?

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:

    +---+---+---+....
    |   |   |   |   .
    +---+---+---+....
      ^           ^
    b开发者_JAVA百科egin        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?

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.

Because you're not permitted to dereference an iterator that points outside the container, it doesn't actually matter what rend() "points" to. It doesn't have to be a legal pointer value, it can be any value that has a particular meaning to the container/iterator type.

There is a difference between what a reverse_iterator points to logically and what its contained iterator points to. Logically, rbegin yields an iterator that points to the last element of the sequence and rend yields an iterator that points to one element before the start. But this is usually implemented with a base iterator which points to the next location after the location the reverse iterator is pointing to. Something like this:

template<class Iter>
class reverse_iter
{
    Iter base;
public:
    explicit reverse_iter(Iter it) : base(it) {}

    reference operator*() const {
        Iter tmp = base;
        --tmp;
        return *tmp;
    }

    reverse_iter& operator++() {--base; return *this;}
};

So, if you initialize such a reverse_iter<> object with container.end(), the base iterator points one past the end, but dereferencing the reverse iterator will give you the last element. No harm done.

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.

The other answers answer the question well.

But I also wonder if it would be legal anyway, as presumably an implementation can do whatever it likes behind the scenes as long as it works and meets the standards. If it chooses to implement the iterator as a pointer and chooses to dereference that then it's the compilers responsibility to know that that will work. You wouldn't be able to implement it this way yourself but it seems to me that the compiler author has special license to do this as they know what the undefined behavour will be, and don't expose that behavour to you directly, just through an iterator interface.