What is the iterator design pattern? The iterator behavioral pattern allows you to access objects in a collection or anything that contains multiple items without worrying about how this is done. Your code works with the iterator in a uniform manner through an interface with methods such as first, next, current, and isDone.
It works by defining an interface for your collection types to implement that defines a factory method to return an iterator. The collection is sometimes referred to as an aggregate because it bundles multiple objects. The iterator will actually be a concrete implementation of another interface for iterators. Your code will work with the collection interface in a uniform manner to create iterators of the correct type for the collection.
The full sequence of methods you’ll need to call is:
- first to get things going.
- isDone to check if the aggregate even has items at all.
- current to get the actual first item in the aggregate.
- next to move to the next item.
- isDone needs to be called each time you move to the next item because there may not be a next item.
- Assuming we’re not yet done, call current to get the item and repeat the process by going back to step 4 and calling next again.
Also make sure to listen to episodes 45 and 46 where I explained the way iterators are implemented in the C++ Standard Library. I recommend that if you need to implement iterators in you classes, that you should follow the way C++ defines them with begin and end methods.
If you’d like to read the book that describes this pattern along with diagrams and sample code, then you can find Design Patterns at the Resources page. You can find all my favorite books and resources at this page to help you create better software designs.
You can also read the full transcript of this episode below.
Transcript
The basic description says that this pattern provides a way to access the elements of an aggregate one at a time without exposing how this is done. I actually thought about skipping this pattern because I already explained C++ iterators in detail in episodes 45 and 46. But then I realized that this episode is still valuable to you because the concepts I’ll explain here aren’t limited to just C++. Sure, I think C++ iterators are an excellent example to follow and I encourage you, if you’re implementing your own iterators, to follow how they were designed in the C++ Standard Library. I’ll describe iterators here as they were first described by the Gang of Four.
Here’s the problem this pattern solves.
Let’s say you have an object that either contains other objects like a collection or is made up of various parts. This container of other objects is called an aggregate. Either way, you want to start with the first object, move to the second, then move to the third, etc. until you reach the end. This is called enumerating the objects. You’ll need some way to tell when you reach the end. And who knows, you might even reach the end right away if your aggregate is empty.
There’s some other important scenarios to consider also. Maybe you sometimes want to move through the items not just one after the other but following some pattern or search criteria. Maybe you only want to look at every third item. Or you only want to enumerate the red objects.
And another scenario is that you sometimes need multiple object enumerations going on at the same time in the same aggregate.
If the aggregate supports adding or removing objects, then it’s already going to have methods to add an item, remove an item, and maybe count the number of items. Adding more methods to return the first item, return the current item, return the next item, and determine if all the items have been returned yet just adds more methods to the aggregate. And these extra methods don’t solve the problem of search criteria. Do you really want methods to get the first red item, get the next red item, etc.? And these extra methods don’t solve the problem of needing multiple enumerations.
And on top of all this, adding methods like this will tie your code to that particular type of aggregate.
I’ll explain how to solve all this right after this message from our sponsor.
( Message from Sponsor )
The first step that this pattern describes is to create a class that knows how to advance from one object to the next.
This is called the iterator.
And actually, because there can be different types of aggregates that each need different navigation strategies we’re going to need multiple iterator types too. In order to restore order to the design, each of the iterators should follow the same interface. This means there will be a common interface for all iterators to follow. This interface should define methods such as first, next, current, and isDone.
- Calling the first method prepares the iterator by moving it to the first item in the aggregate. It may not actually return the first item though.
- That’s the job of the current method. This means that before you call current, you should get things setup by calling the first method first.
- To move to the next item, just call next. Again, to actually get the item that the iterator now refers to, you’ll need to call the current method again.
And to tell when you’re done, you call the isDone method.
The full sequence of methods you’ll need to call is:
- first to get things going.
- isDone to check if the aggregate even has items at all.
- current to get the actual first item in the aggregate.
- next to move to the next item.
- isDone needs to be called each time you move to the next item because there may not be a next item.
- Assuming we’re not yet done, call current to get the item and repeat the process by going back to step 4 and calling next again.
Now, once you have these methods defined in a common interface, you can implement concrete classes that follow this pattern and know how to work with an aggregate type and a particular pattern to navigate items.
Each concrete iterator knows how to work with some type of aggregate and may or may not work with a different aggregate type. So you’ll need some way to know which iterators work with which aggregates.
This is where the iterator design pattern helps you again with more guidance. This time, you need an interface that each aggregate can implement. This aggregate interface will define a factory method that creates an iterator. Episode 59 describes factories. The factory method can also make sure the iterator knows about the instance of the aggregate that’s being enumerated.
In order for the iterator to know how to enumerate objects, it may need special access to the data structures in the aggregate. You can either nest the iterator class inside the aggregate class or declare the iterator to be a friend of the aggregate. Either way will provide the iterator access to the data it needs.
What if you want to extend the iterators later like I mentioned at the beginning of this episode?
It’s unreasonable to think that you’ll even want to include all the different enumeration strategies. But if you don’t include them now, then how will they also get access to the private data structures in the aggregate type? The way you do this is to expose access in the iterators to the necessary data through protected access levels. This way, you can later add extra iterator classes that derive from the initial iterator classes and because of the derivation, they’ll have access to the protected areas of the base iterator type and through that, have access to the data in the aggregate.
I’ll end this episode with the following advice. Be careful if you ever need to modify a collection or an aggregate while also enumerating the contents. And by, be careful, I mean don’t do this. This would be like going through a grocery store checkout line and removing an item that’s already been scanned and saying that you no longer want that item. Only with iterators, modifying a collection while you have an active iterator can lead to much worse behavior. There are some iterators that can deal with this but it takes a lot of extra code to manage modifications while enumerating. These are called robust iterators. If in doubt, assume that your iterator can’t handle modifications.