Sequences in the C++ Standard Library

Suppose you have two prices, 1.5 and 2.5, stored in a sequence, and you want their total. You call the summing algorithm from the <numeric> header, but you pass the integer 0 as the starting value instead of 0.0. Before you read on, make a prediction about what gets printed. The answer depends on a detail that is easy to miss: the starting value and its type, not the numbers in the sequence, control the type of the result.

The <numeric> header provides a small set of generalized numerical algorithms. The one this article studies is accumulate(), which is the algorithm behind the sum calculations you will see in the code that follows.

The word generalized describes two properties. First, these algorithms are not tied to one kind of container. Each one is written to work on every kind of standard-library sequence, so the same accumulate() call pattern applies whether the values live in a vector, a list, or an array. Second, the operation applied to the elements is itself a parameter that the caller can supply. The algorithm is written once, and the sequence and the operation are provided by whoever calls it.

Each algorithm also comes in two forms. The general form takes an operation as an argument. The common form applies the most common operator for that algorithm. For accumulate(), the common form computes a plain sum, which is the everyday case. The general form lets you replace that sum with any combining step you choose. Keeping both forms in mind helps explain why the same walk through a sequence can produce very different results.

accumulate() takes three required arguments in its basic form: the beginning of the sequence, the end of the sequence, and a starting value. It begins with the starting value as its running total. It then visits each element from the beginning to the end and combines the running total with that element. When the walk has visited every element, the running total is the result. Watch three things as the walk runs: which value is the starting point, which elements are visited and in what order, and what number finally reaches the output.

The following program sums a vector of three integers. The starting value is 0, so the running total begins at zero and grows by each element in turn.

The two iterator arguments define a range written $[first, last)$. The range includes the element at first and every element after it, up to but not including the element at last. Since the end iterator marks a position one past the final element, the walk never touches it. That is why values.end() is the correct second argument when you want every element of a vector.

Consider the vector {4, 8, 15} with starting value 0. The call accumulate(values.begin(), values.end(), 0) visits all three values and returns 27. The same walk with the end bound pulled back by one element would return 12, because 15 would never be visited. Changing a bound does not change the algorithm at all, only which stored values it reaches.

The default form combines the running total with each element by addition. A supplied operation changes only that combining step. The walk itself, from the starting value through each element in order to the final running total, stays exactly the same. This means you can compute a product by passing a multiplication operation as the fourth argument, with 1 as the starting value, because 1 is the identity for multiplication.

The starting value is the first running total, so its type shapes every combining step that follows. When the starting value is an integer, the running total is an integer, and each step's result is held in that integer form. Fractions produced by the elements are then lost. The diagram below compares the same sequence {1.5, 2.5} with an int starting value and a double starting value.

Most wrong results from accumulate() come from its inputs rather than from the algorithm itself. When a printed total does not match your hand calculation, follow the same order as the walk.