Container Algorithms in C++

Almost every C++ program eventually needs to do something to a collection of values. It might add the values up, search for one of them, or rearrange them. A programmer can write a loop by hand for each of these jobs, using only the bare features of the language. The C++ standard library, however, already provides ready-made algorithms for many of these jobs. When both options are available, which one should you use, and why? This article works through that practical question, using a small example and tracing exactly what happens in each version.

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. It starts a running total at zero and adds each value to it. Trace the code below before you look at anything else. Notice which parts of the program you have to understand to be sure it is correct: the starting value, the loop condition, the index update, and the body that adds to the total.

The second version of the same task hands the repetitive work to a standard-library algorithm. The standard library's summing algorithm is std::accumulate, declared in the numeric header. Both versions compute the same total, but the second one is shorter and expresses the intent directly: accumulate the values from the beginning of the vector to its end, starting from zero.

Map the pieces of the raw loop onto the algorithm call. The starting value 0 in the call plays the role of the initialization total = 0. The pair numbers.begin() and numbers.end() replaces the index variable and the loop condition, because together they say where the traversal starts and where it stops. The update step and the body are handled inside the algorithm, so the reader no longer has to check the increment or the bounds each time. This particular task needs no predicate, since every element is simply added. Other algorithms accept a predicate, which is a rule that the algorithm applies to each element, and that is where a hand-written body would otherwise have to be rewritten.

The main reason to prefer the library version is that standard-library algorithms tend to be more carefully designed, specified, and implemented than the average hand-crafted loop. The author of a hand-written loop has to get every detail right in one place: the starting value, the boundary, the increment, and the update. A library algorithm has already been built and specified for that job, so the reader does not have to re-verify the loop mechanics each time the code is read. The code's intent becomes visible at a glance.

The pair numbers.begin() and numbers.end() describes a range. You can read it as a half-open range, written $[\mathrm{begin}, \mathrm{end})$: the range includes the element at begin and stops just before end. The end position is one past the last element, so it marks the boundary rather than an element that gets processed. This is why the algorithm call in the previous section processes exactly the four values 3, 5, 8, and 2, and nothing beyond them.

The diagram shows the four stored values as cells in order. The range starts at the first cell and runs through the last one. The end position sits after the final cell, so an algorithm given this pair processes every stored value and stops without touching anything beyond the vector.

Container algorithms are a category of algorithms that operate on containers, meaning the kind of thing they work on is a whole collection. Algorithms in the wider family can be given the same kind of input as a pair of positions instead. The two forms differ in what the caller hands over. The comparison below sets them side by side.

The relationship between these ideas is hierarchical. Standard-library algorithms form the broader family that the guidance recommends. Container algorithms are one category within that family, defined by the kind of thing they operate on: containers. The preference for library algorithms over hand-crafted loops applies to the whole family, and the container category is one way of organizing the members of that family by their input.

Take the loop from the first section and ask what it would take to replace it. Identify the starting value, the range the loop covers, and any work the body does beyond adding each element. If the body only adds elements, a summing algorithm with the same range and starting value matches the job. If the body does something more specific, you have to decide whether a standard algorithm can express it or whether a loop is still the clearest choice.