Главная » Java, Структуры данных и алгоритмы » Итераторы абстрактное представление процесса просмотра коллекций элементов по порядку

0

Типичные вычисления, производимые над вектором, списком или последовательностью, связаны с просмотром всех элементов по порядку, например, для поиска определенного элемента.

Итератором является абстрактное представление процесса просмотра коллекций элементов по порядку. Итератор включает последовательность S, текущую позицию в S, а также способ перехода к следующей позиции S и превращение ее в текущую позицию. Таким образом, итератор расширяет понятие позиции, определенное в разделе 5.2. В действительности позицию можно рассматривать как итератор, остающийся на месте. Итератор инкапсулирует понятия «место» и «следующий» в коллекциях объектов.

АТД Objectlterator поддерживает два следующих метода:

hasNext: проверяет наличие оставшихся в итераторе элементов.

Input: нет; Output: логическое значение.

nextObject: возвращает и удаляет следующий элемент итератора.

Input: нет; Output: объект.

В описываемом АТД содержится понятие «текущего» элемента последовательности. Первый элемент в итераторе возвращается при первом обращении к методу nextObject при условии, что в нем содержится хотя бы один элемент.

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

описаны в Java в интерфейсе java.util.Iterator. В интерфейсе используется укороченное имя next вместо nextObject и поддерживается дополнительный метод удаления ранее возвращенного элемента коллекции. Такая возможность удаления элемента с помощью итератора является спорной с точки зрения объектно-ориентированного программирования, в силу чего его реализация в классах не является обязательной. В Java также существует интерфейс java.util.Enumeration, который возник ранее интерфейса итератора и использует имена hasMoreElements и nextElement.

Чтобы просмотреть содержимое контейнера АТД, состоящего из коллекции объектов, должен поддерживаться метод elements(), который возвращает итератор элементов коллекции. Такой метод описан в интерфейсе java.util.Vector. Во фрагменте кода 5.14 представлен пример использования класса java.util. Iterator, который применяется для печати элементов java.util.Vector.

public static void printVector(java. util. Vector vec) { java.util.Iterator iter = vec.iterator(); while (iter.hasNext()) {

System.out.println(iter.next());

}

}

Фрагмент кода 5.14. Пример Java-итератора, используемого для печати элементов вектора

АТД, поддерживающие понятие позиции (список и последовательность), могут использовать метод positions(), который возвращает итератор позиций в контейнере. Во избежание необходимости преобразования объектов, возвращаемых методом nextObject в позицию, опишем Java-ин- терфейс Positionlterator, расширяющий Objectlterator и поддерживающий дополнительный метод:

nextPosition: возвращает и удаляет следующую позицию в итераторе.

Input: нет; Output: объект.

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

Методы, приведенные выше, описывают ограниченный тип итератора, при котором возможен только один проход по элементам. Можно создать и более мощные итераторы, в которых перемещение возможно вперед и назад по последовательности элементов, а также повторный доступ к текущему элементу. Одним из основных приложений последовательности является реализация таких итераторов; в частности, можно реализовать итератор с помощью последовательности S и позиции сиг, которая обозначает текущий элемент.

Итератор можно рассматривать как копию своего контейнера. В силу этого не рекомендуется использовать итератор при изменении содержимого контейнера. Действительно, многие конкретные реализации интерфейса java.util. Iterator обладают тем свойством, что итератор прекращает выполнение, если модифицируется его контейнер. Безусловно, такая опасность не грозит позиционным объектам, используемым в списках для указания обновленных положений, так как позиционные объекты не перемещаются.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии