10.4.3. Reverse Iterators

A reverse iterator is an iterator that traverses a container backward, from the last element toward the first. A reverse iterator inverts the meaning of increment (and decrement). Incrementing (++it) a reverse iterator moves the iterator to the previous element; derementing (--it) moves the iterator to the next element.

The containers, aside from forward_list, all have reverse iterators. We obtain a reverse iterator by calling the rbegin, rend, crbegin, and crend members. These members return reverse iterators to the last element in the container and one “past” (i.e., one before) the beginning of the container. As with ordinary iterators, there are both const and nonconst reverse iterators.

Figure 10.1 illustrates the relationship between these four iterators on a hypothetical vector named vec.

Figure 10.1. Comparing begin/cend and rbegin/crend Iterators

As an example, the following loop prints the elements of vec in reverse order:

vector<int> vec = {0,1,2,3,4,5,6,7,8,9};
// reverse iterator of vector from back to front
for (auto r_iter = vec.crbegin(); // binds r_iter to the last element
          r_iter != vec.crend();  // crend refers 1 before 1st element
          ++r_iter)               // decrements the iterator one element
    cout << *r_iter << endl;      // prints 9, 8, 7,... 0

Although it may seem confusing to have the meaning of the increment and decrement operators reversed, doing so lets us use the algorithms transparently to process a container forward or backward. For example, we can sort our vector in descending order by passing sort a pair of reverse iterators:

sort(vec.begin(), vec.end()); // sorts vec in ''normal'' order
// sorts in reverse: puts the smallest element at the end of vec
sort(vec.rbegin(), vec.rend());

Reverse Iterators Require Decrement Operators

Not surprisingly, we can define a reverse iterator only from an iterator that supports -- as well as ++. After all, the purpose of a reverse iterator is to move the iterator backward through the sequence. Aside from forward_list, the iterators on the standard containers all support decrement as well as increment. However, the stream iterators do not, because it is not possible to move backward through a stream. Therefore, it is not possible to create a reverse iterator from a forward_list or a stream iterator.

Relationship between Reverse Iterators and Other Iterators

Suppose we have a string named line that contains a comma-separated list of words, and we want to print the first word in line. Using find, this task is easy:

// find the first element in a comma-separated list
auto comma = find(line.cbegin(), line.cend(), ','),
cout << string(line.cbegin(), comma) << endl;

If there is a comma in line, then comma refers to that comma; otherwise it is line.cend(). When we print the string from line.cbegin() to comma, we print characters up to the comma, or the entire string if there is no comma.

If we wanted the last word, we can use reverse iterators instead:

// find the last element in a comma-separated list
auto rcomma = find(line.crbegin(), line.crend(), ','),

Because we pass crbegin() and crend(), this call starts with the last character in line and searches backward. When find completes, if there is a comma, then rcomma refers to the last comma in line—that is, it refers to the first comma found in the backward search. If there is no comma, then rcomma is line.crend().

The interesting part comes when we try to print the word we found. The seemingly obvious way

// WRONG: will generate the word in reverse order
cout << string(line.crbegin(), rcomma) << endl;

generates bogus output. For example, had our input been

FIRST,MIDDLE,LAST

then this statement would print TSAL!

Figure 10.2 illustrates the problem: We are using reverse iterators, which process the string backward. Therefore, our output statement prints from crbegin backward through line. Instead, we want to print from rcomma forward to the end of line. However, we can’t use rcomma directly. That iterator is a reverse iterator, which means that it goes backward toward the beginning of the string. What we need to do is transform rcomma back into an ordinary iterator that will go forward through line. We can do so by calling the reverse_iterator’s base member, which gives us its corresponding ordinary iterator:

// ok: get a forward iterator and read to the end of line
cout << string(rcomma.base(), line.cend()) << endl;

Figure 10.2. Relationship between Reverse and Ordinary Iterators

Given the same preceding input, this statement prints LAST as expected.

The objects shown in Figure 10.2 illustrate the relationship between ordinary and reverse iterators. For example, rcomma and rcomma.base() refer to different elements, as do line.crbegin() and line.cend(). These differences are needed to ensure that the range of elements, whether processed forward or backward, is the same.

Technically speaking, the relationship between normal and reverse iterators accommodates the properties of a left-inclusive range (§ 9.2.1, p. 331). The point is that [line.crbegin(), rcomma) and [rcomma.base(), line.cend()) refer to the same elements in line. In order for that to happen, rcomma and rcomma.base() must yield adjacent positions, rather than the same position, as must crbegin() and cend().