10.4. Revisiting Iterators

In addition to the iterators that are defined for each of the containers, the library defines several additional kinds of iterators in the iterator header. These iterators include

• Insert iterators: These iterators are bound to a container and can be used to insert elements into the container.
• Stream iterators: These iterators are bound to input or output streams and can be used to iterate through the associated IO stream.
• Reverse iterators: These iterators move backward, rather than forward. The library containers, other than forward_list, have reverse iterators.
• Move iterators: These special-purpose iterators move rather than copy their elements. We’ll cover move iterators in § 13.6.2 (p. 543).

10.4.1. Insert Iterators

Fundamental

An inserter is an iterator adaptor (§ 9.6, p. 368) that takes a container and yields an iterator that adds elements to the specified container. When we assign a value through an insert iterator, the iterator calls a container operation to add an element at a specified position in the given container. The operations these iterators support are listed in Table 10.2 (overleaf).

Table 10.2. Insert Iterator Operations

Code	Description
it = t	Inserts the value t at the current position denoted by it. Depending on the kind of insert iterator, and assuming c is the container to which it is bound, calls c.push_back(t), c.push_front(t), or c.insert(t, p), where p is the iterator position given to inserter.
*it ++it it++	These operations exist but do nothing to it. Each operator returns it.

There are three kinds of inserters. Each differs from the others as to where elements are inserted:

• back_inserter (§ 10.2.2, p. 382) creates an iterator that uses push_back.
• front_inserter creates an iterator that uses push_front.
• inserter creates an iterator that uses insert. This function takes a second argument, which must be an iterator into the given container. Elements are inserted ahead of the element denoted by the given iterator.

INFO

We can use front_inserteronly if the container has push_front. Similarly, we can use back_inserteronly if it has push_back.

It is important to understand that when we call inserter(c, iter), we get an iterator that, when used successively, inserts elements ahead of the element originally denoted by iter. That is, if it is an iterator generated by inserter, then an assignment such as

*it = val;

behaves as

it = c.insert(it, val); // it points to the newly added element
++it; // increment it so that it denotes the same element as before

The iterator generated by front_inserter behaves quite differently from the one created by inserter. When we use front_inserter, elements are always inserted ahead of the then first element in the container. Even if the position we pass to inserter initially denotes the first element, as soon as we insert an element in front of that element, that element is no longer the one at the beginning of the container:

list<int> lst = {1,2,3,4};
list<int> lst2, lst3;     // empty lists
// after copy completes, lst2 contains 4 3 2 1
copy(lst.cbegin(), lst.cend(), front_inserter(lst2));
// after copy completes, lst3 contains 1 2 3 4
copy(lst.cbegin(), lst.cend(), inserter(lst3, lst3.begin()));

When we call front_inserter(c), we get an insert iterator that successively calls push_front. As each element is inserted, it becomes the new first element in c. Therefore, front_inserter yields an iterator that reverses the order of the sequence that it inserts; inserter and back_inserter don’t.

INFO

Exercises Section 10.4.1

Exercise 10.26: Explain the differences among the three kinds of insert iterators.

Exercise 10.27: In addition to unique (§ 10.2.3, p. 384), the library defines function named unique_copy that takes a third iterator denoting a destination into which to copy the unique elements. Write a program that uses unique_copy to copy the unique elements from a vector into an initially empty list.

Exercise 10.28: Copy a vector that holds the values from 1 to 9 inclusive, into three other containers. Use an inserter, a back_inserter, and a front_inserter, respectivly to add elements to these containers. Predict how the output sequence varies by the kind of inserter and verify your predictions by running your programs.

10.4.2. iostream Iterators

Advanced

Even though the iostream types are not containers, there are iterators that can be used with objects of the IO types (§ 8.1, p. 310). An istream_iterator (Table 10.3 (overleaf)) reads an input stream, and an ostream_iterator (Table 10.4 (p. 405)) writes an output stream. These iterators treat their corresponding stream as a sequence of elements of a specified type. Using a stream iterator, we can use the generic algorithms to read data from or write data to stream objects.

Table 10.3. istream_iterator Operations

