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

Итератор
Итератор
	Iterator
Тип	поведенческий
Описан в Design Patterns	Да

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

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

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

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

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

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

Итераторы позволяют абстрагироваться от типа и признака окончания агрегата, используя полиморфный Next (часто реализованный как operator++ в C++) и полиморфный 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 "\n First";             $this->printIteratorItems($iterator1);              $iterator2 = $this->aggregate2->createIterator();             echo "\n\n Second";             $this->printIteratorItems($iterator2);         }          /**          * @param $iterator IIterator          */         private function printIteratorItems($iterator)         {             while ($iterator->hasNext()) {                 $item = $iterator->next();                 echo "\n $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 ("\n 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 "\n\n $this->customPropertyName $this->customPropertyDescription";             echo "\n --------------------------------";              $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 "\n\n\n";             $iterator = $this->topItem->createIterator();             while ($iterator->valid()) {                 /** @var $component AComponent */                 $component = $iterator->current();                 if (strstr($component->customPropertyName, 'leaf1')) {                     echo ("\n 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("\n{}\n".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 '''

Шаблоны проектирования
Основные	Делегирования (Delegation) Интерфейс (Interface) Неизменяемый объект (Immutable) Функционального дизайна (Functional design)
Порождающие	Абстрактная фабрика (Abstract factory) Объектный пул (Object pool) Одиночка (Singleton) Отложенная инициализация (Lazy initialization) Прототип (Prototype) Строитель (Builder) Фабричный метод (Factory method)
Структурные	Адаптер (Adapter) Выделение частного класса данных (Private class data) Декоратор (Decorator) Заместитель (Proxy) Компоновщик (Composite) Мост (Bridge) Приспособленец (Flyweight) Фасад (Facade)
Поведенческие	Интерпретатор (Interpreter) Итератор (Iterator) Команда (Command) Наблюдатель (Observer) Посетитель (Visitor) Посредник (Mediator) Состояние (State) Стратегия (Strategy) Хранитель (Memento) Null Object Цепочка обязанностей (Chain of responsibility) Шаблонный метод (Template method)
Параллельного программирования	Блокировка с двойной проверкой Однопоточное выполнение Планировщик Производитель-потребитель Активный объект
Архитектурные	ActiveRecord MVC (расширение HMVC) MVP MVVM PAC Клиент — сервер Локатор служб
Шаблоны Java EE	Шаблоны_J2EE
Прочие шаблоны	Внедрение зависимости
Книги	Design Patterns
Персоналии	Кристофер Александер Эрих Гамма Джон Влиссидес Гради Буч Кент Бек Говард Каннингем Мартин Фаулер Роберт Мартин

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

Примеры[править | править код]

С#[править | править код]

PHP5[править | править код]

Пример итератора компоновщика на PHP5[править | править код]

Python[править | править код]

Rust[править | править код]

Премиум членство

€4.95

Создать Премиум Аккаунт быстро и легко

Сохраните ваши любимые страницы

Слушайте любую страницу в аудио

Цветной ночной режим