Common STL Algorithms and Their Inputs

The STL provides algorithms that do useful work on collections of data. Before you can use one well, you need to know what it expects as input. The central idea is simple: an STL algorithm operates on one or more sequences. Rather than being tied to one particular container, the algorithm works on a sequence of elements that it is given.

As you read this article, keep one question in mind: when an algorithm receives a sequence, exactly which elements does it work on? The answer depends on how the sequence is specified, and the specification is what this article is about.

Think of a sequence as a row of positions, each holding one element. An algorithm reads the elements it is given and does its work on them. To follow what happens, imagine a row of five values: 10, 20, 30, 40, 50, numbered by position from 0 to 4. Nothing about the algorithm has been decided yet. The only question is which part of this row it has been handed.

The source describes the relationship between an algorithm and its inputs in general terms: the algorithm does its work on the sequences it is given, and each of those sequences is what it reads from and acts on. The rest of this article shows how a single sequence is marked out so that the algorithm knows where its work begins and ends.

Conventionally these two iterators are named first and last. Written as a range, the input is $[\mathrm{first}, \mathrm{last})$. The square bracket on the left means the first iterator's position is included. The round bracket on the right means the last iterator's position is not included. This asymmetry is the whole meaning of half-open.

In the diagram, first points at the element 20 and last points at the element 50. The algorithm processes 20, 30 and 40. The element at last, which is 50, is not processed. The end iterator marks the boundary of the range, not its final element.

Because the first iterator is included and the last iterator is not, what happens when both iterators point to the same position? The pair describes a range that starts and stops at the same spot. Nothing lies between them that is both at or after first and before last, so the range contains zero elements.

In this diagram both iterators sit on the element 20. The range $[\mathrm{first}, \mathrm{last})$ would need to include position 1 and stop before position 1, which cannot be done. The algorithm therefore receives no elements to work on. Being able to recognize this case matters, because it means the half-open convention handles the empty sequence without any special rule.

Algorithms differ in how many sequences they take. Some work on a single sequence, and others work on more than one. The source states the general rule: an STL algorithm operates on one or more sequences. Each sequence an algorithm receives is described the same way, by its own pair of iterators, so the same reading rules apply to every input.

The diagram shows two sequences, but the same idea applies to a single sequence. What matters is the relationship: the algorithm does its work on the sequences it is given, and each one is read through its own pair of iterators. Adding a second sequence does not change how a single range is read; it adds one more range to be read in the same way.