How C++ Reverse Iterators Represent Boundaries
Last week, we noted that we can use pointers to represent boundaries by taking the view that a pointer has the same representation as the boundary immediately preceding it, and by implication, that a boundary has the same representation as the pointer immediately following it. Let's continue by looking more closely at how these representations interact with reverse iterators.
c is a container. Then we can access
c's elements in order by writing
for (auto it = c.begin(), it != c.end(); ++it) // access the element at *it
We can also access
c's elements in reverse order by writing
for (auto rt = c.rbegin(), rt != c.rend(); ++rt) // access the element at *it
rt must have different types. If nothing else, giving them different types makes it possible for
++it to move
it to the next element to the right, and for
--rt to move
rt to the next element to the left. No problem so far.
Where things get interesting is when we think about the value of
c.rbegin(). Surely we would like that value to be the same as what we get when we convert
c.end() to a reverse iterator. However,
c.end() is an off-the-end iterator, which means that it does not refer to an element. In contrast, unless
c is empty,
c.rbegin() most definitely does refer to an element, namely the rightmost one! The implication seems to be that when we convert an iterator into the corresponding reverse iterator, we change the element to which the iterator refers.
How can such a design make sense? Surely an iterator should refer to the same element of a container regardless of the direction in which we are processing the container's elements!
Well — of course, it shouldn't; otherwise, I wouldn't have bothered to raise your expectations with that remark. The missing link is that when we think about iterators and directions together, we should be thinking about ranges, and when we think about ranges, we should be thinking about boundaries, not pointers.
c.end() iterators do not exist in isolation; they work together to represent a range. When we think of them in that way,
c.begin() really represents the boundary immediately to the left of the first element of
c.end() represents the boundary immediately to the right of
c's last element. When we write
c.rbegin(), we intend it to represent the same boundary — not necessarily the same element — as
c.end(). In order to represent that boundary as a pointer, we want to use a pointer to the element immediately after the boundary, just as we do for
c.begin(). Because we are now traversing
c right to left, that element that we use to represent
c.rbegin() is the one to the left of the boundary.
In short, although it may seem odd for
c.rend() to refer to different positions in a container, and similarly, for
c.end() to refer to different positions, this difference makes it possible for the
c.end() pair to refer to the same range of elements as the
c.rend() pair, albeit in the opposite order.
Next week, we'll look at some concrete examples of how to intermix iterators and reverse iterators, with an eye toward explaining why these forward/backward conversions are less confusing than they appear at first glance.