 Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726. # How To Use Reverse Iterators Without Getting Confused

July 10, 2014

We shall continue last week's discussion by looking at a concrete example of how to use reverse iterators.

Suppose that `b` and `e` are iterators that represent a sequence of characters. These characters might be part of a `string`, or a `vector<char>`, or `list<char>`, or some other kind of container entirely. Our goal is to initialize two more iterators, which we shall call `b1` and `e1`, that will represent the same sequence as `b` and `e`, except with leading and trailing blanks removed.

To simplify our task, we'll write a little predicate function:

```
bool nonblank(char c) { return c != ' '; }
```

This function accepts a character; it returns `false` if that character is blank and `true` otherwise. There are other, more direct ways of solving this subproblem, but this one has the advantage of being obvious, and therefore of not distracting us from the problem at hand.

Given this nonblank function, it is trivial to obtain an appropriate value for `b1`:

```
auto b1 = find_if(b, e, nonblank);
```

This statement calls the library algorithm `find_if`, which does exactly what we want: It finds the first (i.e., leftmost) value in the range defined by `b` and `e` for which nonblank yields a nonzero value. If there is no such value — in other words, if the range is empty or consists entirely of blanks — then `find_if` will return `e`.

The next part of the problem is harder, namely to find the appropriate value for `e1`. We want to search from the end of the sequence toward the beginning; the most straightforward way of doing so is to use reverse iterators.

A reverse iterator is a standard-library template that traverses the same range of elements as the corresponding iterator. Briefly, if `Iter` is an iterator type, then `reverse_iterator<Iter>` is a reverse-iterator type that corresponds to `Iter`. For convenience, we shall define a template function that takes an iterator object and yields the corresponding reverse iterator:

```
template<class Iter> rev(Iter i) { return reverse_iterator<Iter>(i); }
```

Defining this function makes it easier to reason about programs that use reverse iterators. For example, we can now say that if iterators `b` and `e` denote a range of elements, then `rev(e)` and `rev(b)` denote that same range in reverse order — even though we do not know the specific types of `b` and `e`. Accordingly, we can almost figure out the right value for `e1` to have by writing

```
auto r1 = find_if(rev(e), rev(b), nonblank);
```

Notice that we have defined `r1` here rather than defining `e1`. The reason for doing so is that we would like `e1` to have the same type as `b1` so that `b1` and `e1` form a range. However, whatever type `b1` has, `r1` is the corresponding reverse-iterator type. We need to be able to convert `r1` back to the plain iterator type in such a way that the result of the conversion properly denotes the range that we seek.

There is no such direct conversion. You might think we could simply set `e1` to `rev(r1)`, but then `e1` would have type `reverse_iterator<reverse_iterator<Iter>>`, not type `Iter`. Moreover, if `rev(e)` and `rev(b)` represent the same range of elements as `b` and `e`, then `rev(b)` cannot represent the same element as `b!` The reason is that `rev(b)` must act as an off-the-end iterator for the range from `rev(e)` to `rev(b)`, so `rev(b)` cannot refer to an element directly even though `b` does so.

In effect, we have a rule:

Making a pair of iterators into a pair of reverse iterators covers the same range as the original iterators, but in reverse order.

This rule has a consequence:

Making a single iterator into a reverse iterator yields an iterator that does not refer to the same element as the single iterator.

We can make this consequence more precise. For example, `b` and `e` are iterators that refer to a range. If `rev(e)` and `rev(b)` cover that same range in reverse order, then `rev(b)` must be an off-the end iterator — in other words, `rev(b)` must refer to a position one element before `b`. Similarly, if `rev(e)` is the first element in the reversed range, then `rev(e)` must refer to the element immediately before `e` (unless the range is empty). Accordingly:

If we make an iterator into a reverse iterator, the resulting iterator must refer to the position immediately before  (in the direction of the original iterator) the element to which the original iterator refers.

Because of this rule, `r1` (as defined above) refers to the position before the rightmost nonblank in the sequence — in the direction of `r1`. However, `r1` is a reverse iterator, so this position is equivalent to the one after (in the direction of `b`) the rightmost nonblank in the sequence. This position, in turn, is equivalent to the leftmost in the (possibly empty) sequence of blanks that ends at the end of the original sequence.

Every reverse iterator has a member function named `base`, which undoes the effect of `rev`. In other words, `rev(b).base()` has the same type and value as `b`. Therefore, in order to obtain the proper value for `e1`, all we have to write is

```
auto e1 = r1.base();
```

For that matter, we can do away with `r1` entirely and write

```
auto e1 = find_if(rev(e), rev(b), nonblank).base();
```

In short, by writing

```
auto b1 = std::find_if(b, e, nonblank);
auto e1 = std::find_if(rev(e), rev(b), nonblank).base();
```

we have made `b1` and `e1` define the characters in the original range after excluding leading and trailing blanks.

It may seem confusing that we do not have to adjust the values of `b`, `e`, `b1`, or `e1` to obtain the range we desire. However, much of this confusion vanishes if we think about ranges rather than about elements. We have defined `rev` so that `rev(e)` and `rev(b)` define the same range as `b` and `e`. Similarly, `rev(b).base()` and `rev(e).base()` define the same range as `b` and `e` because of how `base` is defined. Therefore, we can reason about this code using ranges.

The first call to `find_if` yields a value `b1` such that the range from `b` to `b1` consists entirely of blanks. What begins after that is a range that (if nonempty) starts with a nonblank, so it begins with the first character of our desired result. Similarly, the second call to `find_if` yields a value `e1` such that the (reversed) range from `e` to `e1` consists entirely of blanks. What begins after that (going in reverse order) is a range that also starts with a nonblank.

When we converted `r1` to `e1`, all we did was to treat `r1` as a boundary. Making an iterator into a reverse iterator, and calling `base` to make that reverse iterator into an iterator again, leaves unchanged the boundary to which that iterator refers. In doing so, it changes the element to which the iterator refers; but this change is irrelevant so long as we realize that when we change iterator direction, we are using it as a boundary, rather than something that refers to an element.

### More Insights To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.

## Featured Reports ## Featured Whitepapers 