Паттерн Iterator

Сегодня поговорим о том, что такое Iterator в Java и зачем он нужен.

Кратко

• Итератор это объект, который перебирает элементы коллекции по одному и не заставляет знать, как коллекция устроена внутри.
• Работает он на двух методах: hasNext() спрашивает, остались ли еще элементы, next() отдает следующий.
• Если вызвать next() на исчерпанном итераторе, прилетит NoSuchElementException.
• Collection расширяет Iterable, а не Iterator. Именно на Iterable держится цикл for-each.
• У Map своего итератора нет, его берут у map.entrySet(), и тогда next() отдает пару ключ-значение.
• Интерфейс и паттерн это разные вещи: реализуя интерфейс, ты реализуешь паттерн, но паттерн можно реализовать и без него, со своими именами методов.

Итератор (Iterator) в Java это объект, который позволяет последовательно перебирать элементы коллекции, не раскрывая ее внутреннюю структуру. Используя методы hasNext() для проверки наличия следующего элемента и next() для его получения, итератор обеспечивает унифицированный способ обхода List, Set и Map. Iterator в Java это сразу две вещи, и их легко перепутать: готовый интерфейс java.util.Iterator из стандартной библиотеки и одноименный паттерн проектирования, который можно реализовать для любой своей структуры данных. Про обе и поговорим. Как ты уже, вероятно, знаешь, в Java есть замечательный интерфейс Collection, и он расширяет интерфейс Iterable (именно Iterable, а не Iterator: первый умеет отдавать итератор, второй сам им является). Сразу оговорюсь, не следует путать интерфейс iterator с паттерном iterator в Java!

Знакомство с интерфейсом Iterator

И дабы внести ясность, для начала разберемся именно с интерфейсом.Представим на секунду, что iterator в Java отсутствует. В таком случае всем и каждому придется нырнуть в самые глубины коллекций и по-настоящему разобраться, чем отличается ArrayList от LinkedList и HashSet от TreeSet.

Методы интерфейса Iterator

Методов в интерфейсе четыре, но обязательных из них только два. hasNext() и next() абстрактные, их придется написать самому. А remove() и forEachRemaining() с Java 8 объявлены как default-методы, то есть реализация по умолчанию у них уже есть. boolean hasNext(): если в итерируемом объекте (пока что это Collection) остались еще значения, метод вернет true, если значения кончились, вернет false. E next(): возвращает следующий элемент коллекции (объекта). Если элементов больше нет (не было проверки hasNext(), а мы вызвали next(), достигнув конца коллекции), метод бросит NoSuchElementException. void remove(): удалит элемент, который был в последний раз получен методом next(). Метод может бросить:

• UnsupportedOperationException, если данный итератор не поддерживает метод remove() (в случае с read-only коллекциями, например)
• IllegalStateException, если метод next() еще не был вызван, или если remove() уже был вызван после последнего вызова next().

Про remove() есть важная оговорка: с Java 8 это default-метод, и реализовывать его никто не обязан. В документации так и написано: «The default implementation throws an instance of UnsupportedOperationException and performs no other action». То есть если автор итератора про этот метод просто забыл, вызов упадет с тем самым UnsupportedOperationException. void forEachRemaining(Consumer<? super E> action): четвертый метод интерфейса, тоже default и тоже из Java 8. Он прогоняет действие по всем оставшимся элементам разом, так что цикл while можно свернуть в одну строку:

Iterator<String> iterator = list.iterator();
iterator.forEachRemaining(System.out::println);

Никакой магии внутри нет: реализация по умолчанию описана в документации как while (hasNext()) action.accept(next());, просто написанный за тебя.

Использование итераторов с коллекциями

Итак, iterator для List это самая распространенная имплементация. Итератор идет от начала коллекции к ее концу: смотрит есть ли в наличии следующий элемент и возвращает его, если таковой находится. На основе этого несложного алгоритма построен цикл for-each. Его расширение это ListIterator. Рассмотрим дополнительные методы java list iterator. Ты их, скорее всего, знаешь:

