The concept of iterators is fundamental to using the container classes and the associated algorithms provided by the C++ Standard Library. An iterator is a pointer-like object used to cycle through all the elements stored in a container. Because different algorithms need to traverse containers in a variety of fashions, there are different forms of iterators. Each container class in the C++ Standard Library can generate an iterator with functionality appropriate to the storage technique used in implementing the container. It is the category of iterators required as arguments that chiefly distinguishes which algorithms in the C++ Standard Library can be used with which container classes.
Just as pointers can be used in a variety of ways in traditional programming, iterators can be used for a number of different purposes. An iterator can be used to denote a specific value, just as a pointer can be used to reference a specific memory location. A pair of iterators can be used to define a range or sequence of values held in a container, just as two pointers can be used to describe a contiguous region of memory. With iterators, however, the values being described may be only logically rather than physically in sequence because they are derived from the same container, and the second follows the first in the order in which the elements are maintained by the container.
Conventional pointers can sometimes be null, meaning they point at nothing. Iterators, as well, can fail to denote any specific value. Just as it is a logical error to dereference a null pointer, it is an error to dereference an iterator that is not denoting a value.
When two pointers that describe a region in memory are used in a C++ program, it is conventional that the ending pointer not be considered part of the region. For example, an array named x of length 10 is sometimes described as extending from x to x+10, even though the element at x+10 is not part of the array. Instead, the pointer value x+10 is the past-the-end value after the end of the range being described. Iterators are used similarly to describe a range. The second value is not considered part of the range being denoted. Instead, the second value is a past-the-end element describing the next value in sequence after the final value of the range. Sometimes, as with pointers to memory, this will be an actual value in the container. Other times it may be a special value, specifically constructed for the purpose. In either case, it is not proper to dereference an iterator that is being used to specify the end of a range.
Just as with conventional pointers, the fundamental operation used to modify an iterator is the increment operator, operator++(). When the increment operator is applied to an iterator that denotes the final value in a sequence, the iterator is changed to the past-the-end value. An iterator j is said to be reachable from an iterator i if, after a finite sequence of applications of the expression ++i, the iterator i becomes equal to j.
Ranges can be used to describe the entire contents of a container by constructing an iterator to the initial element and a special ending iterator. Ranges can also be used to describe sub-sequences within a single container by employing two iterators to specific values.
NOTE -- Whenever two iterators are used to describe a range, it is assumed that the second iterator is reachable from the first, but this is not verified. Errors can occur if this expectation is not satisfied.
In the remainder of this chapter, we describe the different forms of iterators used by the C++ Standard Library, as well as various other iterator-related functions.