Generalized Algorithms in the Standard Library

Generalized numerical algorithms such as accumulate work on every standard library sequence and let you supply the operation as an argument.

Programming

Predicting a Sum Before Running It

Imagine a list of three doubles: 1.5, 2.5, and 3.0. You want their total. You could write a loop yourself, or you could ask the standard library to do the walking for you. Before reading on, decide what number you expect the library to print, and ask yourself whether it will differ from adding the numbers by hand.

What do you think happens?

What do you think the call below returns when the values are 1.5, 2.5, and 3.0 and the starting value is 0.0?

6.0
7.0
7.5
It depends on the order of the elements

Reveal answer

Answer:

7.0

The total is 1.5 + 2.5 + 3.0 = 7.0. Starting from 0.0 adds nothing, so the result matches the hand sum. The interesting part is not the answer but the mechanism that produces it, which the next sections trace step by step.

Fixed Loops Versus Supplied Operations

A hand-written sum loop fixes several things at once. It decides how to walk the sequence, it decides which operation combines the values (addition), and it decides where the running total begins. If you want to multiply instead, you rewrite the loop. The loop is a single-purpose tool.

A generalized numerical algorithm separates these concerns. The library handles the traversal, so you never write a loop. You describe the sequence with its begin and end positions, you give a starting value, and you can pass the operation itself as an argument. The general version of accumulate accepts that operation as a parameter, and a version with the most common operator, addition, is supplied alongside it for convenience. The same pattern therefore works on any sequence in the standard library, not only a list of doubles.

In a hand-written loop the traversal, the operation, and the starting point are all written into the code. In accumulate, the library supplies the traversal, while the starting value and the operation are arguments you choose.

Tracing the Running Total

The easiest way to understand accumulate is to think of a single running total that is passed from one element to the next. Each step takes the total so far and combines it with one element. The final value is the value the call returns. Because every element passes through this chain, a problem in any single element, or in the starting value, shows up in the final result.

cpp

#include <iostream>
#include <numeric>
#include <vector>

int main() {
    std::vector<double> values = {1.5, 2.5, 3.0};
    double total = std::accumulate(values.begin(), values.end(), 0.0);
    std::cout << total << std::endl;
    return 0;
}

#include <iostream>
#include <numeric>
#include <vector>

int main() {
    std::vector<double> values = {1.5, 2.5, 3.0};
    double total = std::accumulate(values.begin(), values.end(), 0.0);
    std::cout << total << std::endl;
    return 0;
}

Output

Notes on the code

values.begin() and values.end() give the start and end positions of the range
0.0 is the starting value that the running total begins from
No loop is written; the library walks the sequence and combines each element with the total

Worked example

Following the total through each element

Compute accumulate over the range 1.5, 2.5, 3.0 with a starting value of 0.0, and record the running total after every step.

1
Start
The running total begins at the starting value, 0.0.
2
Element 1
Combine 0.0 with 1.5 using addition. The running total is now 1.5.
3
Element 2
Combine 1.5 with 2.5. The running total is now 4.0.
4
Element 3
Combine 4.0 with 3.0. The running total is now 7.0, and there are no elements left.

Result

The call returns 7.0.

Each arrow adds one element to the running total. The last node is the value the call returns.

Where Results Diverge From Expectations

When the output differs from what you expected, walk through the same stages as the chain: check the starting value, check the range given by the begin and end positions, and then check the operation. Each of these is a separate place where the calculation can diverge. The starting value deserves special attention, because its type also affects how every step is computed.

Consider the same three values, but with an integer starting value written as 0 instead of 0.0. The total is then held in an integer, so each intermediate result has to fit into that integer. The running total is cut down at every step rather than only at the end.

cpp

#include <iostream>
#include <numeric>
#include <vector>

int main() {
    std::vector<double> values = {1.5, 2.5, 3.0};
    int total = std::accumulate(values.begin(), values.end(), 0);
    std::cout << total << std::endl;
    return 0;
}

#include <iostream>
#include <numeric>
#include <vector>

int main() {
    std::vector<double> values = {1.5, 2.5, 3.0};
    int total = std::accumulate(values.begin(), values.end(), 0);
    std::cout << total << std::endl;
    return 0;
}

