Editing Iterator pattern

{{Short description|Software design pattern}}
In [[object-oriented programming]], the '''iterator pattern''' is a [[design pattern (computer science)|design pattern]] in which an [[iterator]] is used to traverse a [[Collection (abstract data type)|container]] and access the container's elements. The iterator pattern decouples [[algorithm]]s from containers; in some cases, algorithms are necessarily container-specific and thus cannot be decoupled.

For example, the hypothetical algorithm ''SearchForElement'' can be implemented generally using a specified type of iterator rather than implementing it as a container-specific algorithm. This allows ''SearchForElement'' to be used on any container that supports the required type of iterator.
{{TOC limit|3}}

==Overview==
The Iterator
<ref name="GoF">{{cite book|url=https://archive.org/details/designpatternsel00gamm/page/257|title=Design Patterns: Elements of Reusable Object-Oriented Software|author=Erich Gamma|last2=Richard Helm|last3=Ralph Johnson|last4=John Vlissides|publisher=Addison Wesley|year=1994|isbn=0-201-63361-2|pages=[https://archive.org/details/designpatternsel00gamm/page/257 257ff]|url-access=registration}}</ref>
design pattern is one of the 23 well-known 
''[[Design Patterns|"Gang of Four" design patterns]]'' 
that describe how to solve recurring design problems to design flexible and reusable object-oriented software, that is, objects that are easier to implement, change, test, and reuse.

===What problems can the Iterator design pattern solve?===
<ref>{{cite web|title=The Iterator design pattern - Problem, Solution, and Applicability|url=http://w3sdesign.com/?gr=b04&ugr=proble|website=w3sDesign.com|access-date=2017-08-12}}</ref>
* The elements of an aggregate object should be accessed and traversed without exposing its representation (data structures).
* New traversal operations should be defined for an aggregate object without changing its interface.

Defining access and traversal operations in the aggregate interface is inflexible because it commits the aggregate to particular access and traversal operations and makes it impossible to add new operations
later without having to change the aggregate interface.

===What solution does the Iterator design pattern describe?===

* Define a separate (iterator) object that encapsulates accessing and traversing an aggregate object.
* Clients use an iterator to access and traverse an aggregate without knowing its representation (data structures).

Different iterators can be used to access and traverse an aggregate in different ways. 
<br>New access and traversal operations can be defined independently by defining new iterators.

See also the UML class and sequence diagram below.

==Definition==
The essence of the Iterator Pattern is to "Provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation.".<ref>[[Design Patterns (book)|Gang Of Four]]</ref>

== Structure ==
=== UML class and sequence diagram ===
[[File:w3sDesign Iterator Design Pattern UML.jpg|frame|none|A sample UML class and sequence diagram for the Iterator design pattern.<ref>{{cite web|title=The Iterator design pattern - Structure and Collaboration|url=http://w3sdesign.com/?gr=b04&ugr=struct|website=w3sDesign.com|access-date=2017-08-12}}</ref>]]
In the above [[UML]] [[class diagram]], the <code>Client</code> class refers (1) to the <code>Aggregate</code> interface for creating an <code>Iterator</code> object (<code>createIterator()</code>) and (2) to the <code>Iterator</code> interface for traversing an <code>Aggregate</code> object (<code>next(),hasNext()</code>).
The <code>Iterator1</code> class implements the <code>Iterator</code> interface by accessing the <code>Aggregate1</code> class.

The [[UML]] [[sequence diagram]]
shows the run-time interactions: The <code>Client</code> object calls <code>createIterator()</code> on an <code>Aggregate1</code> object, which creates an <code>Iterator1</code> object and returns it
to the <code>Client</code>.
The <code>Client</code> uses then <code>Iterator1</code> to traverse the elements of the <code>Aggregate1</code> object.

=== UML class diagram ===
[[Image:Iterator UML class diagram.svg|thumb|center|500px|The iterator pattern]]

== Example ==
{{main|Iterator}}
Some languages standardize syntax. C++ and Python are notable examples.
<!-- READ NOTE BELOW BEFORE ADDING EXAMPLES
Wikipedia is not a list of examples. Do not add examples from your favorite programming language here; this page exists to explain the design pattern, not to show how it interacts with subtleties of every language extant. Feel free to add examples here: http://en.wikibooks.org/wiki/Computer_Science_Design_Patterns/Iterator
-->
=== C++ ===
[[C++]] implements iterators with the semantics of [[pointer (computer programming)|pointer]]s in that language. In C++, a class can overload all of the pointer operations, so an iterator can be implemented that acts more or less like a pointer, complete with dereference, increment, and decrement. This has the advantage that C++ algorithms such as <code>std::sort</code> can immediately be applied to plain old memory buffers, and that there is no new syntax to learn. However, it requires an "end" iterator to test for equality, rather than allowing an iterator to know that it has reached the end. In C++ language, we say that an iterator models the iterator [[concept (generic programming)|concept]].

This C++11 implementation is based on chapter "Generalizing vector yet again".<ref>{{cite book |author=Bjarne Stroustrup |title=Programming: Principles and Practice using C++ |edition=2 |publisher=Addison Wesley |year=2014 |isbn=978-0-321-99278-9 |pages=729 ff.}}</ref>

<syntaxhighlight lang="c++">
#include <iostream>
#include <stdexcept>
#include <initializer_list>
		
class Vector {
public:
  using iterator = double*;
  iterator begin() { return elem; }
  iterator end() { return elem + sz; }
  
  Vector(std::initializer_list<double> lst) :elem(nullptr), sz(0) {
    sz = lst.size();
    elem = new double[sz];
    double* p = elem;
    for (auto i = lst.begin(); i != lst.end(); ++i, ++p) {
      *p = *i;
    }
  }  
  ~Vector() { delete[] elem; }
  int size() const { return sz; }
  double& operator[](int n) {
    if (n < 0 || n >= sz) throw std::out_of_range("Vector::operator[]");
    return elem[n];
  }
  Vector(const Vector&) = delete; // rule of three
  Vector& operator=(const Vector&) = delete;
private:
  double* elem;
  int sz;
};

int main() {
  Vector v = {1.1*1.1, 2.2*2.2};
  
  for (const auto& x : v) {
    std::cout << x << '\n';
  }
  for (auto i = v.begin(); i != v.end(); ++i) {
    std::cout << *i << '\n';
  }
  for (auto i = 0; i <= v.size(); ++i) {
    std::cout << v[i] << '\n';
  } 
}
</syntaxhighlight>

The program output is

<syntaxhighlight lang="c++">
1.21
4.84
1.21
4.84
1.21
4.84
terminate called after throwing an instance of 'std::out_of_range'
  what():  Vector::operator[]
</syntaxhighlight>

== See also ==
* [[Composite pattern]]
* [[Container (data structure)]]
* [[Design pattern (computer science)]]
* [[Iterator]]
* [[Observer pattern]]

==References==
{{reflist}}

== External links ==
{{wikibooks|Computer Science Design Patterns|Iterator|Iterator implementations in various languages}}
* [http://us3.php.net/manual/en/language.oop5.iterations.php Object iteration] in PHP
* [http://www.dofactory.com/Patterns/PatternIterator.aspx Iterator Pattern] in C#
* [https://web.archive.org/web/20160303172550/http://www.lepus.org.uk/ref/companion/Iterator.xml Iterator pattern in UML and in LePUS3 (a formal modelling language)]
* [http://sourcemaking.com/design_patterns/iterator SourceMaking tutorial]
* [https://web.archive.org/web/20150520003129/http://www.patterns.pl/iterator.html Design Patterns implementation examples tutorial]
* [http://c2.com/cgi/wiki?IteratorPattern Iterator Pattern]

{{Design Patterns Patterns}}

<!--Categories-->
[[Category:Articles with example C++ code]]
[[Category:Articles with example C Sharp code]]
[[Category:Articles with example JavaScript code]]
[[Category:Articles with example Perl code]]
[[Category:Articles with example PHP code]]
[[Category:Iteration in programming]]
[[Category:Software design patterns]]