Best Practices for Using STL Algorithms

Almost every C++ program eventually needs to do something to a collection of values, such as adding them up, searching for one, or rearranging them. The C++ standard library already provides ready-made algorithms for many of these jobs, so a programmer can often choose between writing a loop by hand and calling a library algorithm. This article answers a practical question: when both options are available, which one should you use, and why?

Before reading any further, try a prediction. Imagine a vector holding five integers, where two of them are zeros. You call the removal algorithm to get rid of every zero. Ask yourself how many elements the vector holds after that call returns. Your first guess is probably a smaller number, and that guess is exactly the belief this article will correct.

A very natural first guess about an STL algorithm is that it works like a tool that edits a list directly. You might expect that calling an algorithm on a sequence can make the sequence longer by adding elements, or shorter by removing them. The name of an algorithm that seems to remove things, such as one that removes matching values, invites exactly this belief.

The rule to hold onto is this: algorithms do not directly add or subtract elements from their argument sequences. The number of elements in a sequence is therefore not changed by an STL algorithm call alone. An algorithm works on the values inside the range it is given. It can move those values around and it can choose which of them to report, but it does not have the power to delete the positions that the range covers.

Consider a concrete run. The vector starts with the values 3, 0, 7, 0, and 5. The removal algorithm is asked to remove every value equal to zero. The algorithm does not look at the vector as a single object that can shrink. Instead, it walks through the range from the first position to the end, and every value it decides to keep is moved toward the front of the range. When it finishes, it returns an iterator that marks where the kept values end.

The diagram shows the two states side by side. Both sequences still have five positions, which is why the size is unchanged. The only thing that changed is the arrangement of the values: the kept values are gathered at the front, and the tail holds values your program should ignore. The algorithm did what it was designed to do, which is to rearrange and select values, and it did not change how many positions exist.

Every STL algorithm is given a range, usually as a pair of iterators: a begin position and an end position. The range covers the positions from begin up to, but not including, end. The algorithm reads and writes only the slots inside that range. It can write values into those slots, swap them, or move them, but the set of slots is fixed by the range it was handed.

Notice what this means for sizing. The five slots exist before the call and they exist after the call. The algorithm can change which value occupies each slot, but the number of slots is determined by the vector, not by the algorithm. That is why you should never read the size of a sequence as a count of how many values the algorithm kept.

If you want the sequence itself to end up shorter, the change has to be made through the sequence, not through the algorithm. The usual pattern has two steps. First, call the algorithm and keep the iterator it returns as the new end of the useful values. Second, ask the sequence to erase everything from that point to its real end. The algorithm rearranges the values, and the erase call changes the size. Because these are two separate steps, each has a clear job.

Consider a simple task: add up the numbers stored in a vector. The hand-written approach uses an index-based loop to visit each element in turn. The loop starts a running total at zero and adds each value to it. This works, but the reader has to check the loop mechanics: the starting index, the stopping condition, and the update of the total.

The library version is preferred for a practical reason: the standard-library algorithm has been designed, specified, and implemented with care. Standard-library algorithms tend to be more carefully designed, specified, and implemented than the average hand-crafted loop. A reader does not have to re-verify the loop mechanics each time the code is read, because the call itself says what is being done.

When you read a hand-written loop, ask what job it is doing. If the loop is visiting every value to add them up, searching for one, or rearranging them, a standard-library algorithm probably already exists for that job. The guidance is to prefer standard-library algorithms over code written in the bare language. The loop that remains is often the sign that the programmer has not yet noticed the library call that matches the intent.

The relationship between these ideas is hierarchical. Standard-library algorithms are the broader family that the guidance recommends. Container algorithms form one category within that family, defined by the kind of thing they work on: containers. So a container algorithm is still a standard-library algorithm, and the category is a way of grouping algorithms by their target.

The same ideas apply inside any container category. Whatever the category, the sizing rule from earlier still holds: an algorithm that operates on a container rearranges or selects values and does not add or remove the container's elements on its own. Any change in size comes from an explicit operation on the container itself.