11.7 Iterators

Tools.h++ provides several distinct methods for iterating over a collection class. Most collections offer an apply member function, which applies your supplied function to every element of a collection class before returning. Another form of iteration is provided by separate collaborating iterator classes associated with many of the collections. For example, an RWTPtrDlistIterator<T> can be used to visit each element of an RWTPtrDlist<T> in turn. Iterators are described in Section 10.4 of Collection Classes.

All Tools.h++ standard library-based collection class templates provide standard iterators. These iterators are fully compliant with the Standard C++ Library requirements for iterators, making them a powerful tool for using the classes in conjunction with the Standard C++ Library -- especially the algorithms. Although full treatment of iterators is beyond the scope of this guide, your Standard C++ Library reference and tutorials will provide ample information.

The standard library-based collection class templates provide three types of iterators: forward, bi-directional, and random-access. Forward iterators allow unidirectional traversal from beginning to end. As suggested by the name, bidirectional iterators allow traversal in both directions -- front to back, and back to front. Random-access iterators are bidirectional as well, and further distinguished by their ability to advance over an arbitrary number of elements in constant time. All of these iterators allow access to the item at the current position via the dereference operator *.

Given iterator iter and an integral value n, the following basic operations are just some of those supported:

Again, your standard library documentation will describe all the operators and functions available for each type of iterator.

In addition to the iterators just described, the standard library-based collection class templates also provide two typedefs used to iterate over the items in a collection class: iterator, and const_iterator. You can use the iterator typedef to traverse a collection class and modify the elements within. You can use instances of const_iterator to traverse, but not modify, the collection class and access elements. For the associative container-based and sorted sequence-based collections, which do not allow modification of elements once they are in the collection class, the iterator and const_iterator types are the same.

Finally, the templates also provide two member functions that return actual iterators you can use for traversing their respective collection classes. These member functions are begin() and end(). Each of these member functions is overloaded by a const receiver so that the non-const version returns an instance of type iterator, and the const version returns an instance of type const_iterator.

Member function begin() always returns an iterator already positioned at the first item in the collection class. Member function end() returns an iterator which has a past-the-end value, the way a pointer to the NULL character of a null-terminated character string has a value that points "past the end." An iterator of past-the-end value can be used to compare with another iterator to see if you've finished visiting all the elements in the collection class. It can also be used as a starting point for moving backwards through collection classes that provide either bidirectional or random-access iterators. The one thing you cannot do with an end() iterator is deference it. Here's an example using iterators to move through a list and search for a match:

RWTValDlist<int> intCollection; // a list of integers

// ... < put stuff in the list >

// position iter at start: 
RWTValDlist<int>::iterator iter = intCollection.begin();

// set another iterator past the end:
RWTValDlist<int>::iterator theEnd = intCollection.end();

// iterate through, looking for a 7:
while (iter != theEnd) {       // test for end of collection
  if (*iter == 7)              // use '*' to access current element
    return true;               // found a 7
  ++iter;                      // not a 7, try next element
}
return false;                  // never found a 7

In the case of a map-based collection class, like RWMapVal<K,T,Compare>, iterators refer to instances of the Standard C++ Library structure pair<const K, T>. As you iterate over a map-based collection, you have access to both the key and its associated data at each step along the traversal. The pair structure provides members first and second, which allow you to individually access the key and its data, respectively. For example:

typedef RWTValMap<RWCString, RWDate, less<RWCString> > Datebook;

Datebook birthdays;
// ... < populate birthdays collection >

Datebook::iterator iter = birthdays.begin();

while (iter != birthdays.end()) {
  cout << (*iter).first              // the key
       << " was born on "
       << (*iter).second             // the data for that key
       << endl;

  ++iter;
};

Note that given a non-const reference to such a pair, you can still modify only the second element_the data associated with the key. This is because the first element is declared to be of type const K. Because the placement of objects within the collection class is maintained internally, based on the value of the key, declaring it as const protects the integrity of the collection class. In order to change a key within a map, you will have to remove the key and its data entirely, and replace them with a new entry.

It may not be obvious at first, but you can think of an iterator as a generalized pointer. Imagine a pointer to an array of ints. The array itself is a collection class, and a pointer to an element of that array is a random-access iterator. To advance to the next element, you simply use the unary operator ++. To move back to a previous element, you use --. To access the element at the current position of the iterator, you use the unary operator *. Finally, it is important to know when you have visited all the elements. C++ guarantees that you can always point to the first address past the end of an allocated array. For example:

int intCollection[10];         // an array of integers

// ... < put stuff in the array >

// position iter at start: 
int* iter = intCollection;

// set another iterator past the end:
int* theEnd = intCollection + 10;

// iterate through, looking for a 7:
while (iter != theEnd) {       // test for end of array
  if (*iter == 7)              // use '*' to access current element
    return true;               // found a 7
  ++iter;                      // not a 7, try next element
}
return false;                  // never found a 7

If you compare this code fragment to the one using standard iterators in Section 11.7.1, you can see the similarities. If you need a bit of help imagining how the standard iterators work, you can always picture them as generalized pointers.