Operations Supplied as Arguments

Accumulate is a standard-library algorithm that adds up the elements of a sequence. Before reading any further, take a moment to make a guess. Imagine a list of four doubles, 1.0, 2.0, 3.0 and 4.0, and a call that passes the beginning of the list, the end of the list, and the starting value 0.0. What total do you expect the call to return, and which part of the call decides that total: the list, the two iterator arguments, or the 0.0?

Keep your guess in mind. The rest of this article explains exactly how the total is built, so you can check your prediction against the reasoning, step by step.

Two ideas in that definition do most of the work. The first is the running total: a single value that starts at the initial value and changes each time an element is taken in. The second is the traversal: the algorithm visits the elements in order, starting at the beginning of the sequence and moving toward its end. The final running total is the value the call returns.

The source states that the three arguments are the start position, the end position, and the initial value, and that each one changes the result. Here is a call that follows the template. The list v holds the four values from the opening prediction.

Notice that the sum is 10.0 only because the initial value is 0.0. The initial value is not decoration: it is the first value of the running total, and it is carried into every later step. Change it, and every intermediate total changes with it, which is exactly why each argument matters.

The diagram below lays the list out by position. Read it as a map of which elements the call visits. For the full call from the previous section, every element from the first to the last is visited, and the end position sits just past the final element, where the traversal stops.

The begin bound is the position of v[0], the first element visited. The end bound is the position after v[3]. Moving the end bound back to the position of v[2], as in the partial call, removes v[2] and v[3] from the visit, which is why the result changes from 10.0 to 3.0 while the list itself stays the same.

The clearest way to understand accumulate is to follow the running total through the list yourself. Each step takes the current total and adds the next element to it. Mathematically, if x_1 through x_n are the elements visited and init is the initial value, the running total s_k after visiting k elements follows this rule.

Read the diagram from left to right. Each box holds the running total at that moment, and each arrow is one visit to an element. The total you finally get back is the value in the last box before the traversal stops. Your opening prediction can now be checked against this trace: the 0.0 sets where the running total starts, and the list supplies the values that are added to it.

The source describes accumulate as a generalized algorithm. Generalizing here means two things. First, the algorithm is not tied to one container, so it applies to every standard-library sequence. Second, it does not hard-wire the operation applied to the elements, because that operation can be supplied as an argument. The same pattern of visiting elements from begin to end, starting from an initial value, stays the same.

The version you have seen so far applies the most common operator for this algorithm, which is addition for a sum. The source explains that each generalized algorithm is supplemented by a version that applies the most common operator, which means a more general version also exists. In that general version, the operation is a parameter, so a different operation can be passed in instead of the built-in sum. The source points to a later section for the full details, so treat this section as orientation.

Because the three parts are separate, you can change one without rewriting the others. A different sequence can be passed where the list was, a different initial value can start the total, and a different operation can replace addition. The traversal from begin to end still defines the order in which the elements are taken in.

When an accumulate result looks wrong, the source's advice is to trace the running total step by step and find the first point where it disagrees with what you expected. Suppose you expected 10.0 but a call returned 110.0. Writing out both traces side by side shows exactly where they split.

The first disagreement is at the start: the expected trace begins at 0.0, while the actual call begins at 100.0. Every later step inherits that difference, so the final total is off by exactly 100.0. Here the cause is the initial value, not the list and not the operation. Tracing the total in this way tells you which argument to inspect first.