Skip to content
a Programmer

Iterator Design Pattern (Behavioral)

Intent

Section titled “Intent”

Iterator is a behavioral design pattern that lets you traverse elements of a collection without exposing its underlying representation (list, stack, tree, etc.).

Problem

Section titled “Problem”

Collections are one of the most common data structures in programming. However, a collection is just a container for a group of objects. Most collections store their elements in simple lists, but some are based on stacks, trees, graphs, and other complex structures.

Regardless of 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 seem 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. Adding more and more traversal algorithms to the collection gradually blurs its primary responsibility, which is efficient data storage.

Solution

Section titled “Solution”

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

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.

All iterators must implement the same interface. This makes the client code compatible with any collection type or any traversal algorithm as long as there’s a proper iterator.

Real-World Analogy

Section titled “Real-World Analogy”

You plan to visit Rome for a few days and visit all the main sights and attractions. But once there, you could waste a lot of time walking in circles, unable to find even the Colosseum.

Instead, you could buy a virtual guide app for your smartphone and use it for navigation. It’s smart and inexpensive, and you could stay at a sight as long as you want. Alternatively, you could spend some of the budget and hire a local guide who knows the city like the back of their hand. The guide would be your iterator. You can choose whichever “iterator” you prefer (app, human, or map) to traverse the city’s sights.

Structure

Section titled “Structure”
  1. Iterator Interface declares the operations required for traversing a collection: fetching the next element, retrieving the current position, restarting iteration, etc..
  2. Concrete Iterators implement specific algorithms for traversing a collection. The iterator object should track the traversal progress on its own.
  3. Collection Interface declares one or multiple methods for getting iterators compatible with the collection.
  4. Concrete Collections return new instances of a particular concrete iterator class each time the client requests one.
  5. Client works with both collections and iterators via their interfaces. This way the client isn’t coupled to concrete classes, allowing you to use various collections and iterators with the same client code.

Structure (Class Diagram)

Section titled “Structure (Class Diagram)”
classDiagram
    class IterableCollection {
        <<interface>>
        +createIterator() Iterator
    }
    class ConcreteCollection {
        +createIterator() Iterator
    }
    class Iterator {
        <<interface>>
        +getNext()
        +hasMore() bool
    }
    class ConcreteIterator {
        -collection: ConcreteCollection
        -iterationState
        +getNext()
        +hasMore() bool
    }

    IterableCollection <|-- ConcreteCollection
    Iterator <|-- ConcreteIterator
    ConcreteCollection ..> ConcreteIterator : creates
    ConcreteIterator o-- ConcreteCollection

Pseudocode

Section titled “Pseudocode”
# The collection interface must declare a factory method for
# producing iterators.
interface SocialNetwork:
    method createFriendsIterator(profileId): Iterator
    method createCoworkersIterator(profileId): Iterator


# Each concrete collection is coupled to a set of concrete
# iterator classes it returns.
class Facebook implements SocialNetwork:
    method createFriendsIterator(profileId):
        return new FacebookIterator(this, profileId, "friends")
    method createCoworkersIterator(profileId):
        return new FacebookIterator(this, profileId, "coworkers")


# The common interface for all iterators.
interface Iterator:
    method getNext(): Profile
    method hasMore(): boolean


# The concrete iterator class.
class FacebookIterator implements Iterator:
    private field facebook: Facebook
    private field profileId, type: string
    private field currentPosition = 0
    private field cache: array of Profile


    constructor FacebookIterator(facebook, profileId, type):
        this.facebook = facebook
        this.profileId = profileId
        this.type = type


    private method lazyInit():
        if (cache == null):
            cache = facebook.socialGraphRequest(profileId, type)


    method getNext():
        if (hasMore()):
            currentPosition++
            return cache[currentPosition]


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

Applicability

Section titled “Applicability”
  • Hide Complex Internal Structures: Use the Iterator pattern when your collection has a complex data structure under the hood, but you want to hide its complexity from clients (for convenience or security).
  • Reduce Code Duplication: Use the pattern to reduce duplication of the traversal code across your app.
  • Uniform Traversal: Use the Iterator when you want your code to be able to traverse different data structures or when types of these structures are unknown beforehand.

How to Implement

Section titled “How to Implement”
  1. Declare the iterator interface.
  2. Declare the collection interface and describe a method for fetching iterators.
  3. Implement concrete iterator classes for the collections that you want to be able to traverse with iterators.
  4. Implement the collection interface in your collection classes.
  5. Go over the client code to replace all of the collection traversal code with the use of iterators.

Pros and Cons

Section titled “Pros and Cons”

Pros:

  • Single Responsibility Principle: You can clean up the client code and the collections by extracting bulky traversal algorithms into separate classes.
  • Open/Closed Principle: You can implement new types of collections and iterators and pass them to existing code without breaking anything.
  • You can iterate over the same collection in parallel because each iterator object contains its own iteration state.
  • You can delay an iteration and continue it when needed.

Cons:

  • Applying the pattern can be an overkill if your app only works with simple collections.
  • Using an iterator might be less efficient than going through elements of some specialized collections directly.

Relations with other Design Patterns

Section titled “Relations with other Design Patterns”
  • You can use Iterators to traverse Composite trees.
  • You can use Factory Method along with Iterator to let collection subclasses return different types of iterators that are compatible with the collections.
  • You can use Memento along with Iterator to capture the current iteration state and roll it back if necessary.
  • Visitor can be used along with Iterator to traverse a complex data structure and execute some operation over its elements, even if they all have different classes.

Code Examples

Section titled “Code Examples”

Code Examples (C#)

Section titled “Code Examples (C#)”
// Iterator
public interface IIterator<T>
{
    bool HasNext();
    T Next();
}


// Aggregate
public interface IAggregate<T>
{
    IIterator<T> CreateIterator();
}


// Concrete Aggregate
public class NumberCollection : IAggregate<int>
{
    private readonly List<int> _numbers = new();


    public void Add(int number) => _numbers.Add(number);


    public IIterator<int> CreateIterator()
        => new NumberIterator(_numbers);
}


// Concrete Iterator
public class NumberIterator : IIterator<int>
{
    private readonly List<int> _numbers;
    private int _position = 0;


    public NumberIterator(List<int> numbers)
    {
        _numbers = numbers;
    }


    public bool HasNext() => _position < _numbers.Count;


    public int Next() => _numbers[_position++];
}


// Usage
class Program
{
    static void Main()
    {
        var collection = new NumberCollection();
        collection.Add(10);
        collection.Add(20);
        collection.Add(30);


        var iterator = collection.CreateIterator();


        while (iterator.HasNext())
            Console.WriteLine(iterator.Next());
    }
}