Iterator
Definition
Iterator is a behavioral design pattern that lets you traverse elements of a collection without exposing its underlying representation (list, stack, tree, etc.).
Problem
Most collections store their elements in simple lists. However, some of them are based on stacks, trees, graphs and other complex data structures.
But no matter how a collection is structured, it must provide some way of accessing its elements so that other code can use these elements. There should be a way to go through each element of the collection without accessing the same elements over and over.
This may sound like an easy job if you have a collection based on a list. You just loop over all of the elements. But how do you sequentially traverse elements of a complex data structure, such as a tree? For example, one day you might be just fine with depth-first traversal of a tree. Yet the next day you might require breadth-first traversal. And the next week, you might need something else, like random access to the tree elements.
Solution
The main idea of the Iterator pattern is to extract the traversal behavior of a collection into a separate object
called an iterator.
Iterators implement various traversal algorithms. Several iterator objects can traverse the same collection at the same time.
In addition to implementing the algorithm itself, an iterator object encapsulates all of the traversal details, such as the current position and how many elements are left till the end. Because of this, several iterators can go through the same collection at the same time, independently of each other.
So what is an iterator
An iterator is «not a user-defined collection» but a tool for traversing this collection and not only a collection, but in general everything that can be iterated over sequentially according to some algorithm. Collection traversal is just a special case.
The iteration algorithm is hidden inside the iterator, which allows you to have a separate data object itself and many iterators with different traversal algorithms (SRP).
That is, an iterator is a class that encapsulates what kind of data traversal algorithm with a standardized enumerator interface.
A sequence can be either a ready-made set of objects in memory or it can consist of objects that are created «on the fly» when the iterator is moved (for example, read from a file).
An iterator abstracts from you not only the collection itself, but also the state of its traversal. For example, for an array, this is the current index, for tree-based structures, this is the current node, and so on. Without iterators, you would have to know exactly how to traverse it for each collection and have access to its internal structures (for example, a sorted set based on a tree does not usually expose its nodes to the public).