• void add(E e) вставляет элемент E в List<E>;
• boolean hasPrevious() вернет true, если при обратном переборе List имеются элементы;
• int nextIndex() вернет индекс следующего элемента;
• E previous() вернет предыдущий элемент листа;
• int previousIndex() вернет индекс предыдущего элемента;
• void set(E e) заменит элемент, возвращенный последним вызовом next() или previous() на элемент e.

Итератор для List

Рассмотрим небольшой пример. Создадим List, содержащий в себе строки приветствия обучающихся:

List<String> list = new ArrayList<>();
list.add("Привет");
list.add("Обучающимся");
list.add("На");
list.add("JavaRush");

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

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

Итератор для Map

Сейчас будет «узкое место»: Java Collections как ты, вероятно, знаешь (а если не знаешь, разберись), расширяют интерфейс Iterable, но это не означает, что только List, Set и Queue поддерживают итератор. Для Map java iterator также поддерживается, но получать его нужно у Map.entrySet():

Map<String, Integer> map = new HashMap<>();
Iterator<Map.Entry<String, Integer>> mapIterator = map.entrySet().iterator();

Тогда метод next() будет возвращать объект Entry, содержащий в себе пару «ключ»-«значение». Дальше все аналогично с List:

while (mapIterator.hasNext()) {
    Map.Entry<String, Integer> entry = mapIterator.next();
    System.out.println("Key: " + entry.getKey());
    System.out.println("Value: " + entry.getValue());
}

Зачем итератору remove: ConcurrentModificationException

Тут стоит остановиться и ответить на вопрос, который возникает у всех: зачем итератору свой remove(), если у коллекции уже есть собственный? Затем, что удалять из коллекции во время ее обхода нельзя. Вот такой безобидный на вид код упадет:

List<String> list = new ArrayList<>(List.of("Привет", "Обучающимся", "На", "JavaRush"));

for (String s : list) {
    if (s.equals("Обучающимся")) {
        list.remove(s);
    }
}

Вывод в консоль:

Exception in thread "main" java.util.ConcurrentModificationException

Коллекция считает, сколько раз ее структурно меняли, а итератор запоминает это число в момент своего создания. Как только числа разошлись, следующий вызов next() бросает ConcurrentModificationException. Цикл for-each тут ни при чем: под капотом он работает через тот же итератор, и проверка срабатывает именно в нем. Документация ArrayList называет такое поведение fail-fast и оговаривает исключение из правила: итератор бросает ошибку при любой структурной правке списка, «in any way except through the iterator's own remove or add methods». Коварство тут в том, что падает не всегда. Удали в том же примере предпоследний элемент, и обход просто молча закончится раньше времени: hasNext() увидит, что курсор уже равен новому размеру списка, и до проверки дело не дойдет. Ошибка никуда не денется, просто проявится тише и найти ее будет сложнее. А вот через итератор удалять можно, потому что он о своем удалении знает и счетчик обновляет сам:

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    if (iterator.next().equals("Обучающимся")) {
        iterator.remove();
    }
}

Вот ради этого remove() у итератора и существует. Подробнее про разные стратегии поведения при изменении коллекции есть отдельная статья, Сказ о двух итераторах.

Интерфейс vs. Паттерн: в чем разница?

Ты думаешь: «Стоп. Мы говорим про интерфейс, а в заголовке статьи написано «Паттерн». То есть паттерн iterator это интерфейс Iterator? Или интерфейс это паттерн?» Если это слово встречается впервые, даю справку: паттерн это шаблон проектирования, некое поведение, которого должен придерживаться класс или множество взаимосвязанных классов. Итератор в java может быть реализован для любого объекта, внутренняя структура которого подразумевает перебор, при этом можно изменить сигнатуру обсуждаемых методов. Главное при реализации паттерна это логика, которой должен придерживаться класс. Интерфейс итератор это частная реализация одноименного паттерна, применяемая как к готовым структурам (List, Set, Queue, Map), так и к прочим, на усмотрение программиста. Расширяя интерфейс Iterator, ты реализуешь паттерн, но для реализации паттерна не обязательно расширять интерфейс. Простая аналогия: все рыбы плавают, но не все, что плавает, рыбы. Если совсем коротко, разница такая:

