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

Шаблон проектирования

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

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

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

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

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

Конечно же, почти любой агрегат можно итерировать указателем void*, но при этом:

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

Итераторы абстрагируют именно эти 2 проблемы, используя полиморфный 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 (item != null)
            {
                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;
            if (_current < _aggregate.Count - 1)
            {
                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();
}

Использование

• интерфейсы IEnumXXX в COM. Для Next используется динамический полиморфизм.
• STL. Итераторы являются шаблонами, и для Next (точнее, operator++) используется статический полиморфизм через разворачивание шаблона. Все алгоритмы STL, работающие над множествами, работают с диапазонами итераторов, и свободны от знания о конкретном типе агрегата.

См. также

• Курсор (базы данных)