iterators and fail-fast

the picture

you know how you remove one element in a for-each and get an exception called ConcurrentModificationException, in a program with exactly one thread? kinda cursed. the name is about the iterator's point of view: something modified the list concurrently with it, meaning while it was in the middle of walking. that something was you.

think of a tour guide walking a group through a museum with a printed map. if a room gets closed mid-tour, the map is wrong, and a good guide stops instead of walking people into a wall. the map has a version number (the iterator's expectedModCount). the museum has the current one (modCount). the guide checks them at every doorway.

what a for-each really is

the compiler turns a for-each over a collection into an iterator loop:

for (String s : list) {
    if (s.equals("b")) list.remove(s);
}

Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String s = it.next();
    if (s.equals("b")) list.remove(s);
}

(the left side isn't wrong because it's a for-each. it's wrong because it calls list.remove while an iterator is walking list, and the for-each hides that iterator from you.)

ArrayList's iterator is three ints: cursor (the next index to return), lastRet (the index it returned last) and expectedModCount. hasNext() is just cursor != size. next() first checks modCount == expectedModCount, then returns elementData[cursor++].

void main() {
    List<String> list = new ArrayList<>(List.of("a", "b", "c", "d"));
    IO.println(list);
    for (String s : list) {
        if (s.equals("b")) list.remove(s);
    }
}

[a, b, c, d]
Exception in thread "main" java.util.ConcurrentModificationException

List<String> list = new ArrayList<>(List.of("a", "b", "c", "d"));
for (String s : list) {
    if (s.equals("c")) list.remove(s);
}
IO.println(list);

the fixes

for (String s : list) {
    if (s.isBlank()) list.remove(s);
}

list.removeIf(String::isBlank);

• removeIf(predicate) java 8+: the clean answer for "remove everything that matches". ArrayList's version is also faster than removing one by one: it marks the doomed elements first, then compacts the array in a single pass, instead of shifting the tail for every removal.
• iterator.remove(): removes the element next() just returned and resynchronises the iterator (cursor = lastRet, expectedModCount = modCount). use it when the decision needs more than a predicate.
• ListIterator: set and add through the iterator, for lists.
• maps: map.entrySet().removeIf(...), map.keySet().removeIf(...), and replaceAll / computeIfPresent for updating values.

void main() {
    List<String> a = new ArrayList<>(List.of("a", "b", "c", "d"));
    for (Iterator<String> it = a.iterator(); it.hasNext(); ) {
        if (it.next().equals("b")) it.remove();
    }
    List<String> b = new ArrayList<>(List.of("a", "b", "c", "d"));
    b.removeIf(s -> s.equals("b"));
    IO.println(a + " " + b);
 
    Map<String, Integer> m = new HashMap<>(Map.of("a", 1, "b", 2, "c", 3));
    m.entrySet().removeIf(e -> e.getValue() % 2 == 1);
    m.replaceAll((k, v) -> v * 10);
    IO.println(m);
}

[a, c, d] [a, c, d]
{b=20}

fail-safe iterators

the concurrent collections in java.util.concurrent don't throw CME. they promise something different instead.

CopyOnWriteArrayList copies its whole array on every write. an iterator grabs the array that existed when it was created (a snapshot) and walks that, while writers swap in new arrays:

import java.util.concurrent.CopyOnWriteArrayList;
 
void main() {
    List<String> list = new CopyOnWriteArrayList<>(List.of("a", "b", "c"));
    for (String s : list) {
        if (s.equals("a")) list.add("d");
        IO.print(s + " ");
    }
    IO.println(list);
}

a b c [a, b, c, d]

great for lists that are read constantly and changed rarely (listener lists, config), terrible for lists that change a lot (every write is O(n)). ConcurrentHashMap takes a third approach: its iterators are weakly consistent. they never throw, they visit each element at most once, and they may or may not reflect changes made after they started. more in concurrent collections.