Итераторы Java

Каждый раз, когда вы пишете for (T x : collection) в Java, вы задействуете скрытую пару: интерфейс Iterable<T>, позволяющий коллекции участвовать в цикле, и Iterator<T>, который он передаёт циклу. Цикл for-each — это синтаксический сахар; Iterator — это движок. Понимание того, что он делает — и какие исключения могут выбрасывать его три метода — это разница между «обход моего списка работает большую часть времени» и «я точно знаю, когда он сломается».

Эта глава посвящена обычному Iterator<E>. Более богатый ListIterator<E>, который может проходить коллекцию в обратном направлении и изменять её во время итерации, рассматривается в отдельной главе следующей.

Два интерфейса

Iterable<T> — это контракт для «вещей, по которым можно итерироваться»:

public interface Iterable<T> {
  Iterator<T> iterator();
  default void forEach(Consumer<? super T> action) { ... }
  default Spliterator<T> spliterator() { ... }
}

Iterator<T> — это курсор:

public interface Iterator<E> {
  boolean hasNext();
  E next();
  default void remove() { throw new UnsupportedOperationException(); }
  default void forEachRemaining(Consumer<? super E> action) { ... }
}

Каждый Collection<E> расширяет Iterable<E> — вот почему цикл for-each работает с List, Set, Queue. (Map не является Iterable; вы итерируете его entrySet(), keySet() или values() — см. как итерировать HashMap.) Цикл for-each:

for (String name : names) { System.out.println(name); }

компилируется в:

for (Iterator<String> it = names.iterator(); it.hasNext(); ) {
  String name = it.next();
  System.out.println(name);
}

Как только вы увидите это раскрытие синтаксиса, остальные правила Iterator становятся понятными.

Три метода и их исключения

hasNext() возвращает true, если вызов next() завершится успешно. Идемпотентен — вызывать его дважды подряд безопасно. Никогда не выбрасывает исключений (в корректных реализациях).

next() перемещает курсор и возвращает элемент. Выбрасывает NoSuchElementException, если следующего элемента нет. Это единственный метод итератора, который по замыслу выбрасывает исключение при неправильном использовании. Всегда защищайте вызов с помощью hasNext(), если коллекция может оказаться пустой:

while (it.hasNext()) { use(it.next()); }     // safe pattern

remove() удаляет элемент, последний раз возвращённый методом next(). Это default-метод, который выбрасывает UnsupportedOperationException, если итератор его не реализует. ArrayList, HashMap.keySet().iterator() и им подобные поддерживают его. Итераторы, возвращаемые из List.of(...), Collections.unmodifiableList(...) и .iterator() потока, — нет. Также нельзя вызывать remove() дважды подряд без промежуточного вызова next() — это выбрасывает IllegalStateException.

Iterator<String> it = names.iterator();
while (it.hasNext()) {
  String name = it.next();
  if (name.isEmpty()) it.remove();           // legal, fail-safe removal
}

it.remove() — это единственный безопасный способ удалять элементы из коллекции при итерации с помощью обычного Iterator. Собственный метод remove(...) коллекции сделал бы итератор недействительным и выбросил бы ConcurrentModificationException при следующем вызове.

Fail-fast итерация

Большинство итераторов коллекций JDK являются fail-fast: они запоминают счётчик модификаций коллекции при создании итератора, проверяют его при каждом вызове hasNext/next и выбрасывают ConcurrentModificationException, если он изменился кем-либо, кроме самого итератора.

List<String> names = new ArrayList<>(List.of("a", "b", "c"));
Iterator<String> it = names.iterator();
names.add("d");                              // direct mutation, not via iterator
it.next();                                   // throws ConcurrentModificationException

Fail-fast — это диагностика по возможности, а не гарантия потокобезопасности. Он чисто и рано выявляет распространённую ошибку («ах, я изменил список внутри цикла, и теперь мой итератор сломался»). Он не защищает от параллельных изменений из другого потока — для этого нужна конкурентная коллекция (CopyOnWriteArrayList, ConcurrentHashMap), итераторы которых слабо согласованы: они проходят по снимку и никогда не выбрасывают исключений.

forEachRemaining и forEach

Два default-метода делают итерацию короче, когда курсор не нужен:

list.forEach(System.out::println);                       // every element

Iterator<String> it = list.iterator();
while (it.hasNext() && !it.next().equals("STOP")) { }
it.forEachRemaining(System.out::println);                // everything past STOP

forEach принадлежит Iterable; forEachRemaining — Iterator. Оба выполняются последовательно. Не используйте их, если вам также нужно вызывать remove — они скрывают курсор, а remove требует его.

Написание собственного Iterator

Вы напишете его, когда реализуете собственный тип, похожий на коллекцию. Контракт невелик, но каждая его часть важна:

class Countdown implements Iterable<Integer> {
  private final int from;
  Countdown(int from) { this.from = from; }

  @Override public Iterator<Integer> iterator() {
    return new Iterator<>() {
      int n = from;
      @Override public boolean hasNext() { return n > 0; }
      @Override public Integer next() {
        if (n <= 0) throw new NoSuchElementException();
        return n--;
      }
    };
  }
}

for (int x : new Countdown(3)) System.out.println(x);   // 3 2 1

Три вещи, которые нужно сделать правильно:

1. next() должен выбрасывать NoSuchElementException при исчерпании. Не возвращайте null или какой-либо sentinel-значение.
2. Итератор должен быть новым экземпляром при каждом вызове iterator(). Двойной вызов for (... : it) на одном и том же iterable должен каждый раз начинать с начала.
3. remove() — опциональный. Не реализуйте его, если вы реально не можете — default-тело, выбрасывающее исключение, вполне подходит.

Рабочий пример: итерация, удаление, fail-fast, пользовательский iterable

Приведённая ниже программа обходит ArrayList тремя способами (for-each, явный итератор, forEachRemaining), безопасно удаляет элементы с помощью Iterator.remove, демонстрирует исключение fail-fast при обходе итератора стороной, и завершается небольшим пользовательским Iterable<T>.

Что следует вынести из запуска:

• Цикл for-each вывел каждый элемент; за кулисами он запросил у ArrayList итератор и обошёл его с помощью hasNext/next.
• Iterator.remove удалил пустые строки во время итерации без ConcurrentModificationException. Это единственная корректная техника удаления внутри цикла при использовании обычного Iterator.
• forEachRemaining — аккуратный способ вычерпать всё, что итератор ещё не выдал, — удобно сразу после частичного обхода.
• Прямое изменение списка при живом другом итераторе выбросило ConcurrentModificationException при следующем вызове next(). Исключение намеренное: оно делает ошибку очевидной.
• Пользовательский Countdown показывает минимальный контракт, необходимый для написания рабочего iterable. hasNext корректно сообщает о состоянии; next выбрасывает исключение при исчерпании; remove не реализован (наследует default-вариант).

Что дальше

Обычный Iterator может двигаться вперёд и удалять элементы. Этого достаточно для множеств, карт и очередей — у них нет позиций в каком-либо ином смысле. У списков они есть, и им достаётся более богатый курсор: ListIterator<E> может двигаться вперёд и назад, сообщать индексы, а также add или set элементы во время обхода. Это следующая глава.

Практика