Monday, September 22, 2003

Live from Chicago! Iterators, generators

Java has it wrong. The iterators in the Java Collections Framework are not actually iterators: they are generators. The real culprit is next() which does two things at once. It advances the iterator and then fetches the value therefrom. This is the generator model.

Contrast with iterators from the STL. Because they model a pointer, they have a separate advance and fetch operation implemented with operator++()/operator++(int) and operator*(). You may freely advanced an STL iterator without fetching the contents; and you may fetch and refetch the contents without needing to adjust the position of the iterator. Of course STL iterators do have the wart that they lack any hasNext() equivalent. Instead you have to carry around a second iterator to compare against to see when you've reached the end.

Why is this? It is because Java is paradigm-poor language while C++ is a paradigm-rich one. Java supports object-oriented programming and that is the end of the tale. C++ supports object-oriented programming, but also generic programming. STL iterators are definitely a generic idiom, not an object-oriented one. But Java has to fit an object-oriented shoe onto an iterator foot, so they compromise by using generators instead, objects which produce a new value upon request.

Incidentally, this is why remove() is so weird and has to be optional. Optional methods to an interface are a sign of design mismatch. There should instead be a Generator base interface with just hasNext() and next(), and a CollectionGenerator which extends Generator and adds advance() and get(). Implementors of CollectionGenerator simply write next() to call advance() and then return get(). To modify the underlying collection, extend CollectionGenerator further and add remove().

No comments: