Iterators: Decoupling Algorithms from Containers



This chapter has not had any significant translation yet.

Alexander Stepanov thought for years about the problem of generic programming techniques before creating the STL (along with Dave Musser). He came to the conclusion that all algorithms are defined on algebraic structures - what we would call containers.

In the process, he realized that iterators are central to the use of algorithms, because they decouple the algorithms from the specific type of container that the algorithm might currently be working with. This means that you can describe the algorithm without worrying about the particular sequence it is operating on. More generally, any code that you write using iterators is decoupled from the data structure that the code is manipulating, and thus your code is more general and reusable.

The use of iterators also extends your code into the realm of functional programming, whose objective is to describe what a program is doing at every step rather than how it is doing it. That is, you say “sort” rather than describing the sort. The objective of the C++ STL was to provide this generic programming approach for C++ (how successful this approach will actually be remains to be seen).

If you’ve used containers in Java (and it’s hard to write code without using them), you’ve used iterators - in the form of the Enumeration in Java 1.0/1.1 and the Iterator in Java 2. So you should already be familiar with their general use. If not, see Chapter 9, Holding Your Objects, under Iterators in Thinking in Java, 3rd edition (freely downloadable from

Because the Java 2 containers rely heavily on iterators they become excellent candidates for generic/functional programming techniques. This chapter will explore these techniques by converting the STL algorithms to Java, for use with the Java 2 container library.

© RemiZOffAlex