Modifying a Set While Iterating

We saw that two iterators over the same set are independent of each other. But an iterator is not independent of the set itself. An iterator remembers where it is in the set, using a cursor index or a current node. This works only if the set does not change while we iterate. If we add or remove an element during the iteration, the saved position can become wrong.

Suppose we want to remove every even number from a set:

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

To see what goes wrong, let’s trace it on an ArraySet built from add(1), add(2), add(3), add(4). Its array is [1, 2, 3, 4] and size is 4. The iteration begins with the cursor at index 0:

┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
└───┴───┴───┴───┘
  ↑
cursor

next() returns arr[0], which is 1, and moves the cursor to 1. That value is odd, so nothing happens:

┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
└───┴───┴───┴───┘
      ↑
   cursor

next() returns arr[1], which is 2, and moves the cursor to 2. That value is even, so we call set.remove(2):

┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
└───┴───┴───┴───┘
          ↑
       cursor

remove finds 2 at index 1. As ArraySet always does, it moves the last element into the gap. So 4 moves into index 1, the slot at index 3 is cleared, and size becomes 3:

┌───┬───┬───┬───┐
│ 1 │ 4 │ 3 │░_░│
└───┴───┴───┴───┘
          ↑
       cursor

next() returns arr[2], which is 3, and moves the cursor to 3. That value is odd, so nothing happens:

┌───┬───┬───┬───┐
│ 1 │ 4 │ 3 │ _ │
└───┴───┴───┴───┘
              ↑
           cursor

Now hasNext() checks cursor < size. That is 3 < 3, which is false, so the loop ends.

We visited 1, 2, and 3, and never looked at 4. When remove(2) moved 4 into index 1, it moved it behind the cursor, which had already gone past that slot. So 4, an even number we meant to remove, was skipped entirely and is still in the set.

LinkedSet behaves differently. Its iterator holds a current node, which has already moved past the element next() just returned, so this particular loop works. The LinkedSet iterator breaks when the loop removes the element that current points to. That node is unlinked from the set, but it keeps its next reference. So the iterator still returns it, and the iteration goes on over elements that are no longer in the set.

In both cases we get a wrong answer, and no error is raised. Which wrong answer we get depends on where the elements are in the set. A bug like this can pass every quick test we try and show up only on certain data.

You might think the fix is simply not to modify a set while iterating over it. That is the right rule, but it is harder to follow than it sounds. The code that changes the set is not always inside the loop. The loop body might call a method, which calls another method, which removes from the set. Or another part of the program might hold a reference to the same set and change it. So you can break this rule without noticing. In the next section, we make the iterator detect the change itself.