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
.
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());
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.
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;
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()
.
The fact that reverse iterators are intended to represent ranges and that these ranges are asymmetric has an important consequence: When we initialize or assign a reverse iterator from a plain iterator, the resulting iterator does not refer to the same element as the original.
Exercise 10.34: Use reverse_iterator
s to print a vector
in reverse order.
Exercise 10.35: Now print the elements in reverse order using ordinary iterators.
Exercise 10.36: Use find
to find the last element in a list
of int
s with value 0.
Exercise 10.37: Given a vector
that has ten elements, copy the elements from positions 3 through 7 in reverse order to a list
.