Iterators: Taxonomy, strength, weakness, and efficiency

Iteration is an operation that traverses the objects of a collection object. Iterators are operators/methods widely used for iteration on a collection of objects. However, iterators were considered to be ad hoc and to be a sign of weakness in object-oriented programming languages. There is a need to formalize iterators and to study their strength and weaknesses. In this paper we first propose a taxonomy of iterators based on the number of data states and the number of control points. The taxonomy identifies four categories of iterators. The simplest one can be implemented straightforwardly in an object-oriented language. Iterators of other categories need transformations and are more difficult to design and implement. Finally, we compare the efficiency of iterators with other implementations of iteration. The results show that all iteration techniques tested, including iterators, have been well optimized and are almost as fast as directly coded loops using recent C++ compilers.