Patterns. Паттерн Iterator (Cursor). Общие сведения




Паттерн Iterator (Cursor). Общие сведения. Способы реализации. Структурная схема. Пример на C++


Содержание


Поиск на других ресурсах:

1. Назначение паттерна Iterator (Ітератор)

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

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

 

2. Общие сведения об агрегированных структурах данных и итераторах

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

Примеры контейнеров, для которых целесообразно применять итераторы:

  • набор битов (bitset);
  • различные виды очередей: обычная очередь (queue), двусторонняя очередь (deque), очередь с приоритетами (priority queue);
  • стек;
  • динамический массив;
  • линейный список;
  • множество;
  • хеш-таблица (map, multimap).

Для вышеуказанных контейнеров используются различные итераторы, которые обеспечивают их обход, например:

  • двунаправленный итератор. Этот вид итератора предназначен для хранения и извлечения значений. Перемещение по элементам контейнера происходит в обоих направлениях (вперед и назад);
  • прямой итератор. Сохраняет и извлекает значение из контейнера. Перемещается только вперед;
  • итератор ввода. Осуществляет только вытягивание элементов. Перемещается только вперед;
  • итератор вывода. Осуществляет только хранение элементов. Перемещается только вперед;
  • итератор произвольного доступа. Данный итератор предназначен для хранения и извлечения значений из контейнера. Итератор обеспечивает произвольный доступ к элементам.

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

 

3. Способы реализации паттерна Iterator. Обобщенная структура паттерна Iterator (Cursor)

С точки зрения поддержки различных типов контейнеров и итераторов, паттерн Iterator может быть реализован одним из четырех возможных способов:

  • поддержка строго определенного контейнера и строго определенного итератора (рисунок 1);
  • поддержка нескольких видов контейнеров (полиморфных контейнеров) и общего итератора (рисунок 2);
  • поддержка определенного контейнера и нескольких (полиморфных) итераторов (рисунок 3);
  • поддержка нескольких видов контейнеров и нескольких итераторов (рисунок 4).

 

3.1. Один контейнер и один итератор
3.1.1. Структура. Рисунок

Простейший случай применения паттерна Iterator — это случай, когда существует один контейнерный класс и для него реализован один итератор. В этом случае структура паттерна выглядит, как показано на рисунке 1.

Структура паттерна Iterator для одного агрегата и одного итератора

Рисунок 1. Структура паттерна Iterator для одного агрегата и одного итератора (простейший случай)

 

3.1.2. Реализация на C++. Текст программы

Ниже приведена реализация паттерна Iterator для структуры, изображенной на рисунке 1. Реализация имеет следующие особенности:

  • контейнером служит динамический массив элементов;
  • в качестве итератора выбран прямой итератор.

 

#include <iostream>
using namespace std;

// Паттерн Iterator для одного агрегата и одного итератора
// Предварительное объявление класса
template <class T>
class Aggregate;

// Класс итератора
template <class T>
class Iterator
{
private:
  const Aggregate<T>* aggregate;
  long current;

public:
  // Конструктор, получающий агрегированный объект
  Iterator(const Aggregate<T>* _aggregate) :
    aggregate(_aggregate), current(0)
  { }

  // Переход (перевод курсора) в начало списка
  virtual void First()
  {
    current = 0;
  }

  // Переход (перевод курсора) на следующий элемент списка
  virtual void Next()
  {
    current++;
  }

  // Проверка, достигнут ли конец списка,
  // текущая позиция курсора находится за последним элементом списка
  virtual bool IsDone() const
  {
    return current >= aggregate->Count();
  }

  // Получить элемент списка по текущей позиции курсора
  virtual T CurrentItem() const
  {
    if (!IsDone())
      return aggregate->GetItem(current);
    else
    {
      // Здесь ошибка, можно сгенерировать исключение или
      // выполнить другие действия
      cout << "Error." << endl;
      return 0;
    }
  }
};

// Класс агрегата
template <class T>
class Aggregate
{
private:
  // данные агрегата (список, массив, ...)
  T* data;
  long count;

public:
  // Конструктор
  Aggregate(long _count)
  {
    if (_count < 0)
    {
      count = 0;
      data = nullptr;
      return;
    }

    try
    {
      data = new T[_count];
      count = _count;

      for (int i = 0; i < count; i++)
        data[i] = (T)0;
    }
    catch (bad_alloc e)
    {
      cout << e.what() << endl;
      count = 0;
      data = nullptr;
    }
  }

