Sequences and Iterators in the Standard Library

When you first meet the standard library's algorithms, it is natural to assume they behave like methods on the container they touch. If an algorithm is handed a container, you might expect it to be able to shrink it, grow it, or rearrange everything inside it. That expectation comes from experience: most people first learn containers through operations that visibly change them, such as adding an item to the end of a list or removing one from the middle.

The source material corrects this belief directly. Standard library algorithms can change the values of the elements they work on, but no algorithm adds or subtracts elements of a container. As you read the rest of this article, keep that line in mind and test it on the operations you already know.

The standard library provides dozens of algorithms. They are defined in the namespace std and presented in the algorithm header. Each one is a reusable operation that either answers a question about a group of elements or performs a transformation on that group. Instead of writing a loop by hand over the same group, you should prefer the standard algorithm, because the standard library's algorithms tend to be more carefully designed, specified, and implemented than the average loop written from scratch.

The source lists a representative set of algorithms, and each follows the same pattern. A sequence is supplied as input, and the algorithm works over the elements in that range. Find returns the position of the first element in the sequence that matches a value, or the end position if none does. Count returns how many elements in the sequence equal a value. Replace changes every matching element in the sequence to a new value. Find_if, count_if, and replace_if do the same jobs but use a test function instead of a fixed value to decide which elements qualify.

Other algorithms copy elements to an output position, move them, remove adjacent duplicates while copying, sort the elements, return the subsequence of equal values in a sorted sequence, or merge two sorted sequences into one output. The source notes that these algorithms, and many more, can be applied to the elements of containers, to strings, and to built-in arrays.

Every standard library algorithm receives its input as a sequence, and a sequence is described by two positions. The first marks where the sequence starts and the second marks where it ends. The source writes a half-open sequence from b to e as $[b : e)$. The square bracket on the left means the start position is included. The parenthesis on the right means the end position is excluded. So the sequence covers the elements from b up to, but not including, e.

The excluded end position is not an accident of notation. It is what allows the end position to act as a stopping marker. An algorithm that searches a sequence and finds nothing has nowhere to point inside the range, so the conventional result is the end position itself. The same convention makes empty ranges simple: when the two positions are equal, the sequence has zero elements and no special case is needed.

The rule that algorithms never add or subtract elements follows from how sequences are defined. A sequence is given by two positions and nothing else. The algorithm therefore sees a run of elements that it can read and, where the operation calls for it, overwrite. Overwriting a value is possible because each position leads to an element that can be assigned to.

What the algorithm never sees is the container that owns those elements. It has no handle through which to insert a new element or erase an old one. Changing how many elements exist therefore requires operating on the container itself. The diagram of this relationship has no edge leading from the algorithm back to the container, and that missing link is exactly why an algorithm alone cannot change the element count.

Sort and replace belong to the first column. Although sort() reorders the elements and replace() overwrites matching ones, each keeps the same set of positions and the same count. The second column contains the routes that bring the container into the work. A back inserter is special because it is a connection to the container, which lets an algorithm that writes to an output position add elements to that container.

If elements must be added or removed, the source gives two routes. One is to supply something that knows about the container, such as a back inserter, so that an algorithm writing to an output position can add elements to the container it is connected to. The other is to call operations directly on the container, such as push_back() to add an element at the end or erase() to remove one. Both routes bring the container into the work, which the bare algorithm does not do.

The before and after states above show the key point. A replace operation over the sequence changes the middle value from 8 to 5, but the container still holds three elements. Nothing about the algorithm's run could have removed or added a slot. If the program needs the container to hold a different number of elements, it must call a container operation such as erase() or push_back() in addition to any algorithm it uses.

Most of the time an algorithm is applied to a sequence that is the contents of a container. The source notes that the sequence concept is general and flexible, but in practice the sequence usually comes from a container. To make that common case easier, container versions of sort() and other algorithms can be provided. The source places these container versions in their own namespace, called Estd, which stands for extended std.

The separation exists to avoid interfering with other programmers' uses of namespace std. Keeping the container versions apart means a program can use a shorthand that accepts a whole container while the standard namespace keeps its original, sequence-based meaning. The shorthand is a convenience layer built on the same underlying idea of a sequence defined by a pair of positions.