7. Iterators

Iterators are generalized pointers that may be used to traverse the contents of a sequence (for example, an STL container or a C++ array).

• Iterators provide data access for both reading and writing data in a sequence.
• A C++ pointer is an iterator, but an iterator is not necessarily a C++ pointer.
• Iterators, like pointers can be dereferenced, incremented and decremented.
• At any point in time, an iterator is positioned at exactly one place in one collection, and remains positioned there until explicitly moved.

7.1 Types of Iterators

7.1.1 Table of iterator categories

There are five categories of iterators. With the exception of input and output iterators, the relationship between each category of iterator is hierarchical: each iterator inherits the characteristics and behavior of the previous type, as Table 4 illustrates:

Table 4. Iterator Categories and Characteristics

Iterator category	Characteristics
input	Can read one item at a time; can only move forward (increment)
output	Can write one item at a time; can only move forward (increment)
forward	Multiply derived from input and output iterators; combines their characteristics (read or write)
bidirectional	Derived from forward iterator; adds ability to move backwards (decrement)
random access	Derived from bidirectional; adds ability to jump forward or backward by an arbitrary distance

In classical C++ terms, input and output iterator classes are base classes, the forward iterator class is doubly derived from both the input and output iterator classes, the bidirectional iterator class is derived from the forward iterator class, and the random access iterator class is derived from the bidirectional iterator class. This hierarchy implies the following:

• An algorithm that requires only input or output iterators can also be used with forward, bidirectional, or random access iterators.
• An algorithm that can be used with forward iterators can also be used with bidirectional or random access iterators.
• An algorithm that can be used with bidirectional iterators can also be used with random access iterators.

It should also be noted that regular C++ pointers fit the characteristics of a random access iterator (and in fact can be used as a random access iterator for STL operations that support random access iterators).

7.2 Iterator Interface Requirements

Different iterator types are required to have a minimum set of interface functions defined, which conform to the behaviors described below. For the following, the value type T is understood to be the data type of the underlying container that the iterator is interfacing with (for example, for a vector<int, allocator<int> >, T = int).

7.2.1 Input iterator interface requirements

A class or built-in data type X can be used as an input iterator for the value type T if and only if the following expressions are defined for X and meet the behavioral requirements stated below. For Table 5, assume a and b are values of type X, r is a reference of type X, and t is a value of type T.

Table 5. Input Iterator Required Behaviors

Operator/function	Required behavior
Copy Constructor	X(a) == a X b(a) must result in a == b
operator=	X b = a and a = b both must result in a == b
operator==	The return type must be convertible to bool and ‘==’ must be an equality relation (such as reflexive, transitive, or associative.)
operator!=	The return type must be convertible to bool and a != b must be the same as !(a == b)
operator*	The return type must be convertible to T. If a == b then *a == *b. Dereferencing an input stream returns a read-only reference of type T. This means that operator* can only appear on the right-hand side of an assignment statement (is an rvalue). t = *a results in t being assigned a value through a.
operator++ (prefix)	The return type must be convertible to type const X&. It is also assumed that the return type is dereferenceable or is the “past-the-end” value of the container.
operator++(int) (postfix)	The return must be convertible to type const X&. The result must be identical to {X tmp = r; ++r; return tmp; }.

7.2.2 Output iterator interface requirements

A class or built-in data type X can be used as an output iterator for the value type T if and only if the following expressions are defined for X and meet the behavioral requirements stated below. For Table 6, assume a and b are values of type X, r is a reference of type X, and t is a value of type T.

Table 6. Output Iterator Required Behavior

Operator/function	Required behavior
Copy Constructor	*a = t and *X(a) = t. The result of X b(a) is that b is a copy of a (Note that equality and inequality are not necessarily defined for output iterators).
operator=	The result of X b = a is that b is a copy of a.
operator*	*a = t results in the value of t being written to the location referenced by a. The return value of the operation is meaningless. Note that the only valid use of operator* on output iterators is on the left-hand side of an assignment (as an lvalue).
operator++ (prefix)	The return type must be convertible to type const X&. It is also assumed that the return type is dereferenceable or is the “past-the-end” value of the container.
operator++(int) (postfix)	The return type must be convertible to type const X&. The result must be identical to: {X tmp = r; ++r; return tmp; }

7.2.3 Forward iterator interface requirements