Output

Notes on the code

The starting value 0 is an int, so the running total is an int
Each partial sum is stored back into an int, which drops the fractional part

Because the starting value is an int, each partial sum is stored as an int. The fractional parts are lost along the way, so the result is 6 instead of 7.0.

Common mistake
Assuming the result is computed in full precision because the elements are doubles
What it looks like
Using int 0 as the starting value with a vector of doubles and expecting 7.0
Why it fails
The starting value sets the type that holds the running total, so the total is repeatedly stored as an int.
Do this instead
Give the starting value the type you want the total to have, such as 0.0 for a double total.
Common mistake
Looking only at the final answer when the result is wrong
Why it fails
The error can enter at any stage of the chain, so the final number alone does not show where it began.
Do this instead
Check the starting value, then the begin and end range, then the operation, following the running total one element at a time.
Common mistake
Forgetting that the end position is one past the last element, so the range is not the same as the container

Changing the Operation

The reason the algorithm is called generalized is that you can change the operation while keeping the same traversal. To multiply the elements instead of adding them, you pass the multiplication operation as the fourth argument, and you change the starting value to 1. The value 1 is the neutral starting point for a product, in the same way that 0 is the neutral starting point for a sum.

cpp

#include <functional>
#include <iostream>
#include <numeric>
#include <vector>

int main() {
    std::vector<int> values = {2, 3, 4};
    int product = std::accumulate(values.begin(), values.end(), 1, std::multiplies<int>());
    std::cout << product << std::endl;
    return 0;
}

#include <functional>
#include <iostream>
#include <numeric>
#include <vector>

int main() {
    std::vector<int> values = {2, 3, 4};
    int product = std::accumulate(values.begin(), values.end(), 1, std::multiplies<int>());
    std::cout << product << std::endl;
    return 0;
}

Output

Notes on the code

The fourth argument is the operation, here std::multiplies<int>
The starting value 1 is neutral for multiplication, so the first step does not change the product

Complex Numbers and Their Scalar Types

The second topic in this section is complex numbers. The standard library provides complex as a template, which means one definition produces a whole family of types. Each member of that family is built around a different scalar type, the type used to store the real and imaginary parts. Common examples named in this material are float and double.

cpp

#include <complex>

int main() {
    std::complex<float> a(1.5f, 2.0f);
    std::complex<double> b(1.5, 2.0);
    return 0;
}

#include <complex>

int main() {
    std::complex<float> a(1.5f, 2.0f);
    std::complex<double> b(1.5, 2.0);
    return 0;
}

Notes on the code

std::complex<float> names the family member whose parts are stored as float
std::complex<double> names the family member whose parts are stored as double

Choosing between these types comes down to the scalar you give the template. The scalar decides the precision of the stored parts. When a calculation depends on accuracy, the scalar type is one of the first things to check, just as you checked the starting value and the range in the accumulate example.

Applying the Chain to a New Calculation

MEDIUM

A vector holds the values 0.5, 0.5, and 2.0. Predict the value returned by accumulate with a starting value of 0.0, then trace the running total after each element. Next, predict what changes if the starting value is written as the int 0 instead.

Hints

Write down the running total before the first element, then after each element.
The int starting value changes how each partial sum is stored, not only the final number.

Your attempt (not saved)

Key Takeaways

A generalized numerical algorithm such as accumulate walks a sequence for you and lets you supply the operation as an argument, so you do not write the loop.
accumulate combines a starting value with each element in turn, so the running total is the thread to follow when a result is unexpected.
When a result is wrong, check the starting value, the begin and end range, and the operation, in that order, because each is a separate place the calculation can diverge.
The standard library complex is a template, so the scalar type you choose decides the precision of the stored parts, and that choice belongs among your first checks when accuracy matters.

Related concepts

Iterators and Sequences in the Standard Library

More concepts starting with G

Predicting a Sum Before Running It

Fixed Loops Versus Supplied Operations

Tracing the Running Total

Where Results Diverge From Expectations

Changing the Operation

Complex Numbers and Their Scalar Types

Applying the Chain to a New Calculation

Key Takeaways

Related Topics

Related concepts