Algorithms in the C++ Standard Library

Many programs need to do arithmetic over collections of values. They may need to add up a list of numbers, combine results step by step, or process a sequence of data. You could write a loop for each of these jobs every time, but C++ does not require you to write every such routine from scratch. The standard library collects a set of ready-made routines for these jobs, and the header named <numeric> is where a group of them lives.

This article follows one idea through the whole discussion: a numerical algorithm is a reusable routine, and you can find it by asking which library it belongs to and what job it does. We will use accumulate() as the running example, because the source names it as the representative member of this group.

The section that introduces this topic makes two claims you should hold onto. First, the <numeric> library contains numerical algorithms. Second, the set it offers is small, and accumulate() is named as one member of it. Together these claims tell you how to think about the library: it is a focused toolkit, not an exhaustive catalogue of every mathematical operation. If you need a numerical routine, checking <numeric> is a sensible first step, but you should not expect it to contain everything.

It helps to see how the pieces relate. The <numeric> header is the container. Inside it sits the group of numerical algorithms. accumulate() is one specific member of that group. Reading this relationship from the top down makes it easy to answer questions such as where a numerical routine comes from, or what a named routine belongs to.

Read the diagram from the top down. If someone asks where accumulate() belongs, the answer comes from its role, which is summing or combining numbers, and from its library, which is the <numeric> header. You do not need to have memorized the name in isolation.

Generalized numerical algorithms are reusable, general-purpose routines for numerical work rather than one-off code. The word generalized signals that the routine is not tied to a single task. The same routine can serve many numerical jobs, and the parts that change from job to job can be supplied by the caller.

accumulate() takes a range of values and combines them into a single result. It begins with a starting value, called the initial value, and then folds in each element one at a time. Each step takes the running result so far and combines it with the next element. When the range is exhausted, the running result is returned. The best way to understand this is to watch the running value change.

Notice that the running result carries forward from one step to the next. Each step does not start over; it builds on what the previous step produced. This is the reason a single call can turn a whole range of values into one answer.

The word generalized matters here. The routine is not fixed to addition. The rule used to combine the running result with each element is a replaceable part. With ordinary addition, the routine sums values. With a different combining rule, such as multiplication, the same routine multiplies values instead. The traversal and the step-by-step carrying of the running result stay the same; only the combining rule changes.