Iterators and Ranges in Algorithms

When you write an algorithm, you usually want it to work on a group of values rather than on one value at a time. Before you can design that algorithm, you need a precise answer to a simple question: exactly which group of values will the algorithm work on? In this part of the course, the answer is the sequence. A sequence is the unit an algorithm is applied to. Understanding how it relates to the containers that hold data is the first step toward writing algorithms that work across many different kinds of storage.

Keep that question in mind as you read. By the end of this article you should be able to look at two positions, say a starting point and a stopping point, and state exactly which values an algorithm would see.

Picture a row of five values stored in positions 0 through 4. Suppose we pick a begin position of 1 and an end position of 4. The sequence those two positions describe starts at the value in position 1 and runs up to, but does not include, the value in position 4. The diagram below marks the values that fall inside that stretch.

Read the diagram from left to right. Position 0 is before the sequence, so A is not part of it. Positions 1, 2 and 3 are covered, so B, C and D form the sequence. Position 4 is the end position, and E is excluded. The sequence therefore contains exactly three values, even though the two boundary positions are 1 and 4.

The square bracket on the left of $[\text{begin} : \text{end})$ means the begin position is included. The round bracket on the right means the end position is excluded. Mathematicians call this a half-open range, because one end is closed and the other is open. The notation is a compact way of saying exactly which positions belong to the sequence, and nothing else is needed to describe it.

Because a sequence is described only by its two boundaries, the definition does not depend on how the values are stored. The source calls this a general and flexible definition. Two positions are all you need to hand to an algorithm.

The two ideas are easy to blur together, because in practice a container and its contents are usually handled as one thing. Separating them makes clear what each one does. A container is the holder of contents. It is where the data lives. A sequence is a definition of which of those contents an algorithm should consider, given by a pair of iterators.

Notice the direction of the relationship. The sequence is not a second copy of the data. It is a way of naming a stretch of it. The container supplies the values, and the iterator pair tells the algorithm which ones to process. This is why algorithms are most often applied to sequences that are the contents of a container.

The sequence is the more general idea. It does not require any particular container, but in practice it is most often used with one. Because the algorithm receives only the two boundaries, the same algorithm can be pointed at different containers, or at only part of one, simply by changing the pair of positions it is given.

The same procedure works for any pair of positions. Count from begin upward, stop before end, and the covered positions are exactly the ones you collected. The number of values is the distance between the two boundaries, because the end position is never counted.

What happens when the begin and end positions are the same? Using the definition, the sequence includes everything from begin up to but not including end. If both point to the same position, there is no position that is both at or after begin and before end. The sequence therefore contains no values.

In the diagram, none of the values are highlighted, because the sequence starts and stops at the same boundary. It is still a valid sequence; it simply has length zero. This is a useful case to recognize, because an algorithm given an empty range has nothing to process and should be written to handle that cleanly.