Section 9.2. Iterators and Iterator Ranges

9.2. Iterators and Iterator Ranges

The constructors that take a pair of iterators are an example of a common form used extensively throughout the library. Before we look further at the container operations, we should understand a bit more about iterators and iterator ranges.

In Section 3.4 (p. 95), we first encountered vector iterators. Each of the container types has several companion iterator types. Like the containers, the iterators have a common interface: If an iterator provides an operation, then the operation is supported in the same way for each iterator that supplies that operation. For example, all the container iterators let us read an element from a container, and they all do so by providing the dereference operator. Similarly, they all provide increment and decrement operators to allow us to go from one element to the next. Table 9.3 lists the iterator operations supported by the iterators for all of the library containers.

Table 9.3. Common Iterator Operations

*iter	Return a reference to the element referred to by the iterator iter.
iter->mem	Dereference iter and fetch the member named mem from the underlying element. Equivalent to (*iter).mem.
++iter iter++	Increment iter to refer to the next element in the container.
--iter iter--	Decrement iter to refer to the previous element in the container.
iter1 == iter2 iter1 != iter2	Compare two iterators for equality (inequality). Two iterators are equal if they refer to the same element of the same container or if they are the off-the-end iterator (Section 3.4, p. 97) for the same container.

Iterators on vector and deque Support Additional Operations

There are two important sets of operations that only vector and deque support: iterator arithmetic (Section 3.4.1, p. 100) and the use of the relational operators (in addition to == and !=) to compare two iterators. These operations are summarized in Table 9.4 on the facing page.

Table 9.4. Operations Supported by vector and deque Iterators

iter + n iter - n	Adding (subtracting) an integral value n to (from) an iterator yields an iterator that many elements forward (backward) within the container. The resulting iterator must refer to an element in the container or one past the end of the container.
iter1 += iter2 iter1 -= iter2	Compound-assignment versions of iterator addition and subtraction. Assigns the value of adding or subtracting iter1 and iter2 into iter1.
iter1 - iter2	Subtracting two iterators yields the number that when added to the right-hand iterator yields the left-hand iterator. The iterators must refer to elements in the same container or one past the end of the container. Supported only for vector and deque.
>, >=, <, <=	Relational operators on iterators. One iterator is less than another if it refers to an element whose position in the container is ahead of the one referred to by the other iterator. The iterators must refer to elements in the same container or one past the end of the container. Supported only for vector and deque.

The reason that only vector and deque support the relational operators is that only vector and deque offer fast, random access to their elements. These containers are guaranteed to let us efficiently jump directly to an element given its position in the container. Because these containers support random access by position, it is possible for their iterators to efficiently implement the arithmetic and relational operations.

For example, we could calculate the midpoint of a vector as follows:

      vector<int>::iterator iter = vec.begin() + vec.size()/2; 

On the other hand, this code

      // copy elements from vec into ilist      list<int> ilist(vec.begin(), vec.end());      ilist.begin() + ilist.size()/2; // error: no addition on list iterators 

is an error. The list iterator does not support the arithmetic operationsaddition or subtractionnor does it support the relational (<=, <, >=, >) operators. It does support pre- and postfix increment and decrement and the equality (inequality) operators.

In Chapter 11 we'll see that the operations an iterator supports are fundamental to using the library algorithms.

Exercises Section 9.2

Exercise 9.7:	What is wrong with the following program? How might you correct it? list<int> lst1; list<int>::iterator iter1 = lst1.begin(), iter2 = lst1.end(); while (iter1 < iter2) /* . . . */
Exercise 9.8:	Assuming vec_iter is bound to an element in a vector that holds strings, what does this statement do? if (vec_iter->empty()) /* . . . */
Exercise 9.9:	Write a loop to write the elements of a list in reverse order.
Exercise 9.10:	Which, if any, of the following iterator uses are in error? const vector< int > ivec(10); vector< string > svec(10); list< int > ilist(10); (a) vector<int>::iterator it = ivec.begin(); (b) list<int>::iterator it = ilist.begin()+2; (c) vector<string>::iterator it = &svec[0]; (d) for (vector<string>::iterator it = svec.begin(); it != 0; ++it) // ...

