What must iterators do

To see what iterators must be able to do, consider the body of a typical generic algorithm. The algorithm shown here is find, one of many generic algorithms. Its purpose is to search a collection to determine if a value occurs, and if so return a pointer to it.

The range of values to be searched is described by a pair of iterators. As long as their are values (that is, as long as first is not equal to last) we test the current value. If it is the value we seek, the loop will halt. Otherwise, the argument first will be incremented, which advances it to the next element.

We halt either when there are no more values, or when we have found the element we seek. In either case we return the value in first.

What is interesting is that this can be used either with ordinary pointers, or with iterators. We can use the same algorithm to find a value in an array, or to find an element is a linked list.

[audio] [real] Text to accompany slide7, in Chapter 16 of An Introduction to Object-Oriented Programming