Iterator

complexitypopularity

Move the job of walking a collection out of the collection and into a separate object, so clients traverse anything without learning how it is stored.

Real-world analogy

Three ways to see Rome

You can wander Rome on instinct and spend the afternoon failing to find the Colosseum. You can buy a navigation app and stop wherever you please. Or you can hire a local guide who tailors the route, tells better stories, and costs considerably more. Rome does not change. What changes is the thing walking you through it - and that thing is an iterator.

The problem

A collection is a container for a group of objects, and whatever it is built on - list, stack, tree, graph, a REST API pretending to be a graph - it has to let other code reach the elements, once each.

Over a list that is a for-loop. Over a tree it is a question: depth-first today, breadth-first next week, something bespoke the week after. Pile all of those into the collection class and you have blurred its actual responsibility, which is storing data efficiently. Some of those walks are application-specific anyway and have no business living in a general-purpose container.

Meanwhile the client code usually does not care how anything is stored - but since every collection exposes access differently, it ends up coupled to concrete collection classes regardless.

The solution

Move the traversal behavior into a separate object: the iterator. Besides the walking algorithm, it holds all the bookkeeping - where you are, how much is left, any cached page of results. Because that state belongs to the iterator rather than the collection, several iterators can crawl the same collection simultaneously without interfering.

An iterator typically offers one primary method for fetching the next element; the client keeps calling until there is nothing left. All iterators implement the same interface, so client code works with any collection and any traversal for which an iterator exists. Need a special walk? Write one iterator class. The collection and the client stay untouched.

1. 1The app asks the collection for an iterator. The collection picks the concrete class; the app only sees the interface type.
2. 2The iterator gets a reference back to the collection it will traverse, plus the parameters that define this particular walk.
3. 3The client is handed the iterator, not the network. It can walk profiles and do nothing else - and it never learns which social network this is.
4. 4The client drives the loop with two questions and no knowledge of how profiles are fetched.
5. 5First call only: the iterator lazily fetches and caches the page of profiles. Authentication, REST, paging - all of it hides here.
6. 6The iterator advances its own position and returns a profile. That position belongs to the iterator, so a second iterator over the same profile is unaffected.
7. 7Loop until hasMore() says stop. Swap in the friends iterator tomorrow and this client code does not change a character.

Structure

Note the collection interface: it declares methods that return iterators, and their return type is the iterator interface. That is a Factory Method doing quiet work, and it is why a concrete collection can hand back whichever concrete iterator it wants without anyone downstream noticing.

implementsusescreates

Code

Same example three ways: walking profiles in a social graph, friends or coworkers, over whichever network is configured.

// The traversal logic lives in the client, welded to one collection.

class SocialSpammer is

method sendToCoworkers(facebook, profileId, message) is

// The client now knows about auth, REST, paging, and the

// shape of Facebook's response. None of that is its job.

token = facebook.authenticate()

page = 0

while (true)

profiles = facebook.get("/friends/" + profileId, token, page)

if (profiles.isEmpty())

break

foreach (p in profiles)

if (p.company == getCompany(profileId))

system.sendEmail(p.email, message)

page++

 

// Need the same walk over LinkedIn? Write it all again.

// Need friends instead of coworkers? Copy and tweak the filter.

// The client knows two methods and nothing else.

class SocialSpammer is

method send(iterator: ProfileIterator, message: string) is

while (iterator.hasMore())

profile = iterator.getNext()

System.sendEmail(profile.getEmail(), message)

 

// Which network, which walk, which order - all decided elsewhere:

spammer.send(facebook.createCoworkersIterator(id), "...")

spammer.send(linkedIn.createFriendsIterator(id), "...")

 

// A new social network is a new collection plus a new iterator.

// This client does not change.

// The collection interface declares factory methods for iterators.

// Several methods means several kinds of walk over the same data.

interface SocialNetwork is

method createFriendsIterator(profileId):ProfileIterator

method createCoworkersIterator(profileId):ProfileIterator

 

// A concrete collection is coupled to its concrete iterators - but

// the client is not, because these methods are typed by the interface.

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")

 

 

// Two methods are the entire contract every iterator must honor.

interface ProfileIterator is

method getNext():Profile

method hasMore():bool

 

 

class FacebookIterator implements ProfileIterator is

// The iterator needs a way back to the collection it walks.

private field facebook: Facebook

private field profileId, type: string

 

// Traversal state lives HERE, not in the collection. That is why

// two iterators over the same profile do not trip over each other.

private field currentPosition

private field cache: array of Profile

 

constructor FacebookIterator(facebook, profileId, type) is

this.facebook = facebook

this.profileId = profileId

this.type = type

 

// Fetch on first use, not on construction.

private method lazyInit() is

if (cache == null)

cache = facebook.socialGraphRequest(profileId, type)

 

// Each concrete iterator brings its own traversal algorithm.

method getNext() is

if (hasMore())

currentPosition++

return cache[currentPosition]

 

method hasMore() is

lazyInit()

return currentPosition < cache.length

 

 

// Handing a client an iterator instead of the collection is the quiet

// superpower here: the client can traverse but cannot reach in, and

// you can change how it traverses by passing a different iterator.

class SocialSpammer is

method send(iterator: ProfileIterator, message: string) is

while (iterator.hasMore())

profile = iterator.getNext()

System.sendEmail(profile.getEmail(), message)

 

// The application picks the collection and the walk, then steps back.

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")

When to use it

• The collection has a complicated structure underneath and you want clients spared the details, for convenience or to keep careless code from mangling it.
• The same bulky traversal logic is being retyped across your app. Move it into iterators and both the client and the collection get leaner.
• Client code must handle several data structures, or structures you cannot name yet. Two interfaces - collection and iterator - are all it has to know.

Pitfalls

• Overkill on simple data. If your collections are lists and your traversals are for-loops, an iterator hierarchy adds classes and subtracts clarity.
• A tax on performance. Going through an iterator is usually slower than indexing a specialized collection directly. Usually irrelevant, occasionally decisive.
• Mutation during iteration. The collection can change under an iterator's feet. Real libraries answer this with fail-fast errors or snapshot semantics; decide which one you are promising before someone finds out the hard way.
• Off-by-one in the cursor. Whether the position starts before the first element or on it decides what hasMore() must compare. Getting it backwards silently drops or repeats an element.

Don't confuse it with

• Composite. Composite gives you the tree, Iterator gives you the walk. A leaf-to-root or root-to-leaf traversal over a Composite is the textbook use.
• Factory Method. Not a rival - a component. createIterator() is a factory method, which is how collection subclasses return iterators matched to themselves.
• Visitor. Iterator controls the order of arrival; Visitor controls what you do on arrival. Combine them to run an operation over a heterogeneous structure.
• Memento. Pair them to snapshot an iteration's position and roll back to it later.
• Language-level iterators. Python's __iter__, Java's Iterable, C#'s IEnumerable are this pattern baked into the runtime. You have been using it for years; this is just the name for it.

Check yourself

Question 1 of 5

Where does the traversal state - current position, what is left - actually live?