Создание собственного итератора

В качестве примера я решил взять… слово. А конкретнее, существительное. Оно состоит из частей: приставки, корня, суффикса и окончания. Для частей слова создадим интерфейс WordPart и классы, расширяющие его: Prefix, Root, Suffix и Ending:

interface WordPart {
    String getWordPart();
}

static class Root implements WordPart {

    private String part;

    public Root(String part) {
        this.part = part;
    }

    @Override
    public String getWordPart() {
        return part;
    }
}

static class Prefix implements WordPart {

    private String part;

    public Prefix(String part) {
        this.part = part;
    }

    @Override
    public String getWordPart() {
        return part;
    }
}

static class Suffix implements WordPart {

    private String part;

    public Suffix(String part) {
        this.part = part;
    }

    @Override
    public String getWordPart() {
        return part;
    }
}

static class Ending implements WordPart {

    private String part;

    public Ending(String part) {
        this.part = part;
    }

    @Override
    public String getWordPart() {
        return part;
    }
}

Класс Word: что перебираем

Тогда класс Word (слово) будет содержать в себе части, а кроме них добавим целое число, отражающее количество частей в слове:

public class Word {

    private Root root;
    private Prefix prefix;
    private Suffix suffix;
    private Ending ending;
    private int partCount;

    public Word(Root root, Prefix prefix, Suffix suffix, Ending ending) {
        this.root = root;
        this.prefix = prefix;
        this.suffix = suffix;
        this.ending = ending;
        this.partCount = 4;
    }

    public Word(Root root, Prefix prefix, Suffix suffix) {
        this.root = root;
        this.prefix = prefix;
        this.suffix = suffix;
        this.partCount = 3;

    }

    public Word(Root root, Prefix prefix) {
        this.root = root;
        this.prefix = prefix;
        this.partCount = 2;
    }

    public Word(Root root) {
        this.root = root;
        this.partCount = 1;
    }

    public Root getRoot() {
        return root;
    }

    public Prefix getPrefix() {
        return prefix;
    }

    public Suffix getSuffix() {
        return suffix;
    }

    public Ending getEnding() {
        return ending;
    }

    public int getPartCount() {
        return partCount;
    }

    public boolean hasRoot() {
        return this.root != null;
    }

    public boolean hasPrefix() {
        return this.prefix != null;
    }

    public boolean hasSuffix() {
        return this.suffix != null;
    }

    public boolean hasEnding() {
        return this.ending != null;
    }
}

Окей, у нас есть четыре перегруженных конструктора (для простоты, предположим, что суффикс у нас может быть только один). Существительное не может состоять из одной приставки, поэтому для конструктора с одним параметром будем устанавливать корень.

WordIterator: сам итератор

Теперь напишем реализацию паттерна итератор: WordIterator, переопределяющий 2 метода: hasNext() и next():

import java.util.Iterator;
import java.util.NoSuchElementException;

public class WordIterator implements Iterator<Word.WordPart> {

    private final Word word;
    private int currentPartIndex;

    public WordIterator(Word word) {
        this.word = word;
        this.currentPartIndex = 0;
    }

    @Override
    public boolean hasNext() {
        return currentPartIndex < word.getPartCount();
    }

    @Override
    public Word.WordPart next() {
        if (!hasNext()) {
            throw new NoSuchElementException("Больше нет частей в этом слове!");
        }
        
        // Задаем обратный порядок, как в оригинальной статье: окончание -> суффикс -> приставка -> корень
        int partToReturnIndex = word.getPartCount() - 1 - currentPartIndex;
        currentPartIndex++;

        switch (partToReturnIndex) {
            case 3:
                return word.getEnding();
            case 2:
                return word.getSuffix();
            case 1:
                return word.getPrefix();
            case 0:
                return word.getRoot();
            default:
                 // Эта логика зависит от того, как устроен класс Word и его конструкторы
                 // Для простоты будем отталкиваться от корня при меньшем кол-ве частей
                 if (word.hasRoot()) return word.getRoot();
                 if (word.hasPrefix()) return word.getPrefix();
                 if (word.hasSuffix()) return word.getSuffix();
                 return word.getEnding();
        }
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("Удаление частей слова не поддерживается!");
    }
}

