Algorithms Working Through Iterators

Imagine writing a routine that adds up every value in a collection. The arithmetic is the same no matter where the values live. They might sit in a fixed-size block, in a linked chain of nodes, or in a file that is read one item at a time. The adding logic never changes, yet a naive routine can end up tied to one particular storage layout. If it walks through that layout directly, then changing how the data is stored forces a rewrite of the routine, even though the adding logic is untouched.

This article examines the way out of that tangle. Instead of letting the algorithm reach directly into storage, the design places a third party between them. That third party is the iterator. The algorithm works through the iterator, and the container hands the iterator out when it is requested. The rest of this article traces how that handoff works and why it is valuable.

Before looking at the iterator, hold the problem in mind with three concrete storage layouts for the same five values. In a fixed-size block, the values sit side by side and each one is reached by its position. In a linked chain, each value sits in a node that points to the next node, so reaching the third value means following two links. In a file read one item at a time, the values are not all in memory at once; each one is fetched as the reader moves forward.

An iterator is the middle party in this design. The algorithm operates on its data through iterators, and it knows nothing about the container in which the elements are stored. The container does not reach out to the algorithm either. Its only role in this relationship is to supply iterators when someone asks for them. Each side therefore has a narrow contract: the algorithm needs only an iterator, and the container needs only the ability to produce one.

The request between the two parties is named in the source through two calls, begin() and end(). The algorithm asks the container for a starting position and an ending position. The container answers by providing iterators. The algorithm receives those iterators and uses them to move through the elements. The order matters: the algorithm first asks for the start, then asks for the end, and only then begins moving between them.

Notice what is absent from this exchange. No algorithm refers to the container's internal layout, and no container refers to the algorithms that will read it. The container never learns which routine is asking; it simply answers the request with iterators.

Once the algorithm holds the starting and ending iterators, it advances step by step. The iterator at begin() is the first position of the range. The algorithm reads the element at its current position, moves the iterator forward, and checks whether the iterator has reached the ending position. If it has not, the loop repeats. If it has, the algorithm stops. The algorithm never needs to know whether the elements sit in a block, a chain, or a file; it only needs to advance and compare.

The separation runs in two directions, and both directions matter. The algorithm depends on iterators. The container depends only on being able to supply iterators. Because of this, storage and algorithms can change independently. The source describes the result as very general and flexible software.

The reason follows directly from the mechanism. Because each algorithm depends only on iterators, one algorithm can be applied to any container that supplies them. Because each container depends only on supplying iterators, one container can be read by any algorithm that works through them. Changing the storage therefore leaves the algorithm alone, and changing the algorithm leaves the storage alone, as long as the iterator handoff stays the same.

The separation between algorithms and containers is easy to misread. The following misreadings are the ones most worth correcting, because each one hides the actual mechanism.