Ітератор (шаблон проєктування)

В об'єктно-орієнтованому програмуванні шаблон проектування ітератор — це шаблон проектування^[1], у якому ітератор використовується для обходу колекції^[en] та доступу до елементів колекції. Шаблон ітератора відокремлює алгоритми від колекції; у деяких випадках алгоритми обов'язково залежать від колекції і тому не можуть бути відокремлені.

Наприклад, гіпотетичний алгоритм ЗнайтиЕлемент може бути реалізований загалом за допомогою певного типу ітератора, а не реалізований як специфічний для колекції алгоритм. Це дозволяє використовувати ЗнайтиЕлемент у будь-якій колекції, яка підтримує необхідний тип ітератора.

Шаблон проектування Ітератор є одним із двадцяти трьох відомих шаблонів проектування GoF, які описують, як розв'язувати повторювані проблеми проектування для розробки гнучкого та багаторазового об'єктно-орієнтованого програмного забезпечення, тобто об'єктів, які легше реалізувати, змінити, тестування та повторне використання. Належить до класу шаблонів поведінки.

Призначення[ред. | ред. код]

Надає спосіб послідовного доступу до всіх елементів складеного об'єкта, не розкриваючи його внутрішнього улаштування.

Мотивація[ред. | ред. код]

Складений об'єкт, скажімо список, повинен надавати спосіб доступу до своїх елементів, не розкриваючи їхню внутрішню структуру. Більш того, іноді треба обходити список по-різному, у залежності від задачі, що вирішується. При цьому немає ніякого бажання засмічувати інтерфейс класу Список усілякими операціями для усіх потрібних варіантів обходу, навіть якщо їх усі можна передбачити заздалегідь. Крім того, іноді треба, щоб в один момент часу існувало декілька активних операцій обходу списку.

Все це призводить до необхідності реалізації шаблону Ітератор. Його основна ідея у тому, щоб за доступ до елементів та обхід списку відповідав не сам список, а окремий об'єкт-ітератор. У класі Ітератор означений інтерфейс для доступу до елементів списку. Об'єкт цього класу прослідковує поточний елемент, тобто він володіє інформацією, які з елементів вже відвідувались.

Застосовність[ред. | ред. код]

Можна використовувати шаблон Ітератор у випадках:

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

Структура[ред. | ред. код]

• 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); 			} 		} 	} } 

Python[ред. | ред. код]

Python визначає синтаксис для ітераторів як частину самої мови, так що ключові слова мови, такі як for, працюють з тим, що Python називає ітераторами. Ітератор має метод __iter__(), який повертає об'єкт ітератора. «Протокол ітератора» вимагає, щоб next() повернув наступний елемент або викликав виключення StopIteration після досягнення кінця послідовності елементів ітератора. Ітератори також надають метод __iter__(), який повертає себе, щоб їх також можна було повторити; наприклад, за допомогою циклу for. Генератори доступні з версії 2.2.

У Python 3 next() було перейменовано на __next__().^[2]

Див. також[ред. | ред. код]

• Композитний візерунок
• Колекція (структура даних)^[en]
• Шаблон проектування (інформатика)
• Ітератор
• Шаблон спостерігача

Примітки[ред. | ред. код]

Джерела[ред. | ред. код]

• Design Patterns: Elements of Reusable Object-Oriented Software [Архівовано 9 листопада 2012 у Wayback Machine.]
• Ітерація об'єктів у PHP
• Шаблон ітератора в C#
• Шаблон ітератора в UML і LePUS3 (формальна мова моделювання)
• Навчальний посібник із SourceMaking
• Підручник із прикладами впровадження шаблонів дизайну
• Шаблон ітератора

Література[ред. | ред. код]

Алан Шаллоуей, Джеймс Р. Тротт. Шаблоны проектирования. Новый подход к объектно-ориентированному анализу и проектированию = Design Patterns Explained: A New Perspective on Object-Oriented Design. — М. : «Вильямс», 2002. — 288 с. — ISBN 0-201-71594-5.