Итераторы (Iterator): отделение алгоритмов от контейнеров
Александр Степанов (Alexander Stepanov) размышлял многие годы о проблеме общих техник программирования прежде чем создал STL (вместе с Dave Musser). Он пришел к заключению, что все алгоритмы определяются через алгебраические структуры - которые мы называем контейнерами.
В процессе создания он реализовал итераторы, являющиеся центральным моментом алгоритмов использования, поскольку они отделяли алгоритмы от контейнеров специфического типа, с которыми алгоритмы могли бы работать. Это означает, что вы можете описать алгоритм, не заботясь о соблюдении определенной последовательности операций. Более того, любой код, который вы пишите с использованием итераторов, не зависит от структуры данных, которой этот код манипулирует и, таким образом, ваш код более общий, и его легче использовать повторно.
Использование итераторов также переносит ваш код в реальность функционального программирования, требованиями которого является описание того, что делает программа на каждом этапе, вместо того, как она это делает. Таким образом, вы говорите "сортировка", а не описываете сортировку. Назначением STL в C++ было обеспечение основных программных подходов для C++ (насколько удачен был этот подход, оставим без внимания).
Если вы используете контейнеры Java (а писать код без их использования достаточно сложно), значит, вы используете итераторы - в форме Enumeration в Java 1.0/1.1 или Iterator в Java 1.2. Поэтому вы уже должны быть хорошо знакомы с основами их использования. Если это не так, обратитесь к Главе 9, Хранение ваших объектов, подраздел Итераторы в книге Thinking in Java, 2-я редакция (ее можно свободно скачать по адресу www.BruceEckel.com).
Поскольку контейнеры Java 2 полностью связаны с итераторами, они становятся великолепными кандидатами на общую/фундаментальную технику программирования. Эта глава исследует эту технику, преобразуя STL алгоритмы в Java для использования с библиотечными контейнерами из Java 2.
Итераторы с проверкой типа (type-safe)
В книге Thinking in Java, 2-я редакция я показал создания контейнера с проверкой типа, который принимал только объекты определенного типа. Читатель, Linda Pazzaglia, спросила, о другом явном компоненте с проверкой типа, об итераторе, который мог бы работать с основными контейнерами из java.util, но навязать ограничение, чтобы тип объекта итерации совпадал с определенным типом.
Хотя Java и включает механизм шаблонов, итератор такого сорта был бы выгоден с точки зрения того, что он мог бы вернуть объект определенного типа, вместо шаблонного итератора, который возвращает общий Object, или требует ручной доводки для каждого типа, который вы хотите итерировать. Я выберу предыдущий подход.
Второе дизайнерское решение применяется тогда, когда тип объекта определен. Первый подход состоит в том, чтобы взять тип первого объекта, который обслуживается итератором, но это проблематично, поскольку контейнер может переупорядочить объекты в соответствии со своим внутренним механизмом упорядочения (например, как хэш-таблица) и таким образом вы можете получить различные результаты в зависимости от используемого итератора. Более безопасный подход состоит в том, чтобы потребовать от пользователя указать тип при конструировании итератора.
И наконец, как мы строим итератор? Мы не можем переписать существующие библиотечные классы Java, которые уже производят Enumeration'ы и Iterator'ы. Однако, мы можем использовать шаблон проектирования Декоратор (Decorator), и создать класс, который просто является оберткой Enumeration или Iterator, производимый контейнером, создать новый объект, который реализует поведение итератора (которое состоит, в данном случае, в выбрасывании RuntimeException, если обнаружен недопустимый тип), но с тем же самым интерфейсом, как и оригинальный Enumeration или Iterator, так что он может быть использован в том же самом месте (на самом деле вы можете сказать, что это шаблон Прокси (Proxy), но мне больше нравиться Декоратор (Decorator) по своему назначению). Ниже приведен код:
//: com:bruceeckel:util:TypedIterator.java
package com.bruceeckel.util;
import java.util.*;
public class TypedIterator implements Iterator {
private Iterator imp;
private Class type;
public TypedIterator(Iterator it, Class type) {
imp = it;
this.type = type;
}
public boolean hasNext() {
return imp.hasNext();
}
public void remove() {
imp.remove();
}
public Object next() {
Object obj = imp.next();
if (!type.isInstance(obj))
throw new ClassCastException("TypedIterator for type " + type
+ " encountered type: " + obj.getClass());
return obj;
}
} // /:~| ← | Состояние (State): изменение поведения объектов | Упражнения | → |