Image by wirestock on Freepik
The code is available on GitHub here
The Iterator Pattern provides a way to access the elements of a collection (such as a list or array) sequentially without exposing its underlying implementation. It defines an object that encapsulates the iteration over a collection and provides a standard interface for accessing its elements one at a time, using methods like moveNext() and current(). This pattern enables decoupling between the collection and the code that uses it, making it easier to modify both independently.
When to use
Use the Iterator Pattern if you have collections of objects that need to be traversed without exposing the internal structure of the collections.
Usually, when we have a collection (or aggregate) of objects we need to access those elements in order to do various computations. An Iterator gives us a way of accessing those objects sequentially. Also, the Iterator hides the internal structure of the collection from the client that uses the iterator, separating the iteration logic from the structure that holds the objects.
Use the Iterator Pattern if you have similar traversals for various collections in various places in the code.
Using the Iterator Pattern can help you reduce duplicated or similar code that is scattered throughout your codebase.
Use the Iterator Pattern if you want to change the way the elements are iterated over.
For instance, you can implement different iterators for different purposes on the same collection. For example a tree can be traversed with 4 different ways, in-order, pre-order, post-order and level-order. Each traversal could be a different Iterator. You can easily switch between iterators depending on requirements.
How to implement
First, we define the collection of objects that we want to iterate over.
The internal structure of the collection is irrelevant and it can be an array, hashmap, or any other structure.
The second step is to define an Iterator interface for the iterator that will be used to iterate over the collection.
This interface should provide methods for checking if there are more elements to iterate over and retrieving the next element in the collection.
Below we present the Iterator interface with its two methods.
public interface Iterator
{
bool MoveNext();
object Current { get; }
}Each collection will need its implementation of the Iterator that knows how to iterate over its objects. This separates the responsibility of iterating the objects to a separate component, rather than the collection itself. In contrast, if we allowed the collection to take on more responsibilities ( like iteration ), then we would give that class two reasons to change. It could change if the collection changes in some way, and it could also change if the way we iterate changes. In order to avoid many changes happening to a component, we should follow the following principle:
A class should have only one reason to change
The previous statement is also know as Single Responsibility Principle, and the Iterator Pattern guides as towards this.
The collection should implement the Iterable interface, which provides a method to return the appropriate Iterator instance for that collection.
By providing a common interface for collections that can be iterated, we can separate the component responsible for iterating over the elements from the collection itself. This decoupling allows for greater flexibility and reusability of code.
Here is the Iterable interface:
public interface Iterable
{
Iterator CreateIterator();
}The Iterable interface should be implemented by any collection that wants its objects to be iterated.
In the following code snippet, we demonstrate how our custom Collection class implements the Iterable interface by returning a concrete Iterator that can traverse its objects.
public class Collection : Iterable
{
private string[] _items;
public Collection (string[] items){ _items = items; }
// other methods for adding or removing items.
public Iterator CreateIterator()
=> new ConcreteIteratorForItems(_items);
}The concrete Iterator
The responsibility of iterating over the objects in a collection is delegated to a concrete Iterator implementation.
In the following code snippet, we present the implementation of ConcreteIteratorForItems, which has all the necessary logic and responsibility for iterating the objects in an array of strings.
public class ConcreteIteratorForItems : Iterator
{
private string[] _data;
private int _position = -1;
public ConcreteIteratorForItems(string[] data)
{
_data = data;
}
public object Current => _data[_position];
public bool MoveNext()
{
if (_position < _data.Length - 1)
{
_position++;
return true;
}
return false;
}
}The Current property returns the current element in the collection, and the MoveNext() method moves to the next element and returns a boolean value indicating whether there are more elements to traverse. In some cases the Iterator can have a Reset() method which resets the Iterator to the beginning of the collection.
With the Iterator implementation in place, we can now use it as shown below:
Collection collection = new Collection(new[] { "item1", "item2", "item3" });
Iterator iterator = collection.CreateIterator();
while (iterator.MoveNext())
{
Console.WriteLine(iterator.Current);
}The Iterator Pattern class diagram is shown below:
Real World Example
The Iterator Pattern is a widely used design pattern in programming languages, and many core collections in .NET have already integrated it. These collections implement the IEnumerable and IEnumerator interfaces, which provide an easy way to iterate over their elements using a foreach loop.
The IEnumerator interface has methods such as Current and MoveNext(), which allow us to access the current element in the collection and move to the next element, respectively. It also has a Reset() method to reset the iterator and start from the beginning of the collection.
The IEnumerable interface provides the GetEnumerator method, which returns an IEnumerator instance that can be used to iterate over the collection.
// In .NET the Iterator is named IEnumerator
public interface IEnumerator
{
// There could be slightly different interfaces for the Iterator.
// Instead of Next() and HasNext() you can have the following IEnumerator methods
object Current { get; }
bool MoveNext();
// One additional method in case you want to reset the iterator and begin
// the iteration from the first element again.
void Reset();
}
// In .NET the Iterable is named IEnumerable
public interface IEnumerable
{
// The CreateIterator that returns an Iterator is named GetEnumerator() in .NET
IEnumerator GetEnumerator();
}Here are some examples of core collections in .NET that implement the Iterator Pattern:
List<T>
List<T> is a generic collection that provides an ordered, index-based access to elements. It implements the IEnumerable<T> interface, which allows us to iterate over its elements using a foreach loop. Here’s an example:
var list = new List<int> { 1, 2, 3 };
foreach (var item in list)
{
Console.WriteLine(item);
}
Dictionary<TKey, TValue>
Dictionary<TKey, TValue> is a generic collection that provides a key-value mapping. It implements the IEnumerable<KeyValuePair<TKey, TValue>> interface, which allows us to iterate over its elements using a foreach loop. Here’s an example:
var dictionary = new Dictionary<string, int>
{
{ "item1", 1 },
{ "item2", 2 },
{ "item3", 3 }
};
foreach (var item in dictionary)
{
Console.WriteLine(item.Key + ": " + item.Value);
}By implementing the Iterator Pattern, these collections provide a simple and efficient way to iterate over their elements, making our code more readable and concise.
Example 1 – Implementing the Iterator Pattern for a Car Company
In this example, we will create a Dealer component that can print cars from various car companies. Each car company stores its cars in different data structures (lists, arrays, etc.). Currently, we have the list of cars from Ferrari and Ford, but in the future, we may add more companies to the Dealer component.
To make the Dealer component flexible and allow it to iterate over the cars of different companies without knowing the internal structure of each company’s data, we will use the Iterator Pattern.
Each car company provides us with a class that manages their cars. Although each company uses a different approach to store its data, all of them follow the same Iterable protocol. We will use the classes for Ferrari and Ford as shown below:
public class Ferrari : Company
{
private List<Car> _cars;
public Ferrari()
{
_cars = new();
}
public void AddItem(Car car)
{
_cars.Add(car);
}
public void RemoveItem(string name)
{
var item = _cars.FirstOrDefault(x => x.Name == name);
_cars.Remove(item);
}
public override Iterator CreateIterator()
{
return new FerrariIterator(_cars);
}
}
public class Ford : Company
{
private Car[] _cars;
public Ford(Car[] cars)
{
_cars = cars;
}
public override Iterator CreateIterator()
{
return new FordIterator(_cars);
}
}Although Ferrari and Ford use different implementations, they both extend the Company base class:
public abstract class Company : Iterable
{
public abstract Iterator CreateIterator();
}This enables us to easily integrate them as Iterable objects.
Each company provides its own implementation of the Iterator, namely the FerrariIterator and FordIterator:
public class FerrariIterator : Iterator
{
private List<Car> _data;
private int _position = -1;
public FerrariIterator(List<Car> data)
{
_data = data;
}
public bool MoveNext()
{
if (_position < _data.Count - 1)
{
_position++;
return true;
}
return false;
}
public object Current => _data[_position];
}
public class FordIterator : Iterator
{
private Car[] _data;
private int _position = -1;
public FordIterator(Car[] data)
{
_data = data;
}
public bool MoveNext()
{
if (_position < _data.Length - 1)
{
_position++;
return true;
}
return false;
}
public object Current => _data[_position];
}Finally, the Dealer component depends on the Company Iterable object and the Iterator interface. This allows it to be unaware and decoupled from their underlying implementations.
Inside the PrintCars() method, we call the CreateIterator() method for each Company item to obtain the corresponding Iterator implementation. We then use this Iterator to traverse and print each of the objects.
public class Dealer
{
private readonly List<Company> _companies;
public Dealer(params Company[] companies)
{
this._companies = companies.ToList();
}
public void PrintCars()
{
for(int i = 0; i < _companies.Count; i++)
{
PrintCars(_companies[i].CreateIterator());
}
}
private void PrintCars(Iterator.CarCompanyExample.Iterator iterator)
{
while (iterator.MoveNext())
{
Console.WriteLine(iterator.Current);
}
}
}Below we present the class diagram of the solution.
The following code shows how to use the Dealer component:
var ferrari = new Ferrari();
ferrari.AddItem(new Car("Ferrari F40"));
ferrari.AddItem(new Car("Ferrari F355"));
ferrari.AddItem(new Car("Ferrari 250 GTO"));
ferrari.AddItem(new Car("Ferrari 125 S"));
ferrari.AddItem(new Car("Ferrari 488 GTB"));
var ford = new Ford(new Car[]
{
new Car("Ford Model T"),
new Car("Ford GT40"),
new Car("Ford Escort"),
new Car("Ford Focus"),
new Car("Ford Mustang"),
});
var dealer = new Dealer(ferrari, ford);
dealer.PrintCars();This code outputs the names of all cars from the different companies.
Ferrari F40
Ferrari F355
Ferrari 250 GTO
Ferrari 125 S
Ferrari 488 GTB
Ford Model T
Ford GT40
Ford Escort
Ford Focus
Ford MustangThe use of the Iterator Pattern and the Iterator interface in the Dealer component allows for decoupling of its dependencies from their underlying implementations and enables easy integration of new car companies as Iterable objects.
Car company Iterator – Improvement
As we can see both implementations of the Iterator is very similar resulting in a fairly amount of duplicated code. Also, depending on the programming language we should use the already existing implementation of the Iterator Pattern it has. Here we will improve our code using the IEnumerable and IEnumerator interfaces of the .NET.
Using .NET IEnumerable and IEnumerator interfaces
In the Car Company Iterator example, both implementations of the Iterator pattern were found to be very similar, resulting in duplicated code. To avoid this, and depending on the programming language, it’s recommended to use the already existing implementation of the Iterator Pattern provided by the language, such as the IEnumerable and IEnumerator interfaces in .NET.
By using these interfaces, we can discard our own implementation of the Iterator Pattern. To do so, we replace the Iterable interface with the IEnumerable interface, and the Iterator with the IEnumerator interface. As a result, the new Ferrari and Ford components will implement the IEnumerable interface and the GetEnumerator() method, which returns the IEnumerator for each collection.
Below we present the new Ferrari and Ford components:
public class Ferrari : IEnumerable
{
private List<Car> _cars;
public Ferrari()
{
_cars = new();
}
public void AddItem(Car car)
{
_cars.Add(car);
}
public void RemoveItem(string name)
{
var item = _cars.FirstOrDefault(x => x.Name == name);
_cars.Remove(item);
}
public IEnumerator GetEnumerator() => _cars.GetEnumerator();
}
public class Ford : IEnumerable
{
private Car[] _cars;
public Ford(Car[] cars)
{
_cars = cars;
}
public IEnumerator GetEnumerator() => _cars.GetEnumerator();
}In the new code implementation, we can see that the List and the array have already implemented iterators, making the FerrariIterator and FordIterator classes obsolete.
The Dealer component will also be updated to use the IEnumerable and IEnumerator interfaces. The new Dealer class takes in an array of IEnumerable as a parameter and uses a for loop to iterate through each collection, calling the PrintCars() method to print out the cars for each collection.
public class Dealer
{
private readonly List<IEnumerable> _companies;
public Dealer(params IEnumerable[] companies)
{
_companies = companies.ToList();
}
public void PrintCars()
{
for (int i = 0; i < _companies.Count; i++)
{
PrintCars(_companies[i].GetEnumerator());
}
}
private void PrintCars(IEnumerator iterator)
{
while (iterator.MoveNext())
{
Console.WriteLine(iterator.Current);
}
}
}This updated code solution provides the same functionality as the previous implementation, but with less duplicated code, making it easier to maintain and modify. Below is the new class diagram of the improved solution, which shows that the different iterator implementations have been replaced by the default implementations provided by the .NET framework.
Using the <foreach> syntax
To further improve the implementation of the Iterator Pattern, we can make use of the foreach syntax provided by the .NET framework. This syntax simplifies the usage of IEnumerators and provides a cleaner way to iterate over collections.
By using the foreach syntax, we can eliminate the need to explicitly call the GetEnumerator() method. Instead, the foreach loop takes care of this call behind the scenes.
Here is an example of the improved Dealer component using the foreach syntax:
class Dealer
{
private readonly List<IEnumerable> _companies;
public DealerUsingForeach(params IEnumerable[] companies)
{
_companies = companies.ToList();
}
public void PrintCars()
{
for (int i = 0; i < _companies.Count; i++)
{
PrintCars(_companies[i]);
}
}
private void PrintCars(IEnumerable iterable)
{
foreach(var item in iterable)
{
Console.WriteLine(item);
}
}
}Example 2 – Binary Tree Iterator
In this example, we will implement multiple iterators for the same collection, specifically for a tree data structure.
Tree Traversal Iterators
Tree traversal is an essential operation when working with tree data structures. There are different ways to traverse a tree, such as in-order, pre-order, post-order, and level-order traversal. In this post, we will explore each of these traversal methods and provide C# code for implementing them as iterators.
To begin, we define a simple binary tree Node structure in C#. Our binary tree will consist of many Node objects that are linked together. With those objects, we can build a composite object (a binary tree in this case) or a collection of objects that our different iterators will iterate.
public class Node
{
public int Value { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
public Node(int value)
{
Value = value;
}
}Next, we implement our three iterators that will use a Queue to store the traversed nodes. In this example, we traverse all nodes of the tree in the initialization of the iterator and store the ordered nodes in the queue.
BinaryTreeIterator
The BinaryTreeIterator is the base class of all iterators. The only abstract method that the rest of the iterators will implement is the Traverse method, which defines the order the tree nodes are traversed. All the other methods like Reset() and MoveNext() are implemented in the same way in the BinaryTreeIterator base class.
public abstract class BinaryTreeIterator : IEnumerator
{
protected Queue<Node> _queue;
private Node _root;
private object _curr;
public BinaryTreeIterator(Node root)
{
_root = root;
_queue = new();
Traverse(root); // we traverse the nodes and build the queue
}
protected abstract void Traverse(Node node);
public object Current => _curr;
public bool MoveNext()
{
if (_queue.Count > 0)
{
_curr = _queue.Dequeue();
return true;
}
return false;
}
public void Reset()
{
_queue.Clear();
_curr = null;
Traverse(_root);
}
}PreOrderIterator
The PreOrderIterator visits the root node first by adding that node to the queue. Next, it traverses the left subtree first and then the right subtree.
public class PreOrderIterator : BinaryTreeIterator
{
public PreOrderIterator(Node root)
: base(root) { }
protected override void Traverse(Node node)
{
if (node == null) return;
_queue.Enqueue(node);
Traverse(node.Left);
Traverse(node.Right);
}
}InOrderIterator
The InOrderIterator visits the left subtree first, adding the node into the queue, then the root node, and then the right subtree.
public class InOrderIterator : BinaryTreeIterator
{
public InOrderIterator(Node root)
: base(root) { }
protected override void Traverse(Node node)
{
if (node == null) return;
Traverse(node.Left);
_queue.Enqueue(node);
Traverse(node.Right);
}
}PostOrderIterator
Lastly, the PostOrderIterator visits the left subtree first, then the right subtree, and then the root node by adding it to the queue for later retrieval.
public class PostOrderIterator : BinaryTreeIterator
{
public PostOrderIterator(Node root)
: base(root) { }
protected override void Traverse(Node node)
{
if (node == null) return;
Traverse(node.Left);
Traverse(node.Right);
_queue.Enqueue(node);
}
}Usage
To use these iterators, we first create the binary tree the iterators will traverse.
Node root = new(25);
root.Left = new(15);
root.Right = new(50);
root.Left.Left = new(10);
root.Left.Right = new(22);
root.Right.Left = new(35);
root.Right.Right = new(70);
root.Left.Left.Left = new(4);
root.Left.Left.Right = new(12);
root.Left.Right.Left = new(18);
root.Left.Right.Right = new(24);
root.Right.Left.Left = new(31);
root.Right.Left.Right = new(44);
root.Right.Right.Left = new(66);
root.Right.Right.Right = new(90);The final binary tree we build is shown in the image below:
Next, we instantiate the three different iterators, and feed them in a method that takes as a parameter a BinaryTreeIterator. We then iterate through the tree using the specific iterator and store the results in a list.
PreOrderIterator preOrderIterator = new (root);
PostOrderIterator postOrderIterator = new(root);
InOrderIterator inOrderIterator = new(root);
IterateTree(preOrderIterator);
IterateTree(postOrderIterator);
IterateTree(inOrderIterator);
private static void IterateTree(BinaryTreeIterator iterator)
{
var results = new List<object>();
while (iterator.MoveNext())
{
results.Add(iterator.Current);
}
Console.WriteLine($"{iterator.GetType().Name} results: {string.Join(",", results)}");
}Finally, we print the results for each iterator:
PreOrderIterator results: 25,15,10,4,12,22,18,24,50,35,31,44,70,66,90
PostOrderIterator results: 4,12,10,18,24,22,15,31,44,35,66,90,70,50,25
InOrderIterator results: 4,10,12,15,18,22,24,25,31,35,44,50,66,70,90By using these iterators, we can easily traverse a binary tree in different orders and perform operations on each node.
Using Dependency Injection
The various iterators can be registered in a dependency injection container like any other service.
Autofac
C#
var builder = new ContainerBuilder();
// first we register them as the same service with different keys.
builder.RegisterType<PreOrderIterator>().Keyed<BinaryTreeIterator>("pre-order");
builder.RegisterType<InOrderIterator>().Keyed<BinaryTreeIterator>("in-order");
builder.RegisterType<PostOrderIterator>().Keyed<BinaryTreeIterator>("post-order");
// later we can resolve any of them by their key.
var iterator = container.ResolveKeyed<BinaryTreeIterator>("post-order");
// use the iteratorRecommendations
Looking to dive deeper into design patterns and take your programming skills to the next level? Check out the highly recommended books Head First Design Patterns and Design Patterns: Elements of Reusable Object-Oriented Software and start mastering the Iterator pattern today! Grab your copy and level up your coding game.
* This site contains product affiliate links. We may receive a commission if you make a purchase after clicking on one of these links.
