18.1 Iterators

The White Rabbit put on his spectacles. “Where shall I begin, please your Majesty?” he asked.

“Begin at the beginning,” the King said, very gravely, “And go on till you come to the end: then stop.”

LEWIS CARROLL, Alice in Wonderland

Vectors, introduced in Chapter 8, are one of the container template classes in the STL. Iterators are a generalization of pointers. (Chapter 13 includes an introduction to pointers used as iterators.) This section shows you how to use iterators with vectors. Other container template classes, which we introduce in Section 18.2, use iterators in the same way. So, all you learn about iterators in this section will apply across a wide range of containers and does not apply solely to vectors. This reflects one of the basic tenets of the STL philosophy: The semantics, naming, and syntax for iterator usage should be (and are) uniform across different container types. We begin with a review and discussion of the using declarations, which we will use extensively when discussing iterators and the STL.

using Declarations

It may help to review the subsection entitled “Qualifying Names” in Chapter 12 before you continue with this subsection and this chapter.

Suppose my_function is a function defined in the namespace my_space. The following using declaration allows you to use the identifier my_function and have it mean the versions of my_function defined in the namespace my_space:

using my_space::my_function;

Within the scope of this using declaration an expression such as my_function(1,2) means the same thing as my_space::my_function(1,2); that is, within the scope of this using declaration the identifier my_function always indicates the version of my_function defined in my_space, as opposed to any definition of my_function defined in any other namespace.

When discussing iterators we will often apply the :: operator to another level. You will often see expressions such as the following:

using std::vector<int >::iterator;

In this case, the identifier iterator names a type. So within the scope of this using directive, the following would be allowed:

iterator p;

This declares p to be of the type iterator. What is the type iterator? It is defined in the definition of the class vector<int>. Which class vector<int>? The one defined in the namespace std. (We will fully explain the type iterator later. At this point we are concerned only with explaining using directives.)

You may object that this is all a big to-do about nothing. There is no class vector<int> defined in any namespace other than the namespace std. That may or may not be true, but there could be a class named vector<int> defined in some other namespace either now or in the future. You may object further that you never heard of defining a type within a class. We have not covered such definitions, but they are possible and they are common in the STL. So, you must know how to use such types, even if you do not define such types.

In summary, consider the using directive

using std::vector<int>::iterator;

Within the scope of this using directive the identifier iterator means the type named iterator that is defined in the class vector<int>, which in turn is defined in the std namespace.

Iterator Basics

An iterator is a generalization of a pointer, and in fact is typically even implemented using a pointer, but the abstraction of an iterator is designed to spare you the details of the implementation and give you a uniform interface to iterators that is the same across different container classes. Each container class has its own iterator types, just like each data type has its own pointer type. But just as all pointer types behave essentially the same for dynamic variables of their particular data type, so too does each iterator type behave the same, but each iterator is used only with its own container class.

An iterator is not a pointer, but you will not go far wrong if you think of it and use it as if it were a pointer. Like a pointer variable, an iterator variable is located at (“points to”) one data entry in the container. You manipulate iterators using the following overloaded operators that apply to iterator objects:

• Prefix and postfix increment operators, ++, for advancing the iterator to the next data item

• Prefix and postfix decrement operators, −−, for moving the iterator to the previous data item.

• Equal and unequal operators, == and !=, to test whether two iterators point to the same data location.

• A dereferencing operator, *, so that if p is an iterator variable, then *p gives access to the data located at (“pointed to by”) p. This access may be read-only, write-only, or allow both reading and changing of the data, depending on the particular container class.

Not all iterators have all of these operators. However, the vector template class is an example of a container whose iterators have all these operators and more.

A container class has member functions that get the iterator process started. After all, a new iterator variable is not located at (“pointing to”) any data in the container. Many container classes, including the vector template class, have the following member functions that return iterator objects (iterator values) that point to special data elements in the data structure:

• c.begin() returns an iterator for the container c that points to the “first” data item in the container c.

• c.end() returns something that can be used to test when an iterator has passed beyond the last data item in a container c. The iterator c.end() is completely analogous to NULL used to test when a pointer has passed the last node in a linked list of the kind discussed in Chapter 13. The iterator c.end() is thus an iterator that is located at no data item, but that is a kind of end marker or sentinel.

