Failing Fast

We want the iterator to notice that the set has changed and stop. The simplest way is to have the set count its own modifications.

We add a field to the set that counts structural changes (let’s call this modCount), and we increment it whenever add or remove actually changes the set:

public boolean add(T item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  if (indexOf(item) != -1) {
    return false;  // already present; no change, so modCount is untouched
  }
  // ... append the item ...
  modCount++;
  return true;
}

The field starts at 0 (private int modCount = 0;), and remove increments it the same way as add does.

When an iterator is created, it records the set’s current modCount. Every next() then checks whether modCount still equals the recorded value. If it does not, the set was modified since the iteration began, and the iterator throws a ConcurrentModificationException:

private class ArraySetIterator implements Iterator<T> {
  private int cursor = 0;
  private int expectedModCount = modCount;  // the set's count when this walk began

  @Override
  public boolean hasNext() {
    return cursor < size;
  }

  @Override
  public T next() {
    if (modCount != expectedModCount) {
      throw new ConcurrentModificationException();
    }
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    return arr[cursor++];
  }
}

The iterator can read the set’s modCount directly because it is an inner class. We pointed out this access earlier, when we chose to make the iterator an inner class. You also need to import java.util.ConcurrentModificationException.

Now let’s run the loop that removes every even number again:

for (Integer x : set) {
  if (x % 2 == 0) {
    set.remove(x);
  }
}

When the iteration begins, the iterator sets expectedModCount to the set’s modCount. After next() returns 2, the loop calls set.remove(2), which removes an element and increments modCount. On the next call to next(), the iterator sees that modCount no longer equals expectedModCount and throws ConcurrentModificationException. Instead of silently skipping 4, the program stops at the first call to next() after the set was changed.

This is a standard technique for making iterators robust. It is called the fail-fast strategy: the iterator fails (throws an exception) as soon as it detects a problem, instead of continuing and returning a wrong answer. It works no matter where the change comes from. The change could come from the loop, from a method the loop calls, or from another part of the program that holds the same set. In every case the change goes through one of the set’s own methods, and every method that changes the set increments modCount. Usually that method is add or remove. A contains that reorders the set, as move-to-front and transpose do, also changes the set, so it increments modCount too.