External iterator classes are verbose to use and to define. You need to define an iterator class for each collection class, and you need to update them in parallel. To use it, you need to instantiate the iterator and make method calls to iterate, fetch and see if there are more.

In 99% of use cases, all you want to do is run a block of code against each element.

A fourth option, which is in the general case superior to all three of your options, is the internal iterator. It delegates management of the iteration to the collection, rather than adding repetitive boilerplate to your functional code.

An internal iterator is an instance method of a collection which is passed a function which it calls for each element in the collection.

An example of internal iterators is seen in Ruby's core collection classes.

For the technically-minded, let me demonstrate the difference between the two with code (Ruby, because it's shorter). (Download the code from http://dave.burt.id.au/ruby/pair.rb to see it indented properly.)

class Pair

attr_accessor :first, :last

def initialize(first = nil, last = nil)

@first = first

@last = last

end

# The internal iterator is an instance method

def each

yield first

yield last

end

# The external iterator is a full-blown, separate class

# which also wants an instance method to obtain an

# iterator instance

def iterator

Iterator.new(self)

end

# Wow, this iterator's definition is longer than the

# collection's!

class Iterator

def initialize(pair)

@pair = pair

@next = :first

end

def has_next?

@next.nil?

end

def next

case @next

when :first

@next = :last

first

when :last

@next = nil

last

else

fail

end

end

end

end

col = Pair.new "a", "b"

# Internal iterator: just pass the block to the iterator

col.each do |x|

print x

end

# External iterator: instantiate, check, fetch

iter = col.iterator

while iter.has_next?

x = iter.next

print x

end

<blockquote>There are many ways to offer traversal ....

<br/>

First, it is possible to use an index into the collection. The advantage of this is that it appears simple and there is no coupling to the collection's data structure. The main disadvantage is that it is only practical if indexing is a constant-time operation, which it won't be for linked data structures.

</blockquote>

Well, sort of. If you are really interested in such dual-purpose access - it can be quite handy - then maintaining an index of the list on the side is worth considering. The obvious cost is both more memory and complexity (internally) but the user doesn't have to fret. And if you want to index by something other than position in the list, you can create a hash or other structure to make getting to the first element simpler.

At some point you run the risk of creating your own database, of course, which may or not be the most efficient use of your efforts in the long run.

The idea of using Internal Iterator (aka Enumeration Method) was mentioned in the article. However, in claiming that "there are essentially only three general designs that keep the collection's internal representation hidden from the caller" one of the important constraints governing the choice of technique was that "the caller needs to be able to know the position of elements in some way". Effective a pattern as Enumeration Method is, this particular constraint excludes it from the running. Change the design criteria, such as requiring exclusive locked access to a collection over a loop, and the selection changes, in this case to include Enumeration Method and exclude Iterator.

The topic of encapsulated iteration, and the trade-offs between these patterns, are interesting enough in their own right to justify another article (see http://www.regdeveloper.co.uk/2006/09/04/to_iterate_human/).

In terms of creating a kind of dual representation within a collection to support more time efficient indexing, yes this can be a consideration if indexing is a strong requirement. However, if is not, it will always be a more expensive and complex approach. As noted, it will always be more costly in terms of space and maintaining a side-by-side representation will increase code complexity and, slightly, the cost of other operations that modify the collection, because they must now keep the index structure in synch as well.