Code	Description
istream_iterator<T> in(is)	reads values of type T from input stream is.
istream_iterator<T> end;	Off-the-end iterator for an istream_iterator that reads values of type T.
in1 == in2 in1 != in2	in1 and in2 must read the same type. They are equal if they are both the end value or are bound to the same input stream.
*in	Returns the value read from the stream.
in->mem	Synonym for (*in).mem.
++in in++	Reads the next value from the input stream using the >> operator for the element type. As usual, the prefix version returns a reference to the incremented iterator. The postfix version returns the old value.

Table 10.4. ostream Iterator Operations

Code	Description
ostream_iterator<T> out(os);	out writes values of type T to output stream os.
ostream_iterator<T> out(os, d);	out writes values of type T followed by d to output stream os. d points to a null-terminated character array.
out = val	Writes val to the ostream to which out is bound using the << operator. val must have a type that is compatible with the type that out can write.
*out ++out out++	These operations exist but do nothing to out. Each operator returns out.

Operations on istream_iterators

When we create a stream iterator, we must specify the type of objects that the iterator will read or write. An istream_iterator uses >> to read a stream. Therefore, the type that an istream_iterator reads must have an input operator defined. When we create an istream_iterator, we can bind it to a stream. Alternatively, we can default initialize the iterator, which creates an iterator that we can use as the off-the-end value.

istream_iterator<int> int_it(cin);   //   reads ints from cin
istream_iterator<int> int_eof;       //   end iterator value
ifstream in("afile");
istream_iterator<string> str_it(in); //   reads strings from "afile"

As an example, we can use an istream_iterator to read the standard input into a vector:

istream_iterator<int> in_iter(cin);  // read ints from cin
istream_iterator<int> eof;           // istream ''end'' iterator
while (in_iter != eof)  // while there's valid input to read
    // postfix increment reads the stream and returns the old value of the iterator
    // we dereference that iterator to get the previous value read from the stream
    vec.push_back(*in_iter++);

This loop reads ints from cin, storing what was read in vec. On each iteration, the loop checks whether in_iter is the same as eof. That iterator was defined as the empty istream_iterator, which is used as the end iterator. An iterator bound to a stream is equal to the end iterator once its associated stream hits end-of-file or encounters an IO error.

The hardest part of this program is the argument to push_back, which uses the dereference and postfix increment operators. This expression works just like others we’ve written that combined dereference with postfix increment (§ 4.5, p. 148). The postfix increment advances the stream by reading the next value but returns the old value of the iterator. That old value contains the previous value read from the stream. We dereference that iterator to obtain that value.

What is more useful is that we can rewrite this program as

istream_iterator<int> in_iter(cin), eof;  // read ints from cin
vector<int> vec(in_iter, eof);  // construct vec from an iterator range

Here we construct vec from a pair of iterators that denote a range of elements. Those iterators are istream_iterators, which means that the range is obtained by reading the associated stream. This constructor reads cin until it hits end-of-file or encounters an input that is not an int. The elements that are read are used to construct vec.

Using Stream Iterators with the Algorithms

Because algorithms operate in terms of iterator operations, and the stream iterators support at least some iterator operations, we can use stream iterators with at least some of the algorithms. We’ll see in § 10.5.1 (p. 410) how to tell which algorithms can be used with the stream iterators. As one example, we can call accumulate with a pair of istream_iterators:

istream_iterator<int> in(cin), eof;
cout << accumulate(in, eof, 0) << endl;

This call will generate the sum of values read from the standard input. If the input to this program is

23 109 45 89 6 34 12 90 34 23 56 23 8 89 23

then the output will be 664.

istream_iterators Are Permitted to Use Lazy Evaluation

When we bind an istream_iterator to a stream, we are not guaranteed that it will read the stream immediately. The implementation is permitted to delay reading the stream until we use the iterator. We are guaranteed that before we dereference the iterator for the first time, the stream will have been read. For most programs, whether the read is immediate or delayed makes no difference. However, if we create an istream_iterator that we destroy without using or if we are synchronizing reads to the same stream from two different objects, then we might care a great deal when the read happens.

Operations on ostream_iterators

