Паттерн Iterator (итератор, cursor, курсор)

Назначение паттерна Iterator

Предоставляет способ последовательного доступа ко всем элементам составного объекта, не раскрывая его внутреннего представления.
Абстракция в стандартных библиотеках C++ и Java, позволяющая разделить классы коллекций и алгоритмов.
Придает обходу коллекции "объектно-ориентированный статус".
Полиморфный обход.

Решаемая проблема

Вам необходим механизм "абстрактного" обхода различных структур данных так, что могут определяться алгоритмы, способные взаимодействовать со структурами прозрачно.

Обсуждение паттерна Iterator

Составной объект, такой как список, должен предоставлять способ доступа к его элементам без раскрытия своей внутренней структуры. Более того, иногда нужно перебирать элементы списка различными способами, в зависимости от конкретной задачи. Но вы, вероятно, не хотите раздувать интерфейс списка операциями для различных обходов, даже если они необходимы. Кроме того, иногда нужно иметь несколько активных обходов одного списка одновременно. Было бы хорошо иметь единый интерфейс для обхода разных типов составных объектов (т.е. полиморфная итерация).

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

Абстракция Iterator имеет основополагающее значение для технологии, называемой "обобщенное программирование". Эта технология четко разделяет такие понятия как "алгоритм" и "структура данных". Мотивирующие факторы: способствование компонентной разработке, повышение производительности и снижение расходов на управление.

Рассмотрим пример. Если вы хотите одновременно поддерживать четыре вида структур данных (массив, бинарное дерево, связанный список и хэш-таблица) и три алгоритма (сортировка, поиск и слияние), то традиционный подход потребует 12 вариантов конфигураций (четыре раза по три), в то время как обобщенное программирование требует лишь 7 (четыре плюс три).

Структура паттерна Iterator

Для манипулирования коллекцией клиент использует открытый интерфейс класса Collection. Однако доступ к элементам коллекции инкапсулируется дополнительным уровнем абстракции, называемым Iterator. Каждый производный от Collection класс знает, какой производный от Iterator класс нужно создавать и возвращать. После этого клиент использует интерфейс, определенный в базовом классе Iterator.

UML-диаграмма классов паттерна Iterator

Пример паттерна Iterator

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

У телевизоров прошлого поколения для смены ТВ-каналов использовался вращающийся переключатель. Каждой позиции на переключателе назначался свой канал. У современных телевизоров для смены каналов можно использовать кнопки "Далее" и "Назад". Когда телезритель нажимает кнопку "Далее", будет отображаться следующий настроенный канал. Телезритель всегда может запросить следующий канал, не зная его номера.

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

Добавьте классу "коллекции" create_iterator()метод и назначьте привилегированный доступ классу "итератор".
Спроектируйте класс "итератор", инкапсулирующий обход "коллекции" класса.
Клиенты запрашивают у объекта Collectionсоздание объекта-итератора.
Клиенты используют the first(), is_done(), next()и current_item()для доступа к элементам класса Collection.

Особенности паттерна Iterator

Iterator может применяться для обхода сложных структур, создаваемых Composite.
Для создания экземпляра подкласса Iterator полиморфные итераторы используют Factory Method.
Часто Memento и Iterator используются совместно. Iterator может использовать Memento для сохранения состояния итерации и содержит его внутри себя.

Реализация паттерна Iterator

Реализация паттерна Iterator с использованием методов

Вынесите из коллекции функциональность "обход элементов коллекции" и придайте ей в "объектный статус". Это упростит саму коллекцию, позволит одновременно создавать множество активных обходов и отделит алгоритмы от структур данных коллекции.

Каждый контейнерный класс должен иметь итератор. Может показаться, что это является нарушением принципа инкапсуляции, так как пользователи класса Stack получают доступ к его содержимому напрямую. Однако Джон Лакош (John Lakos) приводит следующие аргументы: дизайнер класса неизбежно что-то упустит. Позже, когда пользователям потребуется дополнительная функциональность, если итератор первоначально был предусмотрен, то они смогут добавить эту функциональность в соответствии с принципом "открыт для расширения, закрыт для модификации". Без наличия итератора их единственным выходом было бы докучливое изменение рабочего кода. Ниже исходный класс Stack не содержит оператор равенства, но имеет итератор. В результате, оператор равенства может быть легко добавлен.

