Итератор (шаблон проектирования)


Iterator — поведенческий шаблон проектирования. Представляет собой объект, позволяющий получить последовательный доступ к элементам объекта-агрегата без использования описаний каждого из агрегированных объектов.

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

Перебор элементов выполняется объектом итератора, а не самой коллекцией. Это упрощает интерфейс и реализацию коллекции, а также способствует более логичному разделению обязанностей.

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

Конечно же, (в С++) почти в любом агрегате можно выполнять итерации указателем void*, но при этом:

  • не ясно, что является значением «конец агрегата», для двусвязного списка это &ListHead, для массива это &array[size], для односвязного списка это NULL
  • операция Next сильно зависит от типа агрегата.

Итераторы позволяют абстрагироваться от типа и признака окончания агрегата, используя полиморфный Next (часто реализованный как operator++ в С++) и полиморфный aggregate.end(), возвращающий значение «конец агрегата».

Таким образом, появляется возможность работы с диапазонами итераторов, при отсутствии знания о типе итерируемого агрегата. Например:

Iterator itBegin = aggregate.begin(); Iterator itEnd = aggregate.end(); func(itBegin, itEnd);

И далее:

void func(Iterator itBegin, Iterator itEnd) { for( Iterator it = itBegin, it != itEnd; ++it ) { } }

Примеры

С#

Исходный текст на языке С# /* sample code in C# This structural code demonstrates the Iterator pattern which provides for a way to traverse (iterate) over a collection of items without detailing the underlying structure of the collection. */ Hide code // Iterator pattern -- Structural example using System; using System.Collections; namespace DoFactory.GangOfFour.Iterator.Structural { /// <summary> /// MainApp startup class for Structural /// Iterator Design Pattern. /// </summary> class MainApp { /// <summary> /// Entry point into console application. /// </summary> static void Main() { ConcreteAggregate a = new ConcreteAggregate(); a[0] = "Item A"; a[1] = "Item B"; a[2] = "Item C"; a[3] = "Item D"; // Create Iterator and provide aggregate ConcreteIterator i = new ConcreteIterator(a); Console.WriteLine("Iterating over collection:"); object item = i.First(); while (! i.IsDone()) { Console.WriteLine(item); item = i.Next(); } // Wait for user Console.ReadKey(); } } /// <summary> /// The 'Aggregate' abstract class /// </summary> abstract class Aggregate { public abstract Iterator CreateIterator(); public abstract int Count { get; protected set; } public abstract object this[int index] { get; set; } } /// <summary> /// The 'ConcreteAggregate' class /// </summary> class ConcreteAggregate : Aggregate { private readonly ArrayList _items = new ArrayList(); public override Iterator CreateIterator() { return new ConcreteIterator(this); } // Gets item count public override int Count { get { return _items.Count; } protected set { } } // Indexer public override object this[int index] { get { return _items[index]; } set { _items.Insert(index, value); } } } /// <summary> /// The 'Iterator' abstract class /// </summary> abstract class Iterator { public abstract object First(); public abstract object Next(); public abstract bool IsDone(); public abstract object CurrentItem(); } /// <summary> /// The 'ConcreteIterator' class /// </summary> class ConcreteIterator : Iterator { private readonly Aggregate _aggregate; private int _current; // Constructor public ConcreteIterator(Aggregate aggregate) { this._aggregate = aggregate; } // Gets first iteration item public override object First() { return _aggregate[0]; } // Gets next iteration item public override object Next() { object ret = null; _current++; if (_current < _aggregate.Count) { ret = _aggregate[_current]; } return ret; } // Gets current iteration item public override object CurrentItem() { return _aggregate[_current]; } // Gets whether iterations are complete public override bool IsDone() { return _current >= _aggregate.Count; } } } Output Iterating over collection: Item A Item B Item C Item D

PHP5

