Iterator

Intent

Provide a way to 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's 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'll need a breadth-first iteration. And the next week, you'll 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 iterate over the same collection independently. The collection wouldn't 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's another option. You can use a virtual guide on your phone. It's 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 pattern structure
  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 defines 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's 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 won't be coupled to the concrete classes. It also allows adding new iterators and interchanging them without modifications to existing code.

    In general case, clients don't 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 don't 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.

// Common collections interface defines factory method for producing iterators.
// Several methods can be defined if you'd like to offer different kinds of
// iteration over the same collection.
interface SocialNetwork is
    method getFriendsIterator(profileId): ProfileIterator
    method getCoworkerIterator(profileId): ProfileIterator

// Each concrete collection should know which type of iterator it should return.
class Facebook implements SocialNetwork is
    // Iterator creation code.
    method getFriendsIterator(profileId) is
        return new FacebookIterator(this, profileId, "friends")
    method getCoworkerIterator(profileId) is
        return new FacebookIterator(this, profileId, "coworkers")
    // Rest of collection's code...


// Common interface for all iterators.
interface ProfileIterator is
    method hasNext(): bool
    method getNext(): Profile

// Concrete iterator.
class FacebookIterator implements ProfileIterator is
    // Iterator needs a reference to the collection which it traverses through.
    field facebook: Facebook
    field profileId, type: string

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

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

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

    // Each concrete iterator has its own implementation of the
    // common interface.
    method hasNext() is
        initIfNeeded()
        return cache.length < currentPosition

    method getNext() is
        if (hasNext())
            currentPosition++;
            return cache[currentPosition]


// Here's another useful trick: you can pass an iterator instead of a collection
// to a client class. This way, you don't expose a collection. But there's
// another benefit: since client works with iterators through the common
// interface, you can change its behavior at run time by passing different
// iterator objects.
class SocialSpammer is
    method send(iterator: ProfileIterator, message: string) is
        while (iterator.hasNext())
            profile = iterator.getNext()
            sendSingle(profile.email, message)

    method sendSingle(email: string, message: string) is
        // Send VERY IMPORTANT MESSAGE to one email address.


// 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() is
        iterator = network.getFriendsIterator(user.profileId)
        spammer.send(iterator)

    method sendSpamToCoworkers() is
        iterator = network.getCoworkerIterator(user.profileId)
        spammer.send(iterator)

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't or won't 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