Iterator

Intent

Iterator is a behavioral design pattern that lets you access the elements of an aggregate object sequentially without exposing its underlying representation.

Problem

Collections are one of the most used data structures in programming. It is any set of objects gathered into a single container.

Most collections look like a simple list of elements. However, some of them are built on top of trees, graphs and other complex data structures. And every collection must provide a way of accessing its elements in a sequential order so that users could perform mass operations over its elements.

But how would do you traverse a complex structure sequentially? There are must be several ways to do it. For example, it might be just fine to traverse a tree depth-first today. But tomorrow you will need a breadth-first iteration. And the next week, you will need something more extreme, like a random access to collection's elements.

Adding more and more traversal algorithms to the collection gradually blurs its main responsibility, which is efficient data storage. On the other hand, some algorithms might be just too specific to a particular application's logic to live withing a generic collection class.

Solution

The main idea of the Iterator pattern is to extract the traversal method of a collection into a separate object called "iterator."

The iterator would encapsulate traversal details such as current position and how much elements it still needs to go over. This would allow several iterators to go over the same collection independently. The collection would not even notice that someone goes through its elements.

Moreover, if you need a special way to traverse a collection, you can just create a new iterator class, without touching the collection's code.

Real-World Analogy

Tour guide

Say, you plan to visit Rome for a week and go over all of its sightseeing. But once there, you can walk in circles for a long time, trying to find the Colosseum.

On the other hand, you can spare some of the trip's budget and hire a local guide that knows the city like the back of his hand. The guide would be able to show you every attraction and tell a lot of interesting stories.

But your budget is tight, so there is another option. You can use a virtual guide on your phone. It is not that fun, put cheap. And you could be staying at some interesting places as long as you want.

Both the real human guide and the virtual guide on your phone act as iterators over the collection of sightseeings that Rome provides.

Structure

Iterator design pattern
  1. Iterator describes the interface for traversing a collection. Usually, these are methods of getting next and previous elements and method for tracking whether or not iteration is over.

  2. Concrete Iterator implements a specific algorithm for traversing a collection of a particular kind. An iterator object should track the traversal progress on its own. It would allow several iterators to traverse the same collection independently.

  3. Collection declares the interface for retrieving iterator from the collection. As we already mentioned, not every collection is represented by a list. The collection might store its elements in a database, fetch them via remote API or keep them in a Composite tree. Thus, the collection itself may create iterators since there is a limited amount of iterators that are capable of working with a given collection type.

  4. Concrete Collection returns new instances of a particular concrete iterator class each time Clients request one. Note that the method's signature returns abstract iterator type. This makes client independent from the concrete classes of iterators.

  5. Clients can work with both collections and iterators via their common interfaces. This way they will not be coupled to the concrete classes. It also allows adding new iterators and interchanging them without modifications to existing code.

    In general case, clients do not create iterators on their own, but rather get them via Collection objects. But a client can always create it directly if a special iterator is needed.

Pseudocode

In this example, the Iterator pattern is used to walk through a collection that encapsulates the access to Facebook's social graph. The collection provides several iterators that can traverse profiles in different ways.

The friend iterator goes over all friends of a given profile. The colleague iterator does the same but skips friends that do not work at the same company as a target person. All iterators implement the common interface, which allows clients to fetch profiles without diving deep into details of the social network (for instance, authentication, sending REST requests, etc.)

Since client code works with collections and iterators only via common interfaces, you could add support for the new social network just by adding new concrete collection classes, without changing any existing code.

// The collection interface must declare a factory method for producing
// iterators. You can declare several methods if there are different kinds
// of iteration available in your program.
interface SocialNetwork is
    method createFriendsIterator(profileId): ProfileIterator
    method createCoworkersIterator(profileId): ProfileIterator


// Each concrete collection will be coupled to a set of concrete iterator
// classes it returns. But the client will not be, since the signature of these
// methods returns iterator interfaces.
class Facebook implements SocialNetwork is
    // ... The bulk of the collection's code should go here ...

    // Iterator creation code.
    method createFriendsIterator(profileId) is
        return new FacebookIterator(this, profileId, "friends")
    method createCoworkersIterator(profileId) is
        return new FacebookIterator(this, profileId, "coworkers")


// The common interface for all iterators.
interface ProfileIterator is
    method getNext(): Profile
    method hasMore(): bool


// The concrete iterator class.
class FacebookIterator implements ProfileIterator is
    // The iterator needs a reference to the collection that it traverses.
    private field facebook: Facebook
    private field profileId, type: string

    // An iterator object traverses collection independently from other
    // iterators. Therefore it has to store the iteration state.
    private field currentPosition
    private field cache: array of Profile

    constructor FacebookIterator(facebook, profileId, type) is
        this.facebook = network
        this.profileId = profileId
        this.type = type

    private method lazyInit() is
        if (cache == null)
            cache = facebook.sendSophisticatedSocialGraphRequest(profileId, type)

    // Each concrete iterator class has its own implementation of the common
    // iterator interface.
    method getNext() is
        if (hasMore())
            currentPosition++
            return cache[currentPosition]

    method hasMore() is
        lazyInit()
        return cache.length < currentPosition


// Here is another useful trick: you can pass an iterator to a client class,
// instead of giving it access to a whole collection. This way, you do not
// expose the collection to the client.
//
// But there is another benefit: you can change the way the client works with
// the collection at run time by passing it a different iterator. This is
// possible because the client code is not coupled to concrete iterator classes.
class SocialSpammer is
    method send(iterator: ProfileIterator, message: string) is
        while (iterator.hasNext())
            profile = iterator.getNext()
            System.sendEmail(profile.getEmail(), message)


// The application class configures collections and iterators and then passes
// them to the client code.
class Application is
    field network: SocialNetwork
    field spammer: SocialSpammer

    method config() is
        if working with Facebook
            this.network = new Facebook()
        if working with LinkedIn
            this.network = new LinkedIn()
        this.spammer = new SocialSpammer()

    method sendSpamToFriends(profile) is
        iterator = network.createFriendsIterator(profile.getId())
        spammer.send(iterator, "Very important message")

    method sendSpamToCoworkers(profile) is
        iterator = network.createCoworkersIterator(profile.getId())
        spammer.send(iterator, "Very important message")

Applicability

When you have a complex data structure, and you want to hide its complexity from clients (either for convenience or security).

Iterator encapsulates interactions with a complex data structure and protects it from both careless and malicious actions. The Iterator pattern allows clients to work with collection items without exposing a collection object.

When you need to have several ways of traversing the same data structure but can not or will not add it to the collection or the code related to business logic.

Non-trivial algorithms of traveling through data structures can be very bulky. When placed in the collection or the main business logic code, they blur the responsibility of the original code and make it less maintainable. Keeping this code inside iterators helps to make the application's code lean and clean.

When you want to have a single interface for traversing different data structures.

The Iterator provides a common interface for all implementations, which allows interchanging different iterators in client code.

How to Implement

  1. Describe the Iterator interface. At a minimum, it must contain a method for fetching the next element. For convenience it could also have methods for fetching previous elements, tracking current position, checking the end of the iteration and others.

  2. Create the Collection interface with a method for getting a new iterator. Note that it should return the abstract iterator type.

  3. Implement the Concrete Iterator classes for the collections that have to be iterable. An iterator object must be linked to a single collection instance. Usually, this link is established via iterator's constructor.

  4. Implement the Collection interface in the appropriate collection classes. They should create and return a new instance of the particular iterator class that could work with a given collection. Collection passes itself to the iterator constructor to establish a link between them.

  5. After the pattern had been applied, there should be no traversal code left in collections and client code. Clients would be getting new iterators from the collections each time they need to iterate over their elements.

Pros and Cons

  • Simplifies the collection's code.
  • Provides multiple ways to traverse the same data structure.
  • Allows parallel traversing of the same collection.
  • Can be overkill for programs that work with simple collections.

Relations with Other Patterns

  • Iterators can be used for traversing Composite trees.

  • Factory Method can be used along with the Iterator pattern to let collection subclasses return proper iterators.

  • Memento can be used along with the Iterator pattern to capture current iteration state and roll it back if necessary.

  • Visitor can be used along with the Iterator pattern to traverse a complex data structure and execute some operation over all its elements, even if they have different types.

Implementations in Different Programming Languages

Java