Fail-Fast Iterators

Have you ever thought about what will happen if you structurally modify a data structure while you are iterating over it?

A structural modification is any operation that adds or deletes one or more elements, or explicitly resizes the data structure.

Assume you are iterating over an ArraySet. While the iteration is going on, an element you've already visited (iterated over) is removed. This could happen in a concurrent program but here is a contrived example to showcase this scenario:

for (int num: myArraySet) {
  // do something with num
  if (feelingLucky()) {
    myArraySet.remove(num);
  }
}

Exercise Can you anticipate any issues with iteration?

Solution

In depends on the implementation of the iterator and the remove method. In general, the results of the iteration are undefined under a structural modification.

If we assume the removal strategy is the one we have discussed earlier, then the last element of the array will be swapped with the element to be removed. Effectively we will end the iteration not visiting (not knowing about) the last element before removal.

In Java's Collection Framework, it is (generally) prohibited for one thread (program, process) to modify a Collection while it (or another thread) is iterating over it.

When that happens, the iterator will throw ConcurrentModificationException.

Iterators that throw an exception to signal the collection was structurally modified during iteration are known as fail-fast iterators, as they fail quickly and cleanly, rather that risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Exercise How can you make a iterator "fail-fast"?

Hint: To make an iterator "fail-fast" we need to be able to tell that the data structure has been modified since the iteration started.

Solution

Here is one strategy: use a version number in the data structure class to achieve this.

  • The number starts at 0 and is incremented whenever a structural modification is performed.
  • Each iterator also "remembers" the version number it was created for.
  • We can then check for modifications by comparing version numbers in the Iterator operations: If we notice a mismatch, we raise an exception.

We have implemented this feature in the LinkedSet. Make sure to carefully study it when you get the solution code. Then, try to implement it for ArraySet.