Modifying a Set While Iterating

ArraySet<T> implements a set with a backing array. The items are at indices 0 through size - 1, in no particular order. remove closes the gap by moving the last item into it. The iterator is an inner class that traverses the array with a cursor:

public class ArraySet<T> implements Set<T> {
  private T[] arr;   // the backing array
  private int size;  // how many items the set holds

  public boolean add(T item) {
    if (item == null) {
      throw new IllegalArgumentException();
    }
    if (indexOf(item) != -1) {
      return false;
    }
    if (size == arr.length) {
      grow();
    }
    arr[size] = item;
    size++;
    return true;
  }

  public boolean remove(T item) {
    if (item == null) {
      throw new IllegalArgumentException();
    }
    int i = indexOf(item);
    if (i == -1) {
      return false;
    }
    arr[i] = arr[size - 1];
    arr[size - 1] = null;
    size--;
    return true;
  }

  public Iterator<T> iterator() {
    return new ArraySetIterator();
  }

  // indexOf, grow, contains, and size are already implemented

  private class ArraySetIterator implements Iterator<T> {
    private int cursor = 0;

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

    public T next() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      return arr[cursor++];
    }
  }
}

This loop is meant to remove every even number from set:

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

At the start, the array is [8, 5, 7, 6], size is 4, and cursor is 0.

next() returns 8     [8, 5, 7, 6]   size 4   cursor 1
remove(8)            [6, 5, 7, _]   size 3   cursor 1
next() returns 5     [6, 5, 7, _]   size 3   cursor 2
next() returns 7     [6, 5, 7, _]   size 3   cursor 3
hasNext(): 3 < 3 is false, so the loop ends

The set holds 6, 5, and 7. remove(8) moved 6 into index 0, behind the cursor, so the loop never visited 6.

Solution

Add a counter of changes to the set:

private int modCount = 0;  // counts structural changes

In add, put modCount++; right after size++;. In remove, put modCount++; right after size--;.

private class ArraySetIterator implements Iterator<T> {
  private int cursor = 0;
  private int expectedModCount = modCount;

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

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