Исходный текст на языке PHP5 /** * Паттерн итератор предоставляет механизм последовательного перебора элементов коллекции без раскрытия реализации коллекции. * * Перебор элементов выполняется объектом итератора, а не самой коллекцией. * Это упрощает интерфейс и реализацию коллекции, а также способствует более логичному распределению обязанностей. */ namespace iterator1 { /** * Наличие общего интерфейса удобно для клиента, поскольку клиент отделяется от реализации коллекции объектов. * * ConcreteAggregate содержит коллекцию объектов и реализует метод, который возвращает итератор для этой коллекции. */ interface IAggregate { /** * Каждая разновидность ConcreteAggregate отвечает за создание экземпляра Concrete Iterator, * который может использоваться для перебора своей коллекции объектов. */ public function createIterator(); } /** * Интерфейс Iterator должен быть реализован всеми итераторами. * * ConcreteIterator отвечает за управление текущей позицией перебора. */ interface IIterator { /** * @abstract * @return boolean есть ли следующий элемент в коллекции */ public function hasNext(); /** * @abstract * @return mixed следующий элемент массива */ public function next(); /** * Удаляет текущий элемент коллекции * @abstract * @return void */ public function remove(); } /** * В моём примере обе коллекции используют одинаковый итератор - итератор массива. */ class ConcreteAggregate1 implements IAggregate { /** * @var Item[] $items */ public $items = array(); public function __construct() { $this->items = array( new Item(1, 2), new Item(1, 2), new Item(1, 2), ); } public function createIterator() { return new ConcreteIterator1($this->items); } } class ConcreteAggregate2 implements IAggregate { /** * @var Item[] $items */ public $items = array(); public function __construct() { $this->items = array( new Item(2, 3), new Item(2, 3), new Item(2, 3), ); } public function createIterator() { return new ConcreteIterator1($this->items); } } class ConcreteIterator1 implements IIterator { /** * @var Item[] $items */ protected $items = array(); /** * @var int $position хранит текущую позицию перебора в массиве */ public $position = 0; /** * @param $items массив объектов, для перебора которых создается итератор */ public function __construct($items) { $this->items = $items; } public function hasNext() { if ($this->position >= count($this->items) || count($this->items) == 0) { return (false); } else { return (true); } } public function next() { $menuItem = $this->items[$this->position]; $this->position++; return ($menuItem); } public function remove() { if ($this->position <= 0) { throw new Exception('Нельзя вызывать remove до вызова хотя бы одного next()'); } if ($this->items[$this->position - 1] != null) { for ($i = $this->position - 1; $i < count($this->items); $i++) { $this->items[$i] = $this->items[$i + 1]; } $this->items[count($this->items) - 1] = null; } } } class Client { /** * @var ConcreteAggregate1 $aggregate1 */ public $aggregate1; /** * @var ConcreteAggregate2 $aggregate2 */ public $aggregate2; public function __construct($aggregate1, $aggregate2) { $this->aggregate1 = $aggregate1; $this->aggregate2 = $aggregate2; } public function printAggregatesItems() { $iterator1 = $this->aggregate1->createIterator(); echo " First"; $this->printIteratorItems($iterator1); $iterator2 = $this->aggregate2->createIterator(); echo " Second"; $this->printIteratorItems($iterator2); } /** * @param $iterator IIterator */ private function printIteratorItems($iterator) { while ($iterator->hasNext()) { $item = $iterator->next(); echo " $item->name $item->price $item->description"; } } } class Item { public $price; public $name; public $description; public function __construct($name, $price, $description = '') { $this->name = $name; $this->price = $price; $this->description = $description; } } $runner = new Client(new ConcreteAggregate1(), new ConcreteAggregate2()); $runner->printAggregatesItems(); }

Пример итератора компоновщика на PHP5