An ostream_iterator can be defined for any type that has an output operator (the << operator). When we create an ostream_iterator, we may (optionally) provide a second argument that specifies a character string to print following each element. That string must be a C-style character string (i.e., a string literal or a pointer to a null-terminated array). We must bind an ostream_iterator to a specific stream. There is no empty or off-the-end ostream_iterator.

We can use an ostream_iterator to write a sequence of values:

ostream_iterator<int> out_iter(cout, " ");
for (auto e : vec)
    *out_iter++ = e;  // the assignment writes this element to cout
cout << endl;

This program writes each element from vec onto cout following each element with a space. Each time we assign a value to out_iter, the write is committed.

It is worth noting that we can omit the dereference and the increment when we assign to out_iter. That is, we can write this loop equivalently as

for (auto e : vec)
    out_iter = e;  // the assignment writes this element to cout
cout << endl;

The * and ++ operators do nothing on an ostream_iterator, so omitting them has no effect on our program. However, we prefer to write the loop as first presented. That loop uses the iterator consistently with how we use other iterator types. We can easily change this loop to execute on another iterator type. Moreover, the behavior of this loop will be clearer to readers of our code.

Rather than writing the loop ourselves, we can more easily print the elements in vec by calling copy:

copy(vec.begin(), vec.end(), out_iter);
cout << endl;

Using Stream Iterators with Class Types

We can create an istream_iterator for any type that has an input operator (>>). Similarly, we can define an ostream_iterator so long as the type has an output operator (<<). Because Sales_item has both input and output operators, we can use IO iterators to rewrite the bookstore program from § 1.6 (p. 24):

istream_iterator<Sales_item> item_iter(cin), eof;
ostream_iterator<Sales_item> out_iter(cout, "\n");
// store the first transaction in sum and read the next record
Sales_item sum = *item_iter++;
while (item_iter != eof) {
    // if the current transaction (which is stored in item_iter) has the same ISBN
    if (item_iter->isbn() == sum.isbn())
        sum += *item_iter++; // add it to sum and read the next transaction
    else {
        out_iter = sum;      // write the current sum
        sum = *item_iter++;  // read the next transaction
    }
}
out_iter = sum;  // remember to print the last set of records

This program uses item_iter to read Sales_item transactions from cin. It uses out_iter to write the resulting sums to cout, following each output with a newline. Having defined our iterators, we use item_iter to initialize sum with the value of the first transaction:

// store the first transaction in sum and read the next record
Sales_item sum = *item_iter++;

Here, we dereference the result of the postfix increment on item_iter. This expression reads the next transaction, and initializes sum from the value previously stored in item_iter.

The while loop executes until we hit end-of-file on cin. Inside the while, we check whether sum and the record we just read refer to the same book. If so, we add the most recently read Sales_item into sum. If the ISBNs differ, we assign sum to out_iter, which prints the current value of sum followed by a newline. Having printed the sum for the previous book, we assign sum a copy of the most recently read transaction and increment the iterator, which reads the next transaction. The loop continues until an error or end-of-file is encountered. Before exiting, we remember to print the values associated with the last book in the input.

INFO

Exercises Section 10.4.2

Exercise 10.29: Write a program using stream iterators to read a text file into a vector of strings.

Exercise 10.30: Use stream iterators, sort, and copy to read a sequence of integers from the standard input, sort them, and then write them back to the standard output.

Exercise 10.31: Update the program from the previous exercise so that it prints only the unique elements. Your program should use unqiue_copy (§ 10.4.1, p. 403).

Exercise 10.32: Rewrite the bookstore problem from § 1.6 (p. 24) using a vector to hold the transactions and various algorithms to do the processing. Use sort with your compareIsbn function from § 10.3.1 (p. 387) to arrange the transactions in order, and then use find and accumulate to do the sum.

Exercise 10.33: Write a program that takes the names of an input file and two output files. The input file should hold integers. Using an istream_iterator read the input file. Using ostream_iterators, write the odd numbers into the first output file. Each value should be followed by a space. Write the even numbers into the second file. Each of these values should be placed on a separate line.

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

Tricky

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 the 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().

INFO

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.

INFO

Exercises Section 10.4.3

Exercise 10.34: Use reverse_iterators 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 ints 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.