Спроектируйте класс "итератор" для класса "контейнер".
Добавьте контейнерному классу createIterator()метод.
Клиенты запрашивают у объекта "контейнер" создание объекта-итератора.
Клиенты используют first(), is_done(), next()и current_item()методы.

#include <iostream>
using namespace std;

class Stack
{
    int items[10];
    int sp;
  public:
    friend class StackIter;
    Stack()
    {
        sp =  - 1;
    }
    void push(int in)
    {
        items[++sp] = in;
    }
    int pop()
    {
        return items[sp--];
    }
    bool isEmpty()
    {
        return (sp ==  - 1);
    }
    // 2. Добавьте член createIterator()
    StackIter *createIterator() const;
};

// 1. Спроектируйте класс "iterator"
class StackIter
{
    const Stack *stk;
    int index;
  public:
    StackIter(const Stack *s)
    {
        stk = s;
    }
    void first()
    {
        index = 0;
    }
    void next()
    {
        index++;
    }
    bool isDone()
    {
        return index == stk->sp + 1;
    }
    int currentItem()
    {
        return stk->items[index];
    }
};

StackIter *Stack::createIterator()const
{
  return new StackIter(this);
}

bool operator == (const Stack &l, const Stack &r)
{
  // 3. Клиенты запрашивают создание объекта StackIter у объекта Stack
  StackIter *itl = l.createIterator();
  StackIter *itr = r.createIterator();
  // 4. Клиенты используют first(), isDone(), next(), and currentItem()
  for ( itl->first(), itr->first(); 
       !itl->isDone(); 
        itl->next(), itr->next() )
    if (itl->currentItem() != itr->currentItem())
      break;
  bool ans = itl->isDone() && itr->isDone();
  delete itl;
  delete itr;
  return ans;
}

int main()
{
  Stack s1;
  for (int i = 1; i < 5; i++)
    s1.push(i);
  Stack s2(s1), s3(s1), s4(s1), s5(s1);
  s3.pop();
  s5.pop();
  s4.push(2);
  s5.push(9);
  cout << "1 == 2 is " << (s1 == s2) << endl;
  cout << "1 == 3 is " << (s1 == s3) << endl;
  cout << "1 == 4 is " << (s1 == s4) << endl;
  cout << "1 == 5 is " << (s1 == s5) << endl;
}

Вывод программы:

1 == 2 is 1
1 == 3 is 0
1 == 4 is 0
1 == 5 is 0

Реализация паттерна Iterator: использование операторов вместо методов

Джон Лакош отмечает, что интерфейсы GOF-итераторов дают возможность неправильного написания имен методов, являются неуклюжими и требуют слишком много печати. Представленная ниже реализация паттерна Iterator основана на использовании "интуитивных" операторов. Отметим также, что метод createIterator() больше не нужен. Пользователь создает итераторы как локальные переменные, поэтому очистка не требуется.

#include <iostream>
using namespace std;

class Stack
{
    int items[10];
    int sp;
  public:
    friend class StackIter;
    Stack()
    {
        sp =  - 1;
    }
    void push(int in)
    {
        items[++sp] = in;
    }
    int pop()
    {
        return items[sp--];
    }
    bool isEmpty()
    {
        return (sp ==  - 1);
    }
};

class StackIter
{
    const Stack &stk;
    int index;
  public:
    StackIter(const Stack &s): stk(s)
    {
        index = 0;
    }
    void operator++()
    {
        index++;
    }
    bool operator()()
    {
        return index != stk.sp + 1;
    }
    int operator *()
    {
        return stk.items[index];
    }
};

bool operator == (const Stack &l, const Stack &r)
{
  StackIter itl(l), itr(r);
  for (; itl(); ++itl, ++itr)
    if (*itl !=  *itr)
      break;
  return !itl() && !itr();
}

int main()
{
  Stack s1;
  int i;
  for (i = 1; i < 5; i++)
    s1.push(i);
  Stack s2(s1), s3(s1), s4(s1), s5(s1);
  s3.pop();
  s5.pop();
  s4.push(2);
  s5.push(9);
  cout << "1 == 2 is " << (s1 == s2) << endl;
  cout << "1 == 3 is " << (s1 == s3) << endl;
  cout << "1 == 4 is " << (s1 == s4) << endl;
  cout << "1 == 5 is " << (s1 == s5) << endl;
}