A class or built-in data type X can be used as a forward iterator for the value type T if and only if the following expressions are defined for X, and meet the behavioral requirements stated below. For Table 7, assume a and b are values of type X, t is a value of type T, and r and s are references of type X.

Table 7. Forward Iterator Required Behavior

Operator/function	Required behavior
Default Constructor	X() and X a both create an iterator whose position is undefined
Copy Constructor	X(a) == a and X b(a) must result in a == b
operator=	X b = a and a = b must result in a == b
operator==	The return type must be convertible to bool, and ‘==’ must be an equality relation (reflexive, transitive, associative, etc.)
operator!=	The return type must be convertible to bool, and a != b must be the same as !(a == b)
operator*	The return type must be convertible to T. If a == b, then *a == *b. If X is mutable (writable), then *a = t is valid and results in the value of t being written to the location referenced by a.
operator++ (prefix)	The return type must be convertible to type const X&. It is also assumed that the return type is dereferenceable or is the “past-the-end” value of the container. In addition, r == s implies that ++r == ++s.
operator++(int) (postfix)	The return type must be convertible to type const X&. The result must be identical to: {X tmp = r; ++r; return tmp; }

7.2.4 Bidirectional iterator interface requirements

A class or built-in data type X can be used as a bidirectional iterator for the value type T if and only if X conforms to the requirements of a forward iterator and defines the following expressions, which meet the behavioral requirements stated below. For Table 8, assume r and s are references of type X.

Table 8. Bidirectional Iterator Required Behavior

Operator/function	Required behavior
operator-- (prefix)	The return type must be convertible to type const X&. In addition, the following properties must hold: --(++r) == r, and r == s implies that --r == --s.
operator--(int) (postfix)	The return type must be convertible to type const X&. The result must be identical to: {X tmp = r; --r; return tmp;}

7.2.5 Random Access Iterator Interface Requirements

A class or built-in data type X can be used as a random access iterator for the value type T if and only if X conforms to the requirements of a bidirectional iterator and defines the following expressions, which meet the behavioral requirements stated below. For Table 9, assume a and b are values of type X, r is a reference of type X, and n is an int.

Table 9. Random Access Iterator Required Behavior

Operator/function	Required behavior
operator+=	The return type must be convertible to X&. The result of r += n must be the same as computing ‘r++’ n times if n > 0 or ‘r--‘ abs(n) times if n < 0 (trivially, r+=0 == 0).
operator+	The return type must be convertible to X. The result of a + n must be identical to: {X tmp = a; return tmp += n; }. The result of n + a must be the same as a + n (reflexive).
operator-=	The return type must be convertible to X&. The result of r -= n must be the same as the result of r += (-n)
operator-	The result of a - n must be convertible to X, and identical to {X tmp = a; return tmp -= n; }. The result of a - b must be convertible to an integral type that can describe the difference between two locations (difference_type). If a - b = n, then: a + n = b;
operator[]	The return type must be convertible to T. The result of a[n] must be identical to *(a + n).
operator<	The return type must be convertible to bool and operator< must be a total ordering relation
operator>	The return type must be convertible to bool. The result of a > b must be identical to: a < b.
operator>=	The return type must be convertible to bool. The result of a >= b must be identical to: !(a < b).
operator<=	The return type must be convertible to bool. The result of a <= b must be identical to: !(a > b).

Note   STL provides global definitions of ">," ">=," "<=," and "!=" defined in terms of "==" or "<". This means that any object which defines "==" and "<" gets the rest “for free.”

7.3 Categories of Iterators Associated With STL Containers

The description of each STL container class includes the category of iterator types they provide. Table 10 lists the various STL containers and the iterators associated with each:

Table 10. STL Containers and Iterators

STL container	Type of iterator
vector	random access
deque	random access
list	bidirectional
multiset	bidirectional
set	bidirectional
multimap	bidirectional
map	bidirectional

It is not necessary to remember which type of iterator works with which container. Each container, C<T>, supplies typedefs for iterators:

• iterator (mutable)
• const_iterator (nonmutable)

To declare an iterator, simply use the syntax C<T>::iterator or C<T>::const_iterator (see example below).

The following example illustrates how to declare an iterator for a vector of ints and use that iterator to display the values:

#include <vector>
#include <iostream>
typedef vector<int, allocator<int> > INTVECT;
void main()
{
     INTVECT myVector(5);     // declare a vector of 5 ints
     INTVECT::iterator myIter;     // declare an iterator for the vector
     for(int iv = 0; iv < 5; iv++)
          myVector[iv] = iv;      // fill the vector with values
     for(myIter = myVector.begin(); myIter != myVector.end(); myIter++)
          cout << *myIter << “, “;
     cout << endl;
}

