Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Введение в архитектуру программного обеспечения

Паттерн Iterator (Итератор, Cursor, Курсор)

Название и классификация паттерна

Итератор — паттерн поведения объектов.

Назначение

Предоставляет способ последовательного доступа ко всем элементам составного объекта, не раскрывая его внутреннего представления.

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

Придает обходу коллекции «объектно-ориентированный статус».

Полиморфный обход.

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

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

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

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

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

В классе Iterator определен интерфейс для доступа к элементам списка. Объект этого класса отслеживает текущий элемент, т. е. он располагает информацией, какие элементы уже посещались. Например, класс List мог бы предусмотреть класс Listlterator (рис. 66).

List

list

Listlterator

Count()

First()

Append(Element)

Next()

Remove(Element)

IsDoneQ

...

CurrentltemQ

index

Рис. 66. Интерфейс для доступа к элементам списка

Прежде чем создавать экземпляр класса Listlterator, необходимо иметь список, подлежащий обходу. С объектом Listlterator вы можете последовательно посетить все элементы списка. Операция Currentltem возвращает текущий элемент списка, операция First инициализирует текущий элемент первым элементом списка, Next делает текущим следующий элемент, a IsDone проверяет, не оказались ли мы за последним элементом, если да, то обход завершен.

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

Применимость

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

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

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

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

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

Структура паттерна Итератор приведена на рис. 67.

UML-диаграмма паттерна Итератор

Рис. 67. UML-диаграмма паттерна Итератор

I

I

Участники

Iterator — Итератор: определяет интерфейс для доступа и обхода элементов.

Concretelterator — конкретный Итератор:

  • • реализует интерфейс класса Iterator;
  • • следит за текущей позицией при обходе агрегата.

Aggregate — агрегат: определяет интерфейс для создания объекта-итератора.

ConcreteAggregate — конкретный агрегат: реализует интерфейс создания Итератора и возвращает экземпляр подходящего класса Concretelterator.

Результаты

У паттерна Итератор есть следующие важные особенности:

  • поддерживает различные виды обхода агрегата. Сложные агрегаты можно обходить по-разному. Генератор кода может обходить дерево во внутреннем или прямом порядке. Итераторы упрощают изменение алгоритма обхода — достаточно просто заменить один экземпляр Итератора другим. Для поддержки новых видов обхода можно определить и подклассы класса Iterator,
  • Итераторы упрощают интерфейс класса Aggregate. Наличие интерфейса для обхода в классе Iterator делает излишним дублирование этого интерфейса в классе Aggregate',
  • одновременно для данного агрегата может быть активно несколько обходов. Итератор следит за инкапсулированным в нем самом состоянием обхода. Поэтому одновременно разрешается осуществлять несколько обходов агрегата.

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

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

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

Каждый контейнерный класс должен иметь Итератор. Может показаться, что это является нарушением принципа инкапсуляции, так как пользователи класса Stack получают доступ к его содержимому напрямую. Однако при проектировании класса неизбежно что-то будет упущено. Позже, когда потребуется внести дополнительную функциональность, если Итератор первоначально был предусмотрен, то можно будет добавить эту функциональность в соответствии с принципом «открыт для расширения, закрыт для модификации».

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

#include

using namespace std;

class Stack

{

int items[ 10]; int sp; public:

friend class Stacklter;

Stack()

{

sp = - 1;

}

void push(int in)

{

items[++sp] = in;

}

int pop()

{

return items[sp--];

}

bool isEmpty()

{

return (sp == - 1);

}

//2. Добавьте член createIterator() Stacklter *create!terator() const;

// 1. Спроектируйте класс "iterator" class Stacklter

{

const Stack *stk; intindex; public:

StackIter(const Stack *s)

{

stk = s;

}

void first()

{

index = 0;

}

void next()

{

index++;

}

bool isDone()

{

return index == stk->sp + 1;

}

int currentltemO

{

return stk->items[index];

}

};

Stacklter *Stack::createIterator()const

{

return new Stacklter(this);

}

bool operator == (const Stack &1, const Stack &r)

{

// 3. Клиенты запрашивают создание объекта Stacklter у объекта Stack Stacklter *itl = l.createIterator();

Stacklter *itr = r.createIterator();

// 4. Клиенты используют first(), isDone(), next(), and currentltemO for (itl->first(), itr->first();

!itl->isDone(); itl->next(), itr->next()) if (itl->currentltem() != itr->currentltem()) break;

bool ans = itl->isDone() && itr->isDone(); delete itl; delete itr; return ans;

}

int main()

{

Stack si;

for (int i = 1; i < 5; i++) sl.push(i);

Stacks2(sl), s3(sl), s4(sl), s5(sl);

s3.pop();

s5.pop();

s4.push(2);

s5.push(9);

cout << "1 2 is" << (si s2) << endl;

cout << "1 == 3 is" << (si s3) << endl;

cout << "1 == 4 is" << (si s4) << endl;

cout << "1 5 is" << (si s5) << endl;

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

1 == 2 is 1 1 == 3 is О 1 == 4 is О 1 == 5 is О

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

Представленная ниже реализация паттерна Iterator основана на использовании «интуитивных» операторов. Отметим также, что метод CreateIterator() больше не нужен. Пользователь создает Итераторы как локальные переменные, поэтому очистка не требуется.

#include using namespace std;

class Stack

{

int items[10]; int sp; public:

friend class Stacklter;

Stack()

{

sp = - 1;

}

void push(int in)

{

items[++sp] = in;

}

int pop()

{

return items[sp--];

}

bool isEmpty()

{

return (sp == - 1);

}

};

class Stacklter

{

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 &1, const Stack &r)

{

Stacklter itl(l), itr(r); for (; itl(); ++itl, ++itr) if (*itl != *itr) break;

return !itl() && !itr();

}

int main()

{

Stack si; int i;

for (i = 1; i < 5; i++) sl.push(i);

Stacks2(sl), s3(sl), s4(sl), s5(sl);

s3.pop();

s5.pop();

s4.push(2);

s5.push(9);

cout << "1 2 is" << (si s2) << endl;

cout << "1 3 is" << (si s3) << endl;

cout << "1 4 is" << (si s4) << endl;

cout << "1 5 is" << (si s5) << endl;

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

  • 1 == 2 is 1
  • 1 == 3 is О
  • 1 == 4 is О
  • 1 == 5 is О

Родственные паттерны

Компоновщик: Итераторы довольно часто применяются для обхода рекурсивных структур, создаваемых Компоновщиком.

Фабричный метод: полиморфные Итераторы поручают Фабричным методам инстанцировать подходящие подклассы класса Iterator.

Итератор может использовать Хранитель для сохранения состояния итерации и при этом содержит его внутри себя.

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ   След >
 

Популярные страницы