Ітератор (шаблон проєктування)
Ітератор (англ. Iterator) — шаблон проєктування, належить до класу шаблонів поведінки.
Призначення
Надає спосіб послідовного доступу до всіх елементів складеного об'єкта, не розкриваючи його внутрішнього улаштування.
Мотивація
Складений об'єкт, скажімо список, повинен надавати спосіб доступу до своїх елементів, не розкриваючи їхню внутрішню структуру. Більш того, іноді треба обходити список по-різному, у залежності від задачі, що вирішується. При цьому немає ніякого бажання засмічувати інтерфейс класу Список усілякими операціями для усіх потрібних варіантів обходу, навіть якщо їх усі можна передбачити заздалегідь. Крім того, іноді треба, щоб в один момент часу існувало декілька активних операцій обходу списку.
Все це призводить до необхідності реалізації шаблону Ітератор. Його основна ідея у тому, щоб за доступ до елементів та обхід списку відповідав не сам список, а окремий об'єкт-ітератор. У класі Ітератор означений інтерфейс для доступу до елементів списку. Об'єкт цього класу прослідковує поточний елемент, тобто він володіє інформацією, які з елементів вже відвідувались.
Застосовність
Можна використовувати шаблон Ітератор у випадках:
- для доступу до змісту агрегованих об'єктів не розкриваючи їхнє внутрішнє улаштування;
- для підтримки декількох активних обходів одного й того ж агрегованого об'єкта;
- для подання уніфікованого інтерфейсу з метою обходу різноманітних агрегованих структур (тобто для підтримки поліморфної ітерації).
Структура
- Iterator
- визначає інтерфейс для доступу та обходу елементів
- ConcreteIterator
- реалізує інтерфейс класу Iterator;
- слідкує за поточною позицією під час обходу агрегату;
- Aggregate
- визначає інтерфейс для створення об'єкта-ітератора;
- ConcreteAggregate
- реалізує інтерфейс створення ітератора та повертає екземпляр відповідного класу ConcreteIterator
Відносини
ConcreteIterator відслідковує поточний об'єкт у агрегаті та може вирахувати наступний.
Переваги
- Спільний інтерфейс використання
- Перебір колекції
Недоліки
- Основною проблемою ітераторів є те, що реалізація ітераторів може бути складною
Реалізація
C++
#include <iostream>
using namespace std;
// вузол, що є частиною списку
struct Node
{
double item;
Node* next;
Node(double x, Node* link = 0) :
item(x), next(link) {}
};
// «примітивний» ітератор списку
class listIter
{
private:
Node* p;
public:
listIter() :p(0) {}
listIter(Node* ptr) : p(ptr) {}
double& operator*() { return p->item; }
listIter& operator++() { p = p->next; return *this; }
bool operator!=(const listIter& a) { return p != a.p; }
};
// інтерфейс колекції, яка підтримує ітератор
class List
{
private:
Node * first;
Node * last;
public:
List()
{
first = last = new Node(0);
}
~List()
{
while (first != last)
{
Node * victim = first;
first = first->next;
delete victim;
}
delete first;
}
List& add(double el)
{
last = last->next = new Node(el);
return *this;
}
listIter begin()
{
return listIter(first->next);
}
listIter end()
{
return listIter();
}
};
void main()
{
List list;
list.add(4).add(2);
listIter iter = list.begin();
while (iter != list.end())
{
cout << *iter;
++iter;
}
for (listIter iter2 = list.begin(); iter2 != list.end(); ++iter2)
{
cout << *iter2;
}
}
Але щоб ітератор працював із стандартними алгоритмами, варто унаслідувати його від стандартних:
class Iterator : public iterator<bidirectional_iterator_tag,double>
C#
В мові програмування C# шаблон ітератор є вбудованим, його використання можливе за допомогою оператору foreach, за умови, що відповідний контейнер реалізує інтерфейс IEnumerable.
Наприклад:
string[] strings = new string[] { "one", "two", "three" };
foreach (string str in strings)
{
Console.WriteLine(str);
}
Таку форму запису можна замінити на більш низько-рівневу, але еквівалентну:
string[] strings = new string[] { "one", "two", "three" };
IEnumerator enumerator = strings.GetEnumerator();
while (enumerator.MoveNext())
{
Console.WriteLine((string)enumerator.Current);
}
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
namespace IteratorPattern
{
public class Tree : IEnumerable<int>
{
private class Node
{
public int Value { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
}
private Node _root;
public Tree Add(int value)
{
_root = AddInternal(value, _root);
return this;
}
private Node AddInternal(int value, Node node)
{
if (node == null)
{
node = new Node { Value = value };
}
else if (value > node.Value)
{
node.Right = AddInternal(value, node.Right);
}
else if (value < node.Value)
{
node.Left = AddInternal(value, node.Left);
}
return node;
}
// приклад реалізації за допомогою блока ітератора
// (вбудована можливість мови програмування)
#region Inbuilt
public IEnumerator<int> GetEnumerator()
{
return IterateInOrder(_root).GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
private IEnumerable<int> IterateInOrder(Node node)
{
if (node == null) yield break;
// ARB
foreach (var l in IterateInOrder(node.Left)) yield return l;
yield return node.Value;
foreach (var r in IterateInOrder(node.Right)) yield return r;
}
#endregion
// приклад реалізації ітератора на даній платформі
#region Net
public BreadthFirstIterator GetBreadthFirstIterator() => new BreadthFirstIterator(this);
public class BreadthFirstIterator // : IEnumerator<int>
{
private readonly Tree _tree;
private Node _currentNode;
private Queue<Node> _nodeQueue;
public int Current => _currentNode.Value;
public BreadthFirstIterator(Tree tree)
{
_tree = tree;
Reset();
}
public bool MoveNext()
{
if (!_nodeQueue.Any()) return false;
_currentNode = _nodeQueue.Dequeue();
if (_currentNode.Left != null) _nodeQueue.Enqueue(_currentNode.Left);
if (_currentNode.Right != null) _nodeQueue.Enqueue(_currentNode.Right);
return true;
}
public void Reset()
{
_nodeQueue = new Queue<Node>(capacity: 3);
_nodeQueue.Enqueue(_tree._root);
}
}
#endregion
// класичний приклад реалізації ітератора
#region Classic
public DepthFirstIterator GetDepthFirstIterator() => new DepthFirstIterator(this);
public class DepthFirstIterator // можлива реалізація загального інтерфейсу
{
private readonly Stack<Node> _nodeStack;
public int Current => _nodeStack.Peek().Value;
public DepthFirstIterator(Tree tree)
{
_nodeStack = new Stack<Node>(capacity: 3);
_nodeStack.Push(tree._root);
}
public void Next()
{
var currentNode = _nodeStack.Pop();
if (currentNode.Left != null) _nodeStack.Push(currentNode.Left);
if (currentNode.Right != null) _nodeStack.Push(currentNode.Right);
}
public bool HasNext()
{
return _nodeStack.Any();
}
}
#endregion
}
class Program
{
static void Main(string[] args)
{
// 5
// / \
// 2 8
// / \
// 1 3
var tree = new Tree();
tree.Add(5).Add(2).Add(8).Add(1).Add(3);
Console.WriteLine("Inbuilt iterator (yield return)");
// foreach (var v in tree) Console.WriteLine(v);
var enumerator = tree.GetEnumerator();
while (enumerator.MoveNext())
{
Console.WriteLine(enumerator.Current);
}
Console.WriteLine("Breadth first iterator (Net version)");
var iterator = tree.GetBreadthFirstIterator();
while (iterator.MoveNext())
{
Console.WriteLine(iterator.Current);
}
Console.WriteLine("Depth first iterator (classic)");
for (var i = tree.GetDepthFirstIterator(); i.HasNext(); i.Next())
{
Console.WriteLine(i.Current);
}
}
}
}
Література
Алан Шаллоуей, Джеймс Р. Тротт. Шаблоны проектирования. Новый подход к объектно-ориентированному анализу и проектированию = Design Patterns Explained: A New Perspective on Object-Oriented Design. — М. : «Вильямс», 2002. — 288 с. — ISBN 0-201-71594-5.