Output:

0, 1, 2, 3, 4,

Note that the termination condition for the "for loop" was “myIter != myVector.end()” instead of “myIter < myVector.end()”. In the above example, the < operator would have worked because the iterator supplied by a vector is a random access iterator. If our container had been a list, the < operator would not have worked, as the < operator is not defined for the bidirectional iterator that list supplies. The moral of the story is that in such a situation, using != will give the same result and you don’t have to remember which kind of iterator a particular container is supplying.

7.4 Stream Iterators

One of the reasons input and output iterators are defined separately is so that they can be associated with I/O streams.

7.4.1 Istream iterators

STL provides a predefined iterator class called istream_iterator. The istream_iterator class is an input iterator. In Visual C++ version 4.2, istream_iterator<Value_Type, Char_Type, Traits_Type> is derived from the base class iterator<Value_Type, Char_Type, Traits_Type> and conforms to the requirements of an input iterator as described above. istream_iterator provides two constructors, one that takes an input stream as an argument (and ties the iterator to that stream). The other takes no arguments, and is used to provide an end-of-stream marker for several algorithms.

Note   Books Online says that istream_iterator takes two template parameters, Value_Type and Distance_Type, and is derived from input_iterator<Value_Type, Distance_Type>. The classes were modified to the structure stated above for Visual C++  4.2 to overcome some compiler limitations. A future version of Visual C++ will return to the structure and hierarchy reflected in the Books Online. The STL is an emerging standard and will undoubtedly be changed again in the future. In order to minimize the impact these types of changes will have on existing code, the use of typedefs is highly recommended when declaring a particular instantiation of any STL component.

The following fills a vector of strings from an input stream using the copy algorithm in conjunction with an istream_iterator:

// STRING_INPUT is an istream iterator for objects of type string
typedef istream_iterator<string, char, char_traits<char> > STRING_INPUT;
// STRVECTOR is a vector which holds objects of type string
typedef vector<string, allocator<string> > STRVECTOR;
void main()
{
     string FileName;
     STRVECTOR theStrings;
     cout << "Enter Input File Name: ";
     cin >> FileName;
     ifstream ifs(FileName.c_str());   // Open the file read only
     // read to eof, storing each string in theStrings.
     copy(STRING_INPUT(ifs),STRING_INPUT(),back_inserter(theStrings));
}

See section 7.6.1 for more information on the back inserter class.

7.4.2 Ostream iterators

STL provides a predefined iterator class called ostream_iterator. The ostream_iterator class is an output iterator. In Visual C++ version 4.2, ostream_iterator<Value_Type, Char_Type, Traits_Type> is derived from the base class iterator<Value_Type, Char_Type, Traits_Type> and conforms to the requirements of an output iterator as described above. ostream_iterator provides two constructors, one which takes an output stream as an argument (and ties the iterator to that stream). The other takes two arguments, an output stream (with the same effect as the one argument ctor) and a delimiting character, which will be inserted into the stream after each object.

The following is the sample from the istream_iterator section with a new addition. Now, the program prints the strings it has read to stdout, each on a new line. It accomplishes this by again calling the copy algorithm, this time in conjunction with the string container, and sends its output to an ostream_iterator object associated with cout:

// STRING_INPUT is an istream_iterator for objects of type string
typedef istream_iterator<string, char, char_traits<char> > STRING_INPUT;
// STRING_OUTPUT is an ostream_iterator for objects of type string
typedef ostream_iterator<string, char, char_traits<char> > STRING_OUTPUT;
// STRVECTOR is a vector which holds objects of type string
typedef vector<string, allocator<string> > STRVECTOR;
void main()
{
     string FileName;
     STRVECTOR theStrings;
     cout << "Enter Input File Name: ";
     cin >> FileName;
     ifstream ifs(FileName.c_str());   // Open the file read only
     // read to eof, storing each string in theStrings.
     copy(STRING_INPUT(ifs),STRING_INPUT(),back_inserter(theStrings));
// print the contents of theStrings to cout, 
// using copy and STRING_OUTPUT
     copy(theStrings.begin(), theStrings.end(),  
          STRING_OUTPUT(cout,"\n"));
}

7.5 Iterator Adapters

