15.3 Introduction to Iterators
Iterators have many similarities to pointers and are used to point to first-class container elements and for other purposes. Iterators hold state information sensitive to the particular containers on which they operate; thus, iterators are implemented for each type of container. Certain iterator operations are uniform across containers. For example, the dereferencing operator (*) dereferences an iterator so that you can use the element to which it points. The ++ operation on an iterator moves it to the container’s next element (much as incrementing a pointer into a built-in array aims the pointer at the next array element).
First-class containers provide member functions begin and end. Function begin returns an iterator pointing to the first element of the container. Function end returns an iterator pointing to the first element past the end of the container (one past the end)—a nonexistent element that’s frequently used to determine when the end of a container is reached. If iterator i points to a particular element, then ++i points to the “next” element and *i refers to the element pointed to by i. The iterator resulting from end is typically used in an equality or inequality comparison to determine whether the “moving iterator” (i in this case) has reached the end of the container.
An object of a container’s iterator type refers to a container element that can be modified. An object of a container’s const_iterator type refers to a container element that cannot be modified.
Using istream_iterator for Input and ostream_iterator for Output
We use iterators with sequences (also called ranges). These can be in containers, or they can be input sequences or output sequences. Figure 15.4 demonstrates input from the standard input (a sequence of data for input into a program), using an istream_iterator, and output to the standard output (a sequence of data for output from a program), using an ostream_iterator. The program inputs two integers from the user and displays their sum. As you’ll see later in this chapter, istream_iterators and ostream_iterators can be used with the Standard Library algorithms to create powerful statements. For example, starting in Fig. 15.11, you’ll use an ostream_iterator with the copy algorithm to copy a container’s entire contents to the standard output stream with a single statement.
Fig. 15.4 Demonstrating input and output with iterators.
Alternate View
1 // Fig. 15.4: fig15_04.cpp
2 // Demonstrating input and output with iterators.
3 #include <iostream>
4 #include <iterator> // ostream_iterator and istream_iterator
5 using namespace std;
6
7 int main() {
8 cout << "Enter two integers: ";
9
10 // create istream_iterator for reading int values from cin
11 istream_iterator<int> inputInt{cin};
12
13 int number1{*inputInt}; // read int from standard input
14 ++inputInt; // move iterator to next input value
15 int number2{*inputInt}; // read int from standard input
16
17 // create ostream_iterator for writing int values to cout
18 ostream_iterator<int> outputInt{cout};
19
20 cout << "The sum is: ";
21 *outputInt = number1 + number2; // output result to cout
22 cout << endl;
23 }
Enter two integers: 12 25
The sum is: 37
istream_iterator
Line 11 creates an istream_iterator that’s capable of extracting (inputting) int values from the standard input object cin. Line 13 dereferences iterator inputInt to read the first integer from cin and assigns that integer to number1. The dereferencing operator * applied to iterator inputInt gets the value from the stream associated with inputInt; this is similar to dereferencing a pointer. Line 14 positions iterator inputInt to the next value in the input stream. Line 15 inputs the next integer from inputInt and assigns it to number2.
ostream_iterator
Line 18 creates an ostream_iterator that’s capable of inserting (outputting) int values in the standard output object cout. Line 21 outputs an integer to cout by assigning to *outputInt the sum of number1 and number2. Notice that we use the dereferenced outputInt iterator as an lvalue in the assignment statement. If you want to output another value using outputInt, the iterator must be incremented with ++ first. Either the prefix or postfix increment can be used—we use the prefix form for performance reasons because it does not create a temporary object.
Error-Prevention Tip 15.2
The * (dereferencing) operator when applied to a const iterator returns a reference to const for the container element, disallowing the use of non-const member functions.
Iterator Categories and Iterator Category Hierarchy
Figure 15.5 describes the iterator categories. Each provides a specific set of functionality.
Fig. 15.5 Iterator categories.
| Category | Description |
|---|---|
| input | Used to read an element from a container. An input iterator can move only in the forward direction (i.e., from the beginning of the container to the end) one element at a time. Input iterators support only one-pass algorithms—the same input iterator cannot be used to pass through a sequence twice. |
| output | Used to write an element to a container. An output iterator can move only in the forward direction one element at a time. Output iterators support only one-pass algorithms—the same output iterator cannot be used to pass through a sequence twice. |
| forward | Combines the capabilities of input and output iterators and retains their position in the container (as state information). Such iterators can be used to pass through a sequence more than once (for so-called multipass algorithms). |
| bidirectional | Combines the capabilities of a forward iterator with the ability to move in the backward direction (i.e., from the end of the container toward the beginning). Bidirectional iterators support multipass algorithms, such as reversing the elements of a container. |
| random access | Combines the capabilities of a bidirectional iterator with the ability to directly access any element of the container, i.e., to jump forward or backward by an arbitrary number of elements. These can also be compared with relational operators. |
Figure 15.6 illustrates the hierarchy of iterator categories. As you follow the hierarchy from bottom to top, each iterator category supports all the functionality of the categories below it in the figure. Thus the “weakest” iterator types are at the bottom and the most powerful one is at the top. Note that this is not an inheritance hierarchy.
Fig. 15.6 Iterator category hierarchy.
Container Support for Iterators
The iterator category that each container supports determines whether that container can be used with specific algorithms. Containers that support random-access iterators can be used with all Standard Library algorithms—with the exception that if an algorithm requires changes to a container’s size, the algorithm can’t be used on built-in arrays or array objects. Pointers into built-in arrays can be used in place of iterators with most algorithms. Figure 15.7 shows the iterator category of each container. The first-class containers, strings and built-in arrays are all traversable with iterators.
Predefined Iterator typedefs
Figure 15.8 shows the predefined iterator typedefs that are found in the Standard Library container class definitions. Not every typedef is defined for every container. We use const
Fig. 15.7 Iterator types supported by each container.
| Container | Iterator type |
|---|---|
| Sequence containers (first class) | |
vector |
random access |
array |
random access |
deque |
random access |
list |
bidirectional |
forward_list |
forward |
| Ordered associative containers (first class) | |
set |
bidirectional |
multiset |
bidirectional |
map |
bidirectional |
multimap |
bidirectional |
| Unordered associative containers (first class) | |
unordered_set |
bidirectional |
unordered_multiset |
bidirectional |
unordered_map |
bidirectional |
unordered_multimap |
bidirectional |
| Container adapters | |
stack |
none |
queue |
none |
priority_queue |
none |
versions of the iterators for traversing const containers or non-const containers that should not be modified. We use reverse iterators to traverse containers in the reverse direction.
Error-Prevention Tip 15.3
Operations performed on a const_iterator return references to const to prevent modification to elements of the container being manipulated. Using const_iterators where appropriate is another example of the principle of least privilege.
Fig. 15.8 Iterator typedefs.
Predefined typedefs for iterator types |
Direction of ++ |
Capability |
|---|---|---|
iterator |
forward | read/write |
const_iterator |
forward | read |
reverse_iterator |
backward | read/write |
const_reverse_iterator |
backward | read |
Iterator Operations
Figure 15.9 shows operations that can be performed on each iterator type. In addition to the operators shown for all iterators, iterators must provide default constructors, copy constructors and copy assignment operators. A forward iterator supports ++ and all of the input and output iterator capabilities. A bidirectional iterator supports -- and all the capabilities of forward iterators. A random-access iterator supports all of the operations shown in the table. For input iterators and output iterators, it’s not possible to save the iterator, then use the saved value later.
Fig. 15.9 Iterator operations for each type of iterator.
| Iterator operation | Description |
|---|---|
| All iterators | |
++p |
Preincrement an iterator. |
p++ |
Postincrement an iterator. |
p = p1 |
Assign one iterator to another. |
| Input iterators | |
*p |
Dereference an iterator as an rvalue. |
p->m |
Use the iterator to read the element m. |
p == p1 |
Compare iterators for equality. |
p != p1 |
Compare iterators for inequality. |
| Output iterators | |
*p |
Dereference an iterator as an lvalue. |
p = p1 |
Assign one iterator to another. |
| Forward iterators | Forward iterators provide all the functionality of both input iterators and output iterators. |
| Bidirectional iterators | |
--p |
Predecrement an iterator. |
p-- |
Postdecrement an iterator. |
| Random-access iterators | |
p += i |
Increment the iterator p by i positions. |
p -= i |
Decrement the iterator p by i positions. |
p + i or i + p |
Expression value is an iterator positioned at p incremented by i positions. |
p - i |
Expression value is an iterator positioned at p decremented by i positions. |
p - p1 |
Expression value is an integer representing the distance between two elements in the same container. |
p[i] |
Return a reference to the element offset from p by i positions |
p < p1 |
Return true if iterator p is less than iterator p1 (i.e., iterator p is before iterator p1 in the container); otherwise, return false. |
p <= p1 |
Return true if iterator p is less than or equal to iterator p1 (i.e., iterator p is before iterator p1 or at the same location as iterator p1 in the container); otherwise, return false. |
p > p1 |
Return true if iterator p is greater than iterator p1 (i.e., iterator p is after iterator p1 in the container); otherwise, return false. |
p >= p1 |
Return true if iterator p is greater than or equal to iterator p1 (i.e., iterator p is after iterator p1 or at the same location as iterator p1 in the container); otherwise, return false. |