Navigate/Search
« Information Thief
Data-structure slicing »

Iteratator Design

Q: Why would anyone use iterators when there is a foreach construct?

  1. // examples in the D programming language
  2. // http://digitalmars.com/d/
  3. auto iter = collection.iterator;
  4. while(iter.more) {
  5.     auto v = iter.next;
  6.     // …
  7. }
  1. foreach (v; collection) {
  2.     …
  3. }

Answers:
1. Enumerable is the only common interface.
Why? Mixing I/O streams and containers.
Solution:
Make ‘enumerable’ compatible with the foreach construct (ie. it implements opApply).

2. Iterators are used to transform the data structure (ala c++ stl).
Solution A:
Have mutable iteration either as default or as an extra call.

  1. foreach (inout i; collection.mutating)
  2.     i++;

Two reasons to have them as an extra protocol:

  1. The normal interface should be used for guarded operations
  2. Some collections (eg. sets) should not be able to be mutated in such a manner. Although this can be overcome by the default iterator itself, it supplies a consistent interface.

Solution B:
But what about the “walk of death?” One idea I’ve seen is a purging iterator.

  1. foreach (inout purge, inout i; collection.purging) {
  2.     if (i.stale)
  3.         purge = true;
  4.     else
  5.         i++;
  6. }

3. Iterators are used as markers.
Why? It Gives constant time access to elements in expensive constructs, such as
linked lists.

  1. list.collection.insert(i, b);

This kind of operation greatly speeds insertion in middle of lists; it is
otherwise a O(n) operation: the cost to move every element in an array-based
list, as well as the cost of finding position i in a linked list.

This should not be used with containers with no concept of order, such as
hash-based constructs.

Solution A:
Make an easy way to iterate from one iterator to another or to the end of a container

  1. foreach (i; Range[iter1..iterEnd])
  2. { … }
  3.  
  4. foreach (i; Range[iter])
  5. { … }
  6.  
  7. foreach (iter, i; IteratorRange[iter1..iterEnd])
  8. { … }

Solution B:
Make it easy to use the iterator in connection with the collection.

  1. collection.insertBefore(iter);

Solution C:
Make it easy to re-get the value from an iterator.

  1. iter.value

Solution D:
In light of Solutions A-C, rename Iterator to Marker and have it non-enumerable (ie. it only has a value() method.) This, however, will break compatibility with I/O iterators; therefore, it will probably never happen.

4. The iterators are wrapped into transformations or chains.
Why? Self evident-but highly useful.

5. Parallel Iteration
Solution:
Why? It just cannot be done in a foreach construct.

6. Speed.
Is this really an issue? Some of the solutions above assume a speed aspect (2A,B and 3B, for example).

Conclusions:

Looking at these answers, I can see which ones are likely to be useful, at least used most often. Iterators are not cursors (markers). The concern of speed whilst inserting into the middle of a data structure should govern the use of the data structure. Of course, if the data structure does not support that crucial operation it has lost value; but in the case of the a structure like a deque is more appropriate.

Markers are out, but I have learned some useful things in this little exercize.

Published at Wednesday, July 9th, 2008 @ 1:04 pm Category professional
Comments feed RSS 2.0 Trackback Trackback

Leave a Reply