Итератор (Iterator)

Итератор выдаёт элементы, не раскрывая устройство структуры. Алгоритм обхода и позиция хранятся в отдельном объекте.

Сигналы применения

• клиентам нужен обход, но им нельзя отдавать внутренний массив, дерево или граф;
• для одной структуры требуется несколько способов обхода;
• обход должен быть ленивым;
• несколько клиентов должны перемещаться по одной коллекции независимо.

В Java основной контракт — Iterator<T>, а источник итераторов — Iterable<T>.

Роли и протокол

• Aggregate предоставляет новый Iterator;
• Iterator отвечает на hasNext() и next();
• Concrete Iterator хранит очередь, стек, индекс или другой курсор;
• Client потребляет элементы, не управляя внутренней структурой.

После исчерпания next() бросает NoSuchElementException: null может быть элементом.

Пример: обход графа в ширину

final class IntGraph implements Iterable<Integer> {
    private final Map<Integer, List<Integer>> edges;
    private final int start;
    IntGraph(Map<Integer, List<Integer>> edges, int start) {
        this.edges = edges; this.start = start;
    }
    @Override public Iterator<Integer> iterator() {
        return new BfsIterator(edges, start); }
}
final class BfsIterator implements Iterator<Integer> {
    private final Map<Integer, List<Integer>> edges;
    private final Queue<Integer> queue = new ArrayDeque<>();
    private final Set<Integer> visited = new HashSet<>();
    BfsIterator(Map<Integer, List<Integer>> edges, int start) {
        this.edges = edges; queue.add(start); visited.add(start);
    }
    public boolean hasNext() { return !queue.isEmpty(); }
    public Integer next() {
        if (!hasNext()) throw new NoSuchElementException();
        int current = queue.remove();
        for (int neighbor : edges.getOrDefault(current, List.of())) {
            if (visited.add(neighbor)) queue.add(neighbor);
        }
        return current;
    }
}

Каждый iterator() создаёт свои queue и visited, а циклы не зацикливают обход.

Изменение коллекции во время обхода

Итераторы стандартных изменяемых коллекций часто fail-fast: при структурном изменении не через итератор они могут выбросить ConcurrentModificationException. Это диагностика, а не гарантия потокобезопасности.

Для снимка итерируются по копии. Конкурентный обход может быть weakly-consistent без гарантии единого снимка.

Компромиссы

• скрывается устройство коллекции;
• ленивый обход экономит память;
• состояние обхода требует отдельного объекта;
• сложный Iterator труднее отлаживать, чем готовый список;
• бесконечный итератор требует ограничивающей операции со стороны клиента.

Чем отличается

• Stream — вычислительный конвейер, Iterator — протокол следующего элемента;
• Цепочка обязанностей Chain of Responsibility передаёт запрос, Iterator обходит;
• Composite часто предоставляет Iterator для обхода своего дерева.

Вопросы на собеседовании

1. Почему контракты разделены? Источник создаёт независимые курсоры.
2. Что делает for-each? Получает iterator() и вызывает hasNext()/next().
3. Обязателен ли remove()? Нет; по умолчанию он не поддерживается.
4. Fail-fast означает потокобезопасность? Нет.
5. Как обойти большой набор? Лениво; внешний ресурс при этом нужно закрывать. Связи: Поведенческие паттерны, Iterable, Коллекции.