  // Конструктор копирования
  Aggregate(const Aggregate& obj)
  {
    // скопировать данные из obj в текущий экземпляр
    count = obj.count;

    // выделить память для массива в целом
    try
    {
      data = new T[count];
      for (int i = 0; i < count; i++)
        data[i] = obj.data[i];
    }
    catch (bad_alloc e)
    {
      cout << e.what() << endl;
      count = 0;
    }
  }

  // Метод, возвращающий итератор
  Iterator<T>* CreateIterator() const
  {
    return new Iterator<T>(this);
  }

  // Другие методы класса ConcreteAggregate
  long Count() const
  {
    return count;
  }

  T GetItem(long index) const
  {
    if ((index >= 0) && (index < count))
      return data[index];
    return data[0];
  }

  // Метод, добавляющий в конец списка элемент
  void Append(T value)
  {
    T* data2 = data;
    data = new T[count + 1];
    for (int i = 0; i < count; i++)
      data[i] = data2[i];
    data[count++] = value;
    delete[] data2;
  }

  // Удаление элемента из списка,
  // index = 0, 1, ..., count-1
  void Remove(long index)
  {
    if ((index >= 0) && (index < count))
    {
      // Удалить элемент из списка
      T* data2 = data;
      data = new T[count - 1];

      for (int i = 0; i < index; i++)
        data[i] = data2[i];
      for (int i = index + 1; i < count; i++)
        data[i - 1] = data2[i];

      count--;
      delete[] data2;
    }
  }

  // Деструктор
  ~Aggregate()
  {
    if (count > 0)
      delete[] data;
  }

  // Вывод содержимого агрегата
  void Print(string text)
  {
    cout << text << endl;
    for (int i = 0; i < count; i++)
      cout << data[i] << " ";
    cout << endl;
  }
};

void main()
{
  // Демонстрация использования паттерна Iterator
  // 1. Создать агрегат
  Aggregate<double> ag(0);
  ag.Append(2.55);
  ag.Append(3.8);
  ag.Append(-1.557);
  ag.Append(7.32);

  // 2. Вывести агрегат на экран
  ag.Print("ag:");

  // 3. Создать итератор
  Iterator<double>* it = ag.CreateIterator();

  // 4. Вывести первый элемент агрегата
  double x = it->CurrentItem();
  cout << "x = " << x << endl;

  // 5. Вывести все элементы агрегата в цикле
  cout << "-------------" << endl;
  cout << "Items in ag: ";
  it->First();
  while (!it->IsDone())
  {
    cout << it->CurrentItem() << " ";
    it->Next();
  }

  // 6. Освободить память, выделенную для it
  delete it;
}

 

3.1.3. Реализация на C++. Гарантированное удаление итератора

В предыдущем пункте 3.1.2 в коде клиента (функция main()) итератор получался с помощью метода CreateIterator() следующим образом

...

// 3. Создать итератор
Iterator<double>* it = ag.CreateIterator();

...

Это обязывало клиента удалять память, выделенную для указателя it после его использования

...

// 6. Освободить память, выделенную для it
delete it;

...

Причиной этого является утечка памяти (memory leak).

Чтобы упростить работу клиента необходимо создать дополнительный класс, который будет замещать итератор и автоматически уничтожать объект типа Iterator<T> при выходе из области определения.

Ниже приведен код этого класса.

template <class T>
class IteratorPtr
{
private:
  // Внутреннее поле - итератор как указатель
  Iterator<T>* it;

public:
  // Конструктор класса
  IteratorPtr(Iterator<T>* _it) : it(_it) { }

  // Деструктор
  ~IteratorPtr()
  {
    delete it;
  }

  // Переопределенный оператор доступа по указателю ->
  Iterator<T>* operator->()
  {
    return it;
  }

  // Переопределенный оператор доступа по указателю *
  Iterator<T>& operator*()
  {
    return *it;
  }

private:
  // Запретить копирование
  IteratorPtr(const IteratorPtr&); // скрыть конструктор копирования

  // Запретить присваивание - определить оператор = в разделе private
  IteratorPtr& operator=(const IteratorPtr&)
  {
  }
};