9.2.1. Iterator Ranges

The concept of an iterator range is fundamental to the standard library.

An iterator range is denoted by a pair of iterators that refer to two elements, or to one past the last element, in the same container. These two iterators, often referred to as first and last, or beg and end, mark a range of elements from the container.

Although the names last and end are common, they are a bit misleading. The second iterator never refers to the last element of the range. Instead, it refers to a point one past the last element. The elements in the range include the element referred to by first and every element from first tHRough the element just before last. If the iterators are equal, then the range is empty.

This element range is called a left-inclusive interval. The standard notation for such a range is

      // to be read as: includes first and each element up to but not including last      [ first, last ) 

indicating that the range begins with first and ends with, but does not include, last. The iterator in last may be equal to the first or may refer to an element that appears after the one referred to by first. The last iterator must not refer to an element ahead of the one referred to by first.

Requirements on Iterators Forming an Iterator Range

Two iterators, first and last, form an iterator range, if

• They refer to elements of, or one-past-the-end of, the same container.

• If the iterators are not equal, then it must be possible to reach last by repeatedly incrementing first. In other words, last must not precede first in the container.

The compiler cannot itself enforce these requirements. It does not know to which container an iterator is bound, nor does it know how many elements are in a container. Failing to meet these requirements results in undefined run-time behavior.

Programming Implications of Using Left-Inclusive Ranges

The library uses left-inclusive ranges because such ranges have two convenient properties. Assuming first and last denote a valid iterator range, then

1. When first equals last, the range is empty.

2. When first is not equal to last, there is at least one element in the range, and first refers to the first element in that range. Moreover, we can advance first by incrementing it some number of times until first == last.

These properties mean that we can safely write loops such as the following to process a range of elements by testing the iterators:

      while (first != last) {          // safe to use *first because we know there is at least one element          ++first;      } 

Assuming first and last form a valid iterator range, then we know that either first == last, in which case the loop is exited, or the range is non-empty and first refers to an element. Because the condition in the while handles the case where the range is empty, there is no need for a special case to handle an empty range. When the range is non-empty, the loop will execute at least once. Because the loop body increments first, we know the loop will eventually terminate. Moreover, if we are in the loop, then we know that *first is safe: It must refer to an element in the non-empty range between first and last.

Exercises Section 9.2.1

Exercise 9.11:	What are the constraints on the iterators that form iterator ranges?
Exercise 9.12:	Write a function that takes a pair of iterators and an int value. Look for that value in the range and return a bool indicating whether it was found.
Exercise 9.13:	Rewrite the program that finds a value to return an iterator that refers to the element. Be sure your function works correctly if the element does not exist.
Exercise 9.14:	Using iterators, write a program to read a sequence of strings from the standard input into a vector. Print the elements in the vector.
Exercise 9.15:	Rewrite the program from the previous exercise to use a list. List the changes you needed to change the container type.

9.2.2. Some Container Operations Invalidate Iterators

In the sections that follow, we'll see that some container operations change the internal state of a container or cause the elements in the container to be moved. Such operations invalidate all iterators that refer to the elements that are moved and may invalidate other iterators as well. Using an invalidated iterator is undefined, and likely to lead to the same kinds of problems as using a dangling pointer.

For example, each container defines one or more erase functions. These functions remove elements from the container. Any iterator that refers to an element that is removed has an invalid value. After all, the iterator was positioned on an element that no longer exists within the container.

When writing programs that use iterators, we must be aware of which operations can invalidate the iterators. It is a serious run-time error to use an iterator that has been invalidated.

There is no way to examine an iterator to determine whether it has been invalidated. There is no test we can perform to detect that it has gone bad. Any use of an invalidated iterator is likely to yield a run-time error, but there is no guarantee that the program will crash or otherwise make it easy to detect the problem.

When using iterators, it is usually possible to write the program so that the range of code over which an iterator must stay valid is relatively short. It is important to examine each statement in this range to determine whether elements are added or removed and adjust iterator values accordingly.