Iterator pattern
In object-oriented programming, the iterator pattern is a design pattern in which an iterator is used to traverse a container and access the container's elements. The iterator pattern decouples algorithms 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.
Overview
The Iterator [1] design pattern is one of the 23 well-known "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?
- 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.
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.".[3]
Structure
UML class and sequence diagram
In the above UML class diagram, the Client
class refers (1) to the Aggregate
interface for creating an Iterator
object (createIterator()
) and (2) to the Iterator
interface for traversing an Aggregate
object (next(),hasNext()
).
The Iterator1
class implements the Iterator
interface by accessing the Aggregate1
class.
The UML sequence diagram
shows the run-time interactions: The Client
object calls createIterator()
on an Aggregate1
object, which creates an Iterator1
object and returns it
to the Client
.
The Client
uses then Iterator1
to traverse the elements of the Aggregate1
object.
UML class diagram
Example
Some languages standardize syntax. C++ and Python are notable examples.
C++
C++ implements iterators with the semantics of pointers 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 std::sort
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.
This C++11 implementation is based on chapter "Generalizing vector yet again".[5]
#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';
}
}
The program output is
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[]
See also
- Composite pattern
- Container (data structure)
- Design pattern (computer science)
- Iterator
- Observer pattern
References
- ^ Erich Gamma; Richard Helm; Ralph Johnson; John Vlissides (1994). Design Patterns: Elements of Reusable Object-Oriented Software. Addison Wesley. pp. 257ff. ISBN 0-201-63361-2.
- ^ "The Iterator design pattern - Problem, Solution, and Applicability". w3sDesign.com. Retrieved 2017-08-12.
- ^ Gang Of Four
- ^ "The Iterator design pattern - Structure and Collaboration". w3sDesign.com. Retrieved 2017-08-12.
- ^ Bjarne Stroustrup (2014). Programming: Principles and Practice using C++ (2 ed.). Addison Wesley. pp. 729 ff. ISBN 978-0-321-99278-9.