How does std::reverse_iterator hold one before begin?

Question

This is a code example using std::reverse_iterator:

template<typename T, size_t SIZE>
class Stack {
    T arr[SIZE];
    size_t pos = 0;
public:
    T pop() {
        return arr[--pos];
    }
    Stack& push(const T& t) {
        arr[pos++] = t;
        return *this;
    }
    auto begin() {
        return std::reverse_iterator(arr+pos);
    }
    auto end() {
        return std::reverse_iterator(arr);
                // ^ does reverse_iterator take this `one back`? how?
    }
};

int main() {
    Stack<int, 4> s;
    s.push(5).push(15).push(25).push(35);
    for(int val: s) {
        std::cout << val << ' ';
    }
}

// output is as expected: 35 25 15 5 

---

When using std::reverse_iterator as an adaptor for another iterator, the newly adapted end shall be one before the original begin. However calling std::prev on begin is UB.

How does std::reverse_iterator hold one before begin?

Answer 1

Initialization of std::reverse_iterator from an iterator does not decrease the iterator upon initialization, as it would then be UB when sending begin to it (one cannot assume that std::prev(begin) is a valid call).

The trick is simple, std::reverse_iterator holds the original iterator passed to it, without modifying it. Only when it is being dereferenced it peeks back to the actual value. So in a way the iterator is pointing inside to the next element, from which it can get the current.

It would look something like:

// partial possible implementation of reverse_iterator for demo purpose
template<typename Itr>
class reverse_iterator {
    Itr itr;
public:
    constexpr explicit reverse_iterator(Itr itr): itr(itr) {}

    constexpr auto& operator*() {
        return *std::prev(itr); // <== only here we peek back
    }
    constexpr auto& operator++() {
        --itr;
        return *this;
    }
    friend bool operator!=(reverse_iterator<Itr> a, reverse_iterator<Itr> b) {
        return a.itr != b.itr;
    }
};

This is however an internal implementation detail (and can be in fact implemented in other similar manners). The user of std::reverse_iterator shall not be concerned with how it is implemented.