Осталось назначить итератор классу Word:

public class Word implements Iterable<Word.WordPart> {
	//…
	@Override
	public Iterator<WordPart> iterator() {
    		return new WordIterator(this);
	}
	//…
}

Проверяем на слове «перебежка»

Теперь проведем морфемный разбор слова «перебежка»:

public class Main {
    public static void main(String[] args) {
        Word.Root root = new Word.Root("беж");
        Word.Prefix prefix = new Word.Prefix("пере");
        Word.Suffix suffix = new Word.Suffix("к");
        Word.Ending ending = new Word.Ending("a");
        Word word = new Word(root, prefix, suffix, ending);

        Iterator<Word.WordPart> wordIterator = word.iterator();
        while (wordIterator.hasNext()) {
            Word.WordPart part = wordIterator.next();
            System.out.println(part.getClass().getSimpleName() + ": " + part.getWordPart());
        }
    }
}

Обрати внимание, в своей реализации паттерна iterator я выбрал следующий порядок вывода:

1. окончание
2. суффикс
3. приставка
4. корень

При проектировании собственного итератора ты сам можешь задать алгоритм итерации, как захочешь. Успехов в обучении!

Вопросы и ответы

Что такое итератор в Java?

Объект, который перебирает элементы коллекции по одному и скрывает от вызывающего кода ее внутреннее устройство. У него всего два обязательных метода: hasNext() отвечает, остались ли еще элементы, а next() отдает следующий. Благодаря этому один и тот же код обхода работает и для списка, и для множества, и для очереди, хотя внутри они устроены совершенно по-разному.

Чем интерфейс Iterator отличается от паттерна Iterator?

Интерфейс это конкретный тип из стандартной библиотеки со строго заданными именами методов. Паттерн это идея: объект, который умеет выдавать элементы по одному, как бы его методы ни назывались. Реализуя интерфейс, ты автоматически реализуешь и паттерн. Наоборот это не работает: паттерн можно воплотить в своем классе, не трогая java.util.Iterator вообще.

Как получить итератор для Map?

Напрямую никак: Map не расширяет Iterable и метода iterator() у нее нет. Итератор берут у одного из представлений карты, чаще всего у map.entrySet(). Тогда next() возвращает объект Map.Entry с парой ключ-значение, из которого достают getKey() и getValue(). Если нужны только ключи или только значения, есть map.keySet() и map.values().

Почему next() бросает NoSuchElementException?

Потому что элементы закончились, а его все равно вызвали. Метод next() не обязан проверять границы за программиста, эта проверка возложена на hasNext(). Отсюда и канонический вид обхода: сначала while с hasNext(), и только внутри цикла next().

Чем ListIterator отличается от обычного итератора?

Он умеет больше и работает только со списками. Обычный итератор идет строго вперед, а ListIterator ходит и назад через hasPrevious() и previous(), знает индексы элементов через nextIndex() и previousIndex(), а еще умеет менять список прямо во время обхода методами set() и add().

Как написать собственный итератор?

Нужны два класса. Первый реализует Iterator и хранит позицию обхода: в hasNext() он отвечает, есть ли что отдавать дальше, в next() отдает очередной элемент и сдвигает позицию. Второй, тот, который перебирают, реализует Iterable и в методе iterator() возвращает новый экземпляр первого. После этого объект можно обходить обычным циклом for-each.

Читайте также

• Коллекции в Java: Java Collections Framework
• Foreach в Java
• Сказ о двух итераторах: стратегии конкурентной модификации в Java
• Singleton: паттерны проектирования