Container Operations in C++

Most people first meet containers through operations that visibly change them, such as adding an item to the end of a list or removing one from the middle. It is natural to carry that experience over to the standard library. If an algorithm is handed a container, the reasoning goes, it should be able to shrink it, grow it, or rearrange whatever it holds. 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. Before reading on, try to decide for yourself which side of that line a few familiar operations fall on.

Every standard library algorithm receives its input as a sequence. Two facts about the call matter from the start: the algorithm comes from the algorithm header and lives in namespace std, and its inputs are positions that describe a run of elements rather than the container object itself.

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. The sequence therefore covers the elements from b up to, but not including, e.

The end position is the stopping marker of the sequence. Because it is excluded, the number of elements in the sequence is simply the distance between the two positions, and an empty range needs no special case: when the two positions are equal, the distance is zero. The same convention explains why an algorithm that searches a sequence and finds nothing conventionally returns the end position itself, since there is no element inside the range for it to point at.

Several representative algorithms follow the same pattern: a sequence is supplied as input, and the algorithm answers a question or performs an operation over the elements in that range. The count algorithm returns how many elements in the sequence equal a value. The replace algorithm changes every matching element to a new value. Algorithms with the suffix _if do the same jobs but use a test function instead of a fixed value to decide which elements qualify. The following program uses count and replace on a vector. Trace it before reading the output.

The output confirms the prediction. The two matching 4s are now 9s, the vector still holds four elements, and the 1 and 2 are untouched. The algorithm wrote new values into existing positions, which is possible because each position leads to an element that can be assigned to. Nothing in that process created or destroyed an element.

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. It never sees the container that owns those elements, so it has no handle through which to insert a new element or erase an old one. Changing how many elements exist requires operating on the container itself.

The diagram makes the missing link visible. The sequence covers elements that belong to the container, and the algorithm consumes the sequence. There is no edge from the algorithm to the container, which is exactly why an algorithm alone cannot change how many elements the container holds.

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, which lets an algorithm that writes to an output position add elements to a 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 next program uses the second route.

Notice that push_back() and erase() are member operations called on the vector itself. The count changes only because the container was asked to change. For the output-iterator route, the same idea appears in a copy call that writes through a back inserter, such as std::copy(src.begin(), src.end(), std::back_inserter(out)). The copy algorithm still only walks a sequence and writes to positions; the back inserter is what connects those writes to the container and lets it grow.

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, 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 them in their own namespace, called Estd, which stands for extended std. The purpose of this separation is to avoid interfering with other programmers' uses of namespace std.

Keeping the container versions separate 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 on top of the same underlying idea of sequences defined by a pair of positions.