In this section, we describe iterators and the special problem of testing iterators. Figure 1 contains the class declaration for IntegerSet, a simple class storing a set of integers. Assuming that s is an object of type IntegerSet, s.add(i) adds i to s, s.delete(i) removes i from s, and s.isMember(i) returns true or false according to whether i is in s.
Figure 1: IntegerSet class declaration
The IntegerSet iterator is provided by the remaining three calls. A call to s.reset() starts the iteration. Each call to s.next() returns some element of s. When each element has been returned exactly once, s.atEnd() returns true. However, for efficiency reasons, the elements need not be returned in the order in which they were added; the IntegerSet implementor is free to return the elements in any order, as long as each element is returned exactly once. Figure 2 illustrates the use of the IntegerSet iterator. The output of the program will be the integers 1, 2, and 3, in one of the six possible orderings.
Figure 2: IntegerSet iterator example
In commercial libraries, an iterator is often provided for each
collection class.
The fact that the element return order is unconstrained
causes problems for test suites with automated output checking.
For an object storing n elements, there are 
correct answers.
In abstract terms, the iterator testing problem is as follows.
Given a list 
of N integers and a list 
of N integers,
determine, with high probability, whether
is a permutation of 
.