For many container classes, these tools allow you to write for loops that cycle through all the elements in a container object c, as follows:

//p is an iterator variable of the type for the container object c.
for (p = c.begin(); p != c.end(); p++)
    process *p //*p is the current data item.

That’s the big picture. Now let’s look at the details in the concrete setting of the vector template container class.

Display 18.1 illustrates the use of iterators with the vector template class. Keep in mind that each container type in the STL has its own iterator types, although they are all used in the same basic ways. The iterators we want for a vector of ints are of type

std::vector<int>::iterator

Another container class is the list template class. Iterators for lists of ints are of type

std::list<int>::iterator

Display 18.1 Iterators Used with a Vector

 1    //Program to demonstrate STL iterators.
 2    #include <iostream>
 3    #include <vector>
 4    using std::cout;
 5    using std::endl;
 6    using std::vector;
 7    int main()
 8    {
 9        vector<int> container;
10        for (int i = 1; i <= 4; i++)
11               container.push_back(i);
12        cout << "Here is what is in the container:\n";
13        vector<int>::iterator p;
14        for (p = container.begin(); p != container.end(); p++)
15            cout << *p << " ";
16        cout << endl;
17        cout << "Setting entries to 0:\n";
18        for (p = container.begin(); p != container.end(); p++)
19            *p = 0;
20     
21        cout << "Container now contains:\n";
22        for (p = container.begin(); p != container.end(); p++)
23            cout << *p << " ";
24        cout << endl;
25        return 0;
26    }

Sample Dialogue

Here is what is in the container:
1 2 3 4
Setting entries to 0:
Container now contains:
0 0 0 0

In the program in Display 18.1, we specialize the type name iterator so that it applies to iterators for vectors of ints. The type name iterator that we want in Display 18.1 is defined in the template class vector and so if we specialize the template class vector to ints and want the iterator type for vector<int>, we want the type

std::vector<int>::iterator;

Since the vector definition places the name vector in the std namespace, the entire using declaration is

using std::vector<int>::iterator;

The basic use of iterators with the vector (or any container class) is illustrated by the following lines from Display 18.1:

vector<int>::iterator p;
for (p = container.begin(); p != container.end(); p++)
    cout << *p << " ";

Recall that container is of type vector<int>.

A vector v can be thought of as a linear arrangement of its data elements. There is a first data element v[0], a second data element v[1], and so forth. An iterator p is an object that can be located at one of these elements. (Think of p as pointing to one of these elements.) An iterator can move its location from one element to another element. If p is located at, say, v[7], then p++ moves p so it is located at v[8]. This allows an iterator to move through the vector from the first element to the last element, but it needs to find the first element and needs to know when it has seen the last element.

You can tell if an iterator is at the same location as another iterator using the operator ==. Thus, if you have an iterator pointing to the first, last, or other element, you could test another iterator to see if it is located at the first, last, or other element.

If p1 and p2 are two iterators, then the comparison

p1 == p2

is true when and only when p1 and p2 are located at the same element. (This is analogous to pointers. If p1 and p2 were pointers, this would be true if they pointed to the same thing.) As usual, != is just the negation of == and so

p1 != p2

is true when p1 and p2 are not located at the same element.

The member function begin() is used to position an iterator at the first element in a container. For vectors, and many other container classes, the member function begin() returns an iterator located at the first element. (For a vector v the first element is v[0].) Thus,

vector<int>::iterator p = v.begin();

initializes the iterator variable p to an iterator located at the first element. So, the basic for loop for visiting all elements of the vector v is

vector<int>::iterator p;
for (p = v.begin(); Boolean_Expression>; p++)
     Action_At_Location p;

The desired Boolean_Expression for a stopping condition is

p == v.end()

The member function end() returns a sentinel value that can be checked to see if an iterator has passed the last element. If p is located at the last element, then after p++, the test p = v.end() changes from false to true. So the for loop with the correct Boolean_Expression is

vector<int>::iterator p;
for (p = v.begin(); p != v.end(); p++)
     Action_At_Location p;

