9.2.1. Iterators

As with the containers, 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 iterators on the standard container types let us access an element from a container, and they all do so by providing the dereference operator. Similarly, the iterators for the library containers all define the increment operator to move from one element to the next.

With one exception, the container iterators support all the operations listed in Table 3.6 (p. 107). The exception is that the forward_list iterators do not support the decrement (--) operator. The iterator arithmetic operations listed in Table 3.7 (p. 111) apply only to iterators for string, vector, deque, and array. We cannot use these operations on iterators for any of the other container types.

Iterator Ranges

An iterator range is denoted by a pair of iterators each of which refers to an element, or to one past the last element, in the same container. These two iterators, often referred to as begin and end—or (somewhat misleadingly) as first and last—mark a range of elements from the container.

The name last, although commonly used, is a bit misleading, because 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 denoted by first and every element from first up to but not including last.

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

[ begin, end)

indicating that the range begins with begin and ends with, but does not include, end. The iterators begin and end must refer to the same container. The iterator end may be equal to begin but must not refer to an element before the one denoted by begin.

Programming Implications of Using Left-Inclusive Ranges

The library uses left-inclusive ranges because such ranges have three convenient properties. Assuming begin and end denote a valid iterator range, then

• If begin equals end, the range is empty

• If begin is not equal to end, there is at least one element in the range, and begin refers to the first element in that range

• We can increment begin some number of times until begin == end

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

while (begin   != end) {
    *begin =  val;    // ok: range isn't empty so begin denotes an element
    ++begin;          // advance the iterator to get the next element
}

Given that begin and end form a valid iterator range, we know that if begin == end, then the range is empty. In this case, we exit the loop. If the range is nonempty, we know that begin refers to an element in this nonempty range. Therefore, inside the body of the while, we know that it is safe to dereference begin because begin must refer to an element. Finally, because the loop body increments begin, we also know the loop will eventually terminate.