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 можна віднести наступні:

  • забезпечення доступу до вмісту агрегованих об’єктів без розкриття їх внутрішньої реалізації. Зрозуміло, що в коді контейнерного класу можна додатково реалізувати необхідний функціонал для різних видів обходу агрегованих об’єктів. Однак, такий підхід значно ускладнить інтерфейс самого контейнерного класу. Більш доцільно відділити основні операції над контейнером від операцій обходу елементів контейнера.;
  • забезпечення підтримки різних варіантів обходу агрегованого об’єкту (однонаправлений обхід, довільний обхід тощо);
  • забезпечення єдиноподібного поліморфного інтерфейсу з метою обходу різнотипних агрегованих об’єктів (список, семантичне дерево, динамічний масив тощо).

 


Зв’язані теми