Note that p != v.end() does not change from true to false until after p’s location has advanced past the last element. So, v.end() is not located at any element. The value v.end() is a special value that serves as a sentinel value. It is not an ordinary iterator, but you can compare v.end() to an iterator using == and !=. The value v.end() is analogous to the value NULL used to mark the end of a linked list of the kind discussed in Chapter 13.

The following for loop from Display 18.1 uses this exact technique with the vector named container:

vector<int>::iterator p;
for (p = container.begin(); p != container.end(); p++)
   cout << *p << " ";

The action taken at the location of the iterator p is

cout << *p << " ";

The dereferencing operator * is overloaded for STL container iterators so that *p produces the element at location p. In particular, for a vector container, *p produces the element located at the iterator p. So, the cout statement above outputs the element located at the iterator p and the entire for loop outputs all the elements in the vector container.

The dereferencing operator *p always produces the element located at the iterator p. In some situations, *p produces read-only access, which does not allow you to change the element. In other situations, it gives you access to the element and will let you change the element. For vectors, *p will allow you to change the element located at p, as illustrated by the following for loop from Display 18.1:

for (p = container.begin(); p != container.end(); p++)
    *p = 0;

This for loop cycles through all the elements in the vector container and changes all the elements to 0.

Programming Tip Use auto to Simplify Variable Declarations

The auto keyword can make your code much more readable when it comes to templates and iterators. Declaring an iterator can be really verbose:

vector<int>::iterator p = v.begin();

We can do the same thing much more compactly with auto:

auto p = v.begin();

Pitfall Compiler Problems

Some compilers have problems with iterator declarations. You can declare an iterator in different ways. For example, we have been using the following:

using std::vector;
 …
vector<char>::iterator p;

Iterator

An iterator is an object that can be used with a container to gain access to elements in the container. An iterator is a generalization of the notion of a pointer, and the operators ==, !=, ++, and −− behave the same for iterators as they do for pointers. The basic outline of how an iterator can cycle through all the elements in a container is

STL_Container<type>::iterator p;
for (p = container.begin(); p != container.end(); p++)
     Process_Element_At_Location p;

STL_Container is the name of the container class (for example, vector) and type is the data type of the item to be stored. The member function begin() returns an iterator located at the first element. The member function end() returns a value that serves as a sentinel value one location past the last element in the container.

Alternatively, if your code only uses a single type of iterator, you could use the following:

using std::vector<char>::iterator;
…
iterator p;

You also could use the following, which is not quite as nice, because it introduces all names from the std namespace to the current declarative region, increasing the likelihood of a name conflict.

using namespace std;
 …
vector<char>::iterator p;

There are other, similar variations. Your compiler should accept any of these alternatives. However, we have found that some compilers will accept only certain of them. If one form does not work with your compiler, try another.

Dereferencing

The dereferencing operator *p when applied to an iterator p produces the element located at the iterator p. For some STL container classes, *p produces read-only access, which does not allow you to change the element. For other STL container classes, it gives you access to the element and will let you change the element.

Self-Test Exercises

1. If v is a vector, what does v.begin() return? What does v.end() return?

2. If p is an iterator for a vector object v, what is *p?

3. Suppose v is a vector of ints. Write a for loop that outputs all the elements of v, except for the first element.

Kinds of Iterators

Different containers have different kinds of iterators. Iterators are classified according to the kinds of operations that work on them. Vector iterators are of the most general form; that is, all the operations work with vector iterators. So, we will again use the vector container to illustrate iterators. In this case we use a vector to illustrate the iterator operators of decrement and random access. Display 18.2 shows another program using a vector object named container and an iterator p.

Display 18.2 Bidirectional and Random Access Iterator Use

Figure 18.2 Full Alternative Text

18.1-1 Full Alternative Text

Sample Dialogue

container[0] == A
container[1] == B
container[2] == C
container[3] == D
The third entry is C
The third entry is C
The third entry is C
Back to container[0].
which has value A
Two steps forward and one step back:
B
C
B

The decrement operator is used in Display 18.2, where the line containing it is shown in highlight. As you would expect, p−− moves the iterator p to the previous location. The decrement operator −− is the same as the increment operator ++, but it moves the iterator in the opposite direction.

