Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

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.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips 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.
 


Video