How std::reverse_iterator Works in C++

This article explains how the C++ Standard Template Library (STL) implements std::reverse_iterator as an adaptor for bidirectional iterators. It explores the off-by-one design pattern required to map reverse ranges to standard ranges, details the internal mechanics of dereferencing and incrementing, and clarifies how the underlying base iterator interacts with operations like element insertion and deletion.

In C++, std::reverse_iterator is an iterator adaptor that inverts the direction of traversal for any underlying iterator meeting at least the std::bidirectional_iterator requirement. It allows algorithms designed for forward processing to iterate backward through sequences without requiring specialized backward algorithms.

The Off-by-One Relationship

The primary design challenge when reversing a range lies in the asymmetry of standard iterator ranges: ranges are half-open, expressed as [begin, end). The begin iterator points directly to the first valid element, while end points one past the final element.

If a reverse iterator simply stored an underlying iterator pointing to the current element, rbegin() would have to wrap an iterator pointing to the last valid element, and rend() would have to point to one position before the first element. However, in C++, decrementing an iterator past the beginning of a sequence (such as decrementing container.begin()) yields undefined behavior.

To solve this without undefined behavior, std::reverse_iterator maintains the invariant that its logical position corresponds to the element immediately preceding the physical position of the underlying iterator.

  • rbegin() wraps end().
  • rend() wraps begin().
Positions:        [ Element 0 ]   [ Element 1 ]   [ Element 2 ]
Iterators:        ^               ^               ^               ^
                  begin()                                         end()
                                                                  rbegin().base()
Reverse access:                   *rend()         *(rbegin()+1)   *rbegin()

Dereferencing and Movement Operations

Because of this offset, the member operations of std::reverse_iterator translate reverse operations into inverted forward operations on the underlying iterator:

  1. Dereferencing (operator*): When dereferencing a reverse iterator, it does not access the element at the underlying iterator's current position. Instead, it accesses the element prior to it.

    reference operator*() const {
    Iterator temp = current;
    return *--temp;
}

    When dereferencing rbegin() (which wraps end()), the temporary iterator is decremented to the last valid element, safely returning it.

  2. Increment (operator++): Advancing a reverse iterator forward moves the traversal backward in the container. Therefore, prefix increment decrements the wrapped iterator:

    reverse_iterator& operator++() {
    --current;
    return *this;
}

  3. Decrement (operator--): Conversely, moving the reverse iterator backward advances the wrapped iterator:

    reverse_iterator& operator--() {
    ++current;
    return *this;
}

The base() Member Function

The underlying iterator can be extracted using the .base() member function. Due to the shift mechanism, rit.base() does not point to the element that *rit evaluates to; it points to the element immediately following it in forward order.

This distinction is critical when modifying containers:

  • Insertion (insert): Calling container.insert(rit.base(), value) places the new element at the position immediately before rit.base(), which corresponds exactly to the position before rit in the reverse sequence. No manual offset adjustment is needed.

  • Erasure (erase): Passing rit.base() directly to container.erase() erases the element after the element pointed to by the reverse iterator. To erase the element currently referenced by rit, the base iterator must be decremented first:

    container.erase(std::next(rit).base()); // or container.erase(--rit.base());

By decoupling the physical position of the underlying iterator from the logical element accessed, std::reverse_iterator provides reverse navigation across standard ranges safely within the bounds of defined iterator behavior.