External Iterator

An ExternalIterator is an object that represents a location within a collection. They are used in conjunction with a loop to traverse all the elements in the collection. Each iteration of the loop contains a statement that increments the logical position of the object within the collection. The rest of the instructions in the loop body can use the ExternalIterator to examine and, often, change the contents of the collection at the location it represents.

ExternalIterators are very flexible. They can be used together to create complex simultaneous iterations, they can be used to share and update the state of the iteration across multiple function calls, they can even be used as object references in some cases. But all manipulations of ExternalIterators are manual, so they require a new loop construct to be written every single time they are used for their normal task of iterating through the members of a collection. Often this means introducing a low level construct into an otherwise high-level method thereby obscuring intention. These loops are also a potential source of bugs, such as the IteratorInvalidationProblem.

Compare with InternalIterators and see InternalizeExternalIterators and TransfoldPattern for ways to avoid the limitations of ExternalIterators.

Are Rubyists and Smalltalkers aware of the family of zipWiths? zipWiths capture at least the "go down N lists simultaneously while applying this function to each of them" kind of external iteration. If you need some other kind of iteration, it's likely that you're flattening a more accurate representation of your problem into a list unnecessarily.


Please clarify "increments the logical position of the object". Thanks.

If the iterator is for an array collection, there will (probably) be an integer index that points to the current array item. So, "increments the logical position of the object" means "gets the next array item by adding 1 to the current index value".

In an iterator for a linked list collection, "increments the logical position of the object" means "gets the next item by following the current item's link to the next item in the list".

In an iterator for a binary tree collection using a depth-first iterator, "increments the logical position of the object" means "gets the next item in depth-first order".

In an iterator for a binary tree collection using a breadth-first iterator, "increments the logical position of the object" means "gets the next item in breadth-first order".

In an iterator for a RDBMS table, "increments the logical position of the object" means "uses the cursor to fetch the next row".

In many iterators, "increments the logical position of the object" is handled by a method called next().

Is this a copy of the "current node", or merely a pointer to it? Does it contain copies or references to the attributes and methods of the actual node?

It depends on the implementation and isn't part of the definition of "external iterator", but in practice it's usually a reference or pointer to the "current node" rather than a copy.


CategoryCodingConventions


EditText of this page (last edited January 29, 2013) or FindPage with title or text search