Исходный текст итератора компоновщика на языке PHP5 /** * Паттерн-компоновщик с внешним итератором * Итератор использует рекурсию для перебора дерева элементов */ namespace compositeIterator { /** * Клиент использует интерфейс AComponent для работы с объектами. * Интерфейс AComponent определяет интерфейс для всех компонентов: как комбинаций, так и листовых узлов. * AComponent может реализовать поведение по умолчанию для add() remove() getChild() и других операций */ abstract class AComponent { public $customPropertyName; public $customPropertyDescription; /** * @param AComponent $component */ public function add($component) { throw new Exception("Unsupported operation"); } /** * @param AComponent $component */ public function remove($component) { throw new Exception("Unsupported operation"); } /** * @param int $int */ public function getChild($int) { throw new Exception("Unsupported operation"); } /** * @return IPhpLikeIterator */ abstract function createIterator(); public function operation1() { throw new Exception("Unsupported operation"); } } /** * Leaf наследует методы add() remove() getChild( которые могут не иметь смысла для листового узла. * Хотя листовой узер можно считать узлом с нулём дочерних объектов * * Leaf определяет поведение элементов комбинации. Для этого он реализует операции, поддерживаемые интерфейсом Composite. */ class Leaf extends AComponent { public function __construct($name, $description = '') { $this->customPropertyName = $name; $this->customPropertyDescription = $description; } public function createIterator() { return new NullIterator(); } public function operation1() { echo (" I'am leaf {$this->customPropertyName}, i don't want to do operation 1. {$this->customPropertyDescription}"); } } class NullIterator implements IPhpLikeIterator { public function valid() { return (false); } public function next() { return (false); } public function current() { return (null); } public function remove() { throw new CException('unsupported operation'); } } /** * Интерфейс Composite определяет поведение компонентов, имеющих дочерние компоненты, и обеспечивает хранение последних. * * Composite также реализует операции, относящиеся к Leaf. Некоторые из них не могут не иметь смысла для комбинаций; в таких случаях генерируется исключение. */ class Composite extends AComponent { private $_iterator = null; /** * @var ArrayObject AComponent[] $components для хранения потомков типа AComponent */ public $components = null; public function __construct($name, $description = '') { $this->customPropertyName = $name; $this->customPropertyDescription = $description; } /** * @param AComponent $component */ public function add($component) { if (is_null($this->components)) { $this->components = new ArrayObject; } $this->components->append($component); } public function remove($component) { foreach ($this->components as $i => $c) { if ($c === $component) { unset($this->components[$i]); } } } public function getChild($int) { return ($this->components[$int]); } public function operation1() { echo " $this->customPropertyName $this->customPropertyDescription"; echo " --------------------------------"; $iterator = $this->components->getIterator(); while ($iterator->valid()) { $component = $iterator->current(); $component->operation1(); $iterator->next(); } } /** * @return CompositeIterator */ public function createIterator() { if (is_null($this->_iterator)) { $this->_iterator = new CompositeIterator($this->components->getIterator()); } return ($this->_iterator); } } /** * Рекурсивный итератор компоновщика */ class CompositeIterator implements IPhpLikeIterator { public $stack = array(); /** * @param ArrayIterator $componentsIterator */ public function __construct($componentsIterator) { //$this->stack= new ArrayObject; $this->stack[] = $componentsIterator; } public function remove() { throw new CException('unsupported operation'); } public function valid() { if (empty($this->stack)) { return (false); } else { /** @var $componentsIterator ArrayIterator */ // берём первый элемент $componentsIterator = array_shift(array_values($this->stack)); if ($componentsIterator->valid()) { return (true); } else { array_shift($this->stack); return ($this->valid()); } } } public function next() { /** @var $componentsIterator ArrayIterator */ $componentsIterator = current($this->stack); $component = $componentsIterator->current(); if ($component instanceof Composite) { array_push($this->stack, $component->createIterator()); } $componentsIterator->next(); //return($component); } public function current() { if ($this->valid()) { /** @var $componentsIterator ArrayIterator */ // берём первый элемент $componentsIterator = array_shift(array_values($this->stack)); return ($componentsIterator->current()); } else { return (null); } } } /** * Интерфейс Iterator должен быть реализован всеми итераторами. * Данный интерфейс является частью интерфейса стандартного php итератора. * Конкретный Iterator отвечает за управление текущей позицией перебора в конкретной коллекции. */ interface IPhpLikeIterator { /** * @abstract * @return boolean есть ли текущий элемент */ public function valid(); /** * @abstract * @return mixed перевести курсор дальше */ public function next(); /** * @abstract * @return mixed получить текущий элемент */ public function current(); /** * удалить текущий элемент коллекции * @abstract * @return void */ public function remove(); } class Client { /** * @var AComponent */ public $topItem; public function __construct($topItem) { $this->topItem = $topItem; } public function printOperation1() { $this->topItem->operation1(); } public function printOperation2() { echo " "; $iterator = $this->topItem->createIterator(); while ($iterator->valid()) { /** @var $component AComponent */ $component = $iterator->current(); if (strstr($component->customPropertyName, 'leaf1')) { echo (" I'm Client, I found leaf {$component->customPropertyName}, I'll just leave it here (for my 'first-leafs' tea collection). {$component->customPropertyDescription}"); } $iterator->next(); } } } class Test { public static function go() { $a = new Composite("c1"); $b = new Composite("c2"); $c = new Composite("c3"); $topItem = new Composite("top item"); $topItem->add($a); $topItem->add($b); $topItem->add($c); $a->add(new Leaf("c1-leaf1")); $a->add(new Leaf("c1-leaf2")); $b->add(new Leaf("c2-leaf1")); $b->add(new Leaf("c2-leaf2")); $b->add(new Leaf("c2-leaf3")); $c->add(new Leaf("c3-leaf1")); $c->add(new Leaf("c3-leaf2")); $client = new Client($topItem); $client->printOperation1(); $client->printOperation2(); } } Test::go(); }

Python

Исходный текст на языке Python from abc import ABCMeta, abstractmethod class Iterator(metaclass=ABCMeta): """ Абстрактный итератор """ _error = None # класс ошибки, которая прокидывается в случае выхода за границы коллекции def __init__(self, collection, cursor): """ Constructor. :param collection: коллекция, по которой производится проход итератором :param cursor: изначальное положение курсора в коллекции (ключ) """ self._collection = collection self._cursor = cursor @abstractmethod def current(self): """ Вернуть текущий элемент, на который указывает итератор """ pass @abstractmethod def next(self): """ Сдвинуть курсор на следующий элемент коллекции и вернуть его """ pass @abstractmethod def has_next(self): """ Проверить, существует ли следующий элемент коллекции """ pass @abstractmethod def remove(self): """ Удалить текущий элемент коллекции, на который указывает курсор """ pass def _raise_key_exception(self): """ Прокинуть ошибку, связанную с невалидным индексом, содержащимся в курсоре """ raise self._error('Collection of class {} does not have key "{}"'.format( self.__class__.__name__, self._cursor)) class ListIterator(Iterator): """ Итератор, проходящий по обычному списку """ _error = IndexError def __init__(self, collection: list): super().__init__(collection, 0) def current(self): if self._cursor < len(self._collection): return self._collection[self._cursor] self._raise_key_exception() def next(self): if len(self._collection) >= self._cursor + 1: self._cursor += 1 return self._collection[self._cursor] self._raise_key_exception() def has_next(self): return len(self._collection) >= self._cursor + 1 def remove(self): if 0 <= self._cursor < len(self._collection): self._collection.remove(self._collection[self._cursor]) else: self._raise_key_exception() class DictIterator(Iterator): """ Итератор, проходящий по словарю - из-за того, что словари в Python'е реализованы, как хеш-таблицы, порядок обхода может меняться во время разных запусков """ _error = KeyError def __init__(self, collection: dict): super().__init__(collection, next(iter(collection))) self._keys = list(self._collection.keys()) self._keys.pop(0) def current(self): if self._cursor in self._collection: return self._collection[self._cursor] self._raise_key_exception() def next(self): if len(self._keys): self._cursor = self._keys.pop(0) return self._collection[self._cursor] else: self._raise_key_exception() def has_next(self): return len(self._keys) > 0 def remove(self): if self._cursor in self._collection: del self._collection[self._cursor] try: self.next() except self._error: raise KeyError('Collection of type {} is empty'.format(self.__class__.__name__)) else: self._raise_key_exception() class Collection(metaclass=ABCMeta): """ Абстрактная коллекция """ @abstractmethod def iterator(self): pass class ListCollection(Collection): """ Коллекция-обертка для обычного списка """ def __init__(self, collection: list): self._collection = collection def iterator(self): return ListIterator(self._collection) class DictCollection(Collection): """ Коллекция-обертка для словаря """ def __init__(self, collection: dict): self._collection = collection def iterator(self): return DictIterator(self._collection) def test(title=str, collection=Collection): print(" {} ".format(title)) iterator = collection.iterator() print(iterator.current()) iterator.next() print(iterator.next()) iterator.remove() print(iterator.current()) print(iterator.has_next()) print() if __name__ == '__main__': print('OUTPUT:') test('List testing', ListCollection([1, 2, 3, 4, 5])) test('Dictionary testing', DictCollection({'a': 1, 'b': 2, 'c': 3, 'f': 8})) ''' OUTPUT: List testing 1 3 4 True Dictionary testing 1 3 2 False '''

Rust

Пример для языка Rust #[derive(Debug, Clone, Copy)] pub struct ExampleRange { begin : i64, current : i64, end : i64, } impl ExampleRange { pub fn new(begin : i64, end : i64) -> Self { ExampleRange { begin, current : begin, end, } } pub fn iter(&self) -> ExampleRange { *self } } use std::fmt; impl fmt::Display for ExampleRange { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { write!(f, "{}", self.current) } } impl Iterator for ExampleRange { type Item = i64; fn next(&mut self) -> Option<Self::Item> { if self.current < self.end { (Some(self.current), self.current += 1).0 } else { None } } fn last(mut self) -> Option<Self::Item> { if self.current > self.begin { (self.current -= 1, Some(self.current)).1 } else { None } } } fn main() { let it = ExampleRange::new(0, 6); for item in it { println!("{}", item); } } ''' OUTPUT: 0 1 2 3 4 5 '''

Имя:*
E-Mail:
Комментарий:
Информационный некоммерческий ресурс fccland.ru ©
При цитировании информации ссылка на сайт обязательна.
Копирование материалов сайта ЗАПРЕЩЕНО!