The increment and decrement operators can be used in either prefix (++p) or postfix (p++) notation. In addition to changing p, they also return a value. The details of the value returned are completely analogous to what happens with the increment and decrement operators on int variables. In prefix notation, first the variable is changed and the changed value is returned. In postfix notation, the value is returned before the variable is changed. We prefer not to use the increment and decrement operators as expressions that return a value and use them only to change the variable value.

The following lines from Display 18.2 illustrate that with vector iterators you have random access to the elements of a vector, such as container:

vector<char>::iterator p = container.begin();
cout << "The third entry is " << container[2] << endl;
cout << "The third entry is " << p[2] << endl;
cout << "The third entry is " << *(p + 2) << endl;

Random access means you can go in one step directly to any particular element. We have already used container[2] as a form of random access to a vector. It is simply the square bracket operator that is standard with arrays and vectors. What is new is that you can use this same square bracket notation with an iterator. The expression p[2] is a way to obtain access to the element indexed by 2.

The expressions p[2] and *(p + 2) are completely equivalent. By analogy to pointer arithmetic (see Chapter 9), (p + 2) names the location two places beyond p. Since p is at the first (index 0) location in the above code, (p + 2) is at the third (index 2) location. The expression (p + 2) returns an iterator. The expression *(p + 2) dereferences that iterator. Of course, you can replace 2 with a different nonnegative integer to obtain a pointer pointing to a different element.

Be sure to note that neither p[2] nor (p + 2) changes the value of the iterator in the iterator variable p. The expression (p + 2) returns another iterator at another location, but it leaves p where it was. The same thing happens with p[2]. Also note that the meaning of p[2] and (p + 2) depends on the location of the iterator in p. For example, (p + 2) means two locations beyond the location of p, wherever that may be.

For example, suppose the previously discussed code from Display 18.2 were replaced with the following (note the added p++):

vector<char>::iterator p = container.begin();
p++;
cout << "The third entry is " << container[2] << endl;
cout << "The third entry is " << p[2] << endl;
cout << "The third entry is " << *(p + 2) << endl;

The output of these three couts would no longer be

The third entry is C
The third entry is C
The third entry is C

but would instead be

The third entry is C
The third entry is D
The third entry is D

The p++ moves p from location 0 to location 1 and so (p + 2) is now an iterator at location 3, not location 2. So, *(p + 2) and p[2] are equivalent to container[3], not container[2].

Kinds of Iterators

Different containers have different kinds of iterators. The following are the main kinds of iterators:

• Forward iterators: ++ works on the iterator.

• Bidirectional iterators: both ++ and −− work on the iterator.

• Random access iterators: ++, −−, and random access all work with the iterator.

We now know enough about iterators to make sense of how iterators are classified. The main kinds of iterators are

• Forward iterators: ++ works on the iterator.

• Bidirectional iterators: both ++ and −− work on the iterator.

• Random access iterators: ++, −−, and random access all work with the iterator.

Note that these are increasingly strong categories: Every random access iterator is also a bidirectional iterator, and every bidirectional iterator is also a forward iterator. As we will see, different template container classes have different kinds of iterators. The iterators for the vector template class are random access iterators.

Note that the names forward iterator, bidirectional iterator, and random access iterator refer to kinds of iterators, not type names. The actual type names will be something like std::vector<int>::iterator, which in this case happens to be a random access iterator.

Self-Test Exercise

4. Suppose the vector v contains the letters 'A', 'B', 'C', and 'D' in that order. What is the output of the following code?

   vector<char>::iterator i = v.begin();
   i++;
   cout << *(i + 2) << " ";
   i−−;
   cout << i[2] << " ";
   cout << *(i + 2) << " ";

Constant and Mutable Iterators

The categories forward iterator, bidirectional iterator, and random access iterator each subdivide into two categories: constant and mutable, depending on how the dereferencing operator behaves with the iterator. With a constant iterator the dereferencing operator produces a read-only version of the element. With a constant iterator p, you can use *p, for example, to assign it to a variable or output it to the screen, but you cannot change the element in the container by, for example, assigning it to *p. With a mutable iterator p, *p can be assigned a value and that will change the corresponding element in the container. The vector iterators are mutable, as shown by the following lines from Display 18.1:

cout << "Setting entries to 0:\n";
for (p = container.begin(); p != container.end(); p++)
    *p = 0;

If a container has only constant iterators, you cannot obtain a mutable iterator for the container. However, if a container has mutable iterators and you want a constant iterator for the container, you can have it. You might want a constant iterator as a kind of error checking if you intend that your code not change the elements in the container. For example, the following will produce a constant iterator for a vector container named container:

std::vector<char>::const_iterator p = container.begin();

or equivalently

using std::vector<char>::const_iterator;
const_iterator p = container.begin();

With p declared in this way, the following would produce an error message:

*p = 'Z';

For example, Display 18.2 would behave exactly the same if you change

vector<int>::iterator p;

to

vector<int>::const_iterator p;

However, a similar change would not work in Display 18.1 because of the following line from the program in Display 18.1:

*p = 0;

Note that const_iterator is a type name, while constant iterator is the name of a kind of iterator. However, every iterator of a type named const_iterator will be a constant iterator.

Constant Iterator

A constant iterator is an iterator that does not allow you to change the element at its location.

Reverse Iterators

Sometimes you want to cycle through the elements in a container in reverse order. If you have a container with bidirectional iterators, you might be tempted to try

vector<int>::iterator p;
for (p = container.end(); p != container.begin(); p−−)
    cout << *p << " ";

This code will compile, and you may be able to get something like this to work on some systems, but there is something fundamentally wrong with this: container.end() is not a regular iterator, but only a sentinel, and container.begin() is not a sentinel.

Fortunately, there is an easy way to do what you want. For a container with bidirectional iterators, there is a way to reverse everything using a kind of iterator known as a reverse iterator. The following will work fine:

vector<int>::reverse_iterator rp;
for (rp = container.rbegin(); rp != container.rend(); rp++)
    cout << *rp << " ";

The member function rbegin() returns an iterator located at the last element. The member function rend() returns a sentinel that marks the “end” of the elements in the reverse order. Note that for an iterator of type reverse_ iterator, the increment operator ++ moves backward through the elements. In other words, the meanings of −− and ++ are interchanged. The program in Display 18.3 demonstrates a reverse iterator.

Display 18.3 Reverse Iterator

 1    //Program to demonstrate a reverse iterator.
 2    #include <iostream>
 3    #include <vector>
 4    using std::cout;
 5    using std::endl;
 6    using std::vector;
 7    int main()
 8    {
 9        vector<char> container;
10        container.push_back('A');
11        container.push_back('B');
12        container.push_back('C');
13        cout << "Forward:\n";
14        vector<char>::iterator p;
15	  for (p = container.begin(); p != container.end(); p++)
16            cout << *p << " ";
17        cout << endl;
18     
19        cout << "Reverse:\n";
20        vector<char>::reverse_iterator rp;
21	  for (rp = container.rbegin(); rp != container.rend(); rp++)
22            cout << *rp << " ";
23        cout << endl;
24        return 0;
25    }

Sample Dialogue

Forward:
A B C
Reverse:
C B A

Reverse Iterators

A reverse iterator can be used to cycle through all elements of a container, provided that the container has bidirectional iterators. The general scheme is as follows:

STL_Container<type>::reverse_iterator rp;
for (rp = c.rbegin(); rp != c.rend(); rp++)
     Process_At_Location rp;

The object c is a container class with bidirectional iterators.

The reverse_iterator type also has a constant version, which is named const_reverse_iterator.

Other Kinds of Iterators

There are other kinds of iterators that we will not cover in this book. Briefly, two kinds of iterators you may encounter are an input iterator, which is essentially a forward iterator that can be used with input streams, and an output iterator, which is essentially a forward iterator that can be used with output streams. For more details, you will need to consult a more advanced reference.

Self-Test Exercises

5. Suppose the vector v contains the letters 'A', 'B', 'C', and 'D' in that order. What is the output of the following code?

   vector<char>::reverse_iterator i = v.rbegin();
   i++;
   i++;
   cout << *i << " ";
   i−−;
   cout << *i << " ";

6. Suppose you want to run the following code, where v is a vector of ints:

   for (p = v.begin(); p != v.end(); p++)
       cout << *p << " ";

   Which of the following are possible ways to declare p?

   std::vector<int>::iterator p;
   std::vector<int>::const_iterator p;