Как видно из вышеприведенного кода, основными методами являются операторные функции operator->() и operator*(), которые переопределяют доступ к итератору типа Iterator<T> по указателю. В конструкторе выделяется память для указателя it. В деструкторе эта память освобождается. Поэтому клиенту не нужно заниматься дополнительно освобождением памяти для указателя it.

После введения класса IteratorPtr в код программы с п. 3.1.2, код клиента может быть таким

...

void main()
{
  // Использовать класс IteratorPtr в коде клиента
  // 1. Создать агрегат
  Aggregate<double> ag(0);
  ag.Append(2.55);
  ag.Append(3.8);
  ag.Append(-1.557);
  ag.Append(7.32);

  // 2. Вывести агрегат на экран
  ag.Print("ag:");

  // 3. Создать экземпляр класса IteratorPtr
  IteratorPtr<double> itPtr(ag.CreateIterator());

  // 4. Вывести список элементов с помощью itPtr
  cout << "-------------------------" << endl;
  itPtr->First(); // установить первый элемент
  while (!itPtr->IsDone())
  {
    cout << itPtr->CurrentItem() << " ";
    itPtr->Next();
  }
}

 

3.2. Полиморфный контейнер и один итератор. Структура. Рисунок

Если нужно использовать один итератор для агрегатов различной реализации, то структура паттерна Iterator выглядит как показано на рисунке 2. Создается абстрактный класс Aggregate, который расширяется несколькими конкретными агрегатами ConcreteAggregate1, ConcreteAggregate2 … Каждый конкретный агрегат имеет уникальную реализацию хранения наборов данных.

Структура паттерна Iterator. Случай с несколькими контейнерами и одним итератором

Рисунок 2. Структура паттерна Iterator. Случай с несколькими контейнерами и одним итератором

 

3.3. Контейнер с поддержкой нескольких итераторов. Рисунок

Для одного контейнера может быть реализовано несколько видов итераторов. Эти итераторы могут реализовать различные способы обхода элементов контейнера (смотрите п. 2). В этом случае итератор должен быть реализован так, что исчезает зависимость от конкретной реализации. На рисунке 3 изображена структура паттерна Iterator в котором нет зависимости от конкретной реализации итератора, то есть реализован полиморфный итератор. Создается абстрактный класс Iterator, который наследуется специализированными итераторами ConcreteIterator1, ConcreteIterator2 и т.д.

Структура паттерна Iterator. Случай с одним контейнером и несколькими итераторами

Рисунок 3. Структура паттерна Iterator. Случай с одним контейнером и несколькими итераторами

 

3.4. Полиморфный контейнер и полиморфный итератор. Рисунок

На рисунке 4 изображена структура паттерна Iterator для одного агрегированного объекта (контейнера) с возможностью поддержки нескольких агрегированных объектов и нескольких итераторов.

Поддержка нескольких агрегированных объектов обеспечивается объявлением абстрактного класса Aggregate, который служит интерфейсом между клиентом и конкретным агрегатом (классом ConcreteAgregate и/или иным классом). Аналогично, абстрактный класс Iterator является интерфейсом между клиентом и конкретными итераторами, реализующими различные способы обхода агрегированного объекта. Таким образом обеспечивается полиморфизм для контейнера и итератора.

Структура паттерна Iterator с поддержкой полиморфного контейнера и полиморфного итератора

Рисунок 4. Структура паттерна Iterator с поддержкой полиморфного контейнера и полиморфного итератора

 

4. Необходимость (преимущества) применения итераторов для контейнеров

К преимуществам применения паттерна Iterator можно отнести следующие:

  • обеспечение доступа к содержимому агрегированных объектов без раскрытия их внутренней реализации. Понятно, что в коде контейнерного класса можно дополнительно реализовать необходимый функционал для различных видов обхода агрегированных объектов. Однако, такой подход значительно усложнит интерфейс самого контейнерного класса. Более целесообразно отделить основные операции над контейнером от операций обхода элементов контейнера;
  • обеспечение поддержки различных вариантов обхода агрегированного объекта (однонаправленный обход, произвольный обход и т.п.);
  • обеспечение единообразного полиморфного интерфейса с целью обхода разнотипных агрегированных объектов (список, семантическое дерево, динамический массив и т.д.).

 


Связанные темы