An adapter in STL is a wrapper class that takes an existing class and provides it with a new interface. There are two adapters provided by the STL for iterators: reverse iterators and insert iterators.

7.5.1 Reverse iterators

Reverse iterator adapters transform their iterators to traverse a collection from back to front. There are two adapters supplied by the STL: reverse_bidirectional_iterator, which transforms bidirectional iterators, and reverse_iterator, which transforms random access iterators. Each container, C<T>, supplies typedefs for reverse iterators:

• reverse_iterator (mutable)
• const_reverse_iterator (nonmutable)

To declare an iterator, simply use the syntax C<T>::reverse_iterator or C<T>::const_reverse_iterator (see example below).

The following example illustrates how to declare a reverse iterator for a vector of ints and use that iterator to display the values in reverse order:

#include <vector>
#include <iostream>
typedef vector<int, allocator<int> > INTVECT;
void main()
{
     INTVECT myVector(5);     // declare a vector of 5 ints
     // declare a reverse iterator for the vector
     INTVECT::reverse_iterator myIter; 
     for(int iv = 0; iv < 5; iv++)
          myVector[iv] = iv;      // fill the vector with values
     for(myIter = myVector.rbegin(); myIter != myVector.rend(); 
         myIter++)
          cout << *myIter << “, “;
     cout << endl;
}

Output:

4, 3, 2, 1, 0,

Note the use of rbegin and rend in the above example. Just as each type of STL container supplies begin and end member functions (which return regular iterators), each also supplies rbegin and rend member functions (which return reverse iterators).

When reverse iterators are passed to a generic algorithm, they make the algorithm work in reverse. Consider the sort algorithm:

sort(myVector.begin(), myVector.end());

Sorts the contents of myVector into ascending order, and:

sort(myVector.rbegin(), myVector.rend());

Sorts the contents into ascending order as seen from back to front, which results in the contents being sorted into descending order.

7.6 Insert Iterators

Insert iterators put an algorithm into insert mode. The most useful effect of this is that insert iterators use insert operations (which expand allocated memory as needed) instead of assignment operations (which assume the space is available) to add objects to a target container. This is done via a redefinition of operator*, so that *i = … calls one of the container’s insert functions instead of operator=. Consider the following use of the copy algorithm to copy the objects from a deque to a vector:

// v1 is and empty vector
vector<int, allocator<int> > v1;   
// d1 holds 100 1’s
deque<int, allocator<int> > d1(100, 1);
// causes an error
copy(d1.begin(), d1.end(), v1.begin());  

The call to copy above will cause a run-time error (probably a GPF) when *(v1.begin()) = *(d1.begin()) is called, because v1 does not have any memory allocated for itself. Replacing v1.begin() with an insert iterator, such as back_inserter will solve the problem as follows:

copy(d1.begin(), d1.end(), back_inserter(v1));  // executes correctly

Now, *(v1.begin()) = *(d1.begin()) (and all subsequent assignments) map to vector::push_back instead of vector::operator=. STL provides three insert adapters: back_inserter, front_inserter, and inserter.

7.6.1 back_inserter iterators

As noted above, back_inserter iterators call the push_back method of the container instead of operator= when the iterator’s operator* method is invoked as an l-value. This means that back_inserter iterators can only be used with containers that support the push_back method (vector, deque, list). The following illustrates a declaration of a back_inserter iterator to be associated with a vector:

// declare a vector of ints
vector<int, allocator<int> > iV;   
// declare a back_inserter iterator associated with iV
back_inserter iVPtr(iV);

7.6.2 front_inserter iterators

Because front_inserter iterators call the push_front method of the container instead of operator= when the iterator’s operator* method is invoked as an l-value, front_inserter iterators can only be used with containers that support the push_front method (deque, list). The following illustrates a declaration of a front_inserter iterator to be associated with a list:

// declare a list of ints
list<int, allocator<int> > iL;
// declare a front_inserter iterator associated with iL
front_inserter iLPtr(iL);

7.6.3 Inserter iterators

Inserter iterators call the insert method of the container instead of operator= when the iterator’s operator* method is invoked as an l-value. This means that inserter iterators can be used with all the STL containers, even the sorted associative containers, as they all support an insert method. The following illustrates a declaration of an inserter iterator to be associated with a set that inserts its objects beginning at the second item in the set.

// declare a set of ints
set<int, less<int>, allocator<int> > iS;   
// declare an inserter iterator associated with iS
inserter(iS, iS.begin() + 1);