Templates and Generic Types in C++

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

Programming

Predicting a Surprising Sum

Suppose you have a list of doubles and you want its total. In C++ the standard library can do the adding for you through the numeric header, using a generalized numerical algorithm called accumulate. The call takes a range, described by a begin position and an end position, plus a starting value. Before you look at the answer, it is worth noticing that the starting value is part of the calculation, and that a small change to it can change the printed result.

What do you think happens?

The list holds 1.5, 2.5, and 3.0. The call uses the starting value 0 (an int) instead of 0.0. What does the program print?

Reveal answer

Answer:

The starting value sets the type of the running total. Because 0 is an int, the running total is stored as an int at every step, so each fractional part is dropped along the way. The result is 6, not 7.

The rest of this article explains why that happens, and how to trace the calculation so you can find the exact step where a result drifts from what you expected.

Fixed Sums Versus Generalized Algorithms

A fixed sum calculation is a loop that you write by hand for one specific job. It walks the data itself, it adds with the plus operator, and it usually works on one element type. If you later need to multiply instead, or to sum a different kind of container, you rewrite the loop.

cpp

#include <vector>

std::vector<double> v = {1.5, 2.5, 3.0};

double sum = 0.0;
for (double x : v) {
    sum += x;
}
// sum is 7.0

#include <vector>

std::vector<double> v = {1.5, 2.5, 3.0};

double sum = 0.0;
for (double x : v) {
    sum += x;
}
// sum is 7.0

Output

sum is 7.0

A generalized numerical algorithm removes the loop from your code. The library handles the traversal, and you describe the sequence and the starting point. The same call works on any sequence in the standard library, not only a list of doubles, and the algorithm is not locked to addition. The general version accepts the operation as a parameter, and a version with the most common operator is supplied alongside it for convenience. For accumulate, that common operator is addition.

cpp

#include <numeric>
#include <vector>

std::vector<double> v = {1.5, 2.5, 3.0};

double sum = std::accumulate(v.begin(), v.end(), 0.0);
// sum is 7.0

#include <numeric>
#include <vector>

std::vector<double> v = {1.5, 2.5, 3.0};

double sum = std::accumulate(v.begin(), v.end(), 0.0);
// sum is 7.0

Output

7.0

Notes on the code

v.begin() is the start position of the range
v.end() is the end position, one past the last element
0.0 is the starting value, and its type sets the running total's type

What is the difference between a hardcoded loop that sums one specific type and an accumulate() call that works on any sequence with a supplied operation?

Tracing the Running Total

The easiest way to understand accumulate is to picture a single running total that is passed from one element to the next. The algorithm starts with the starting value. At each step it takes the total so far, combines it with one element using the operation, and keeps the result as the new total. When every element has been used, the final total is the value the call returns.

In what order does accumulate() combine the initial value and each element, and what is the running result after each step?

Notice that the order matters. The algorithm does not add the elements in some arbitrary order: it starts from the starting value and moves through the range from begin to end. Each element passes through this chain, so a problem in any single element, or in the starting value, shows up in the final result.

Worked example

Tracing accumulate() With a Starting Value of 0.0

Find the value returned by accumulate over the range {1.5, 2.5, 3.0} with starting value 0.0 and the default addition.

1
Set the running total
The starting value is 0.0, so the running total begins as a double equal to 0.0.
2
Combine the first element
Add 1.5 to the running total: $0.0 + 1.5 = 1.5$.
3
Combine the second element
Add 2.5 to the running total: $1.5 + 2.5 = 4.0$.
4
Combine the third element
Add 3.0 to the running total: $4.0 + 3.0 = 7.0$.
5
Return the total
The range is exhausted, so the running total is returned.

Result

7.0

Where a Result Goes Wrong

When an accumulate result is not what you expected, the source suggests walking the same stages as the chain: check the starting value, then check the range given by begin and end, then check the operation. Each of these is a separate place where the calculation can diverge. The starting value is often the first suspect, because its type is also the type of the running total.

Before

std::vector<double> v = {1.5, 2.5, 3.0};
auto total = std::accumulate(v.begin(), v.end(), 0);
// total is 6

Starting value is int 0, so the running total is an int and each fractional part is dropped

After

std::vector<double> v = {1.5, 2.5, 3.0};
auto total = std::accumulate(v.begin(), v.end(), 0.0);
// total is 7.0

Starting value is double 0.0, so the running total keeps its fractional parts

If the starting value is an int 0 but the elements are doubles, where does the fractional part get lost, and how does changing the initial value to 0.0 change the result?

Common mistake
Using an integer starting value for a sum of doubles
What it looks like
```
std::accumulate(v.begin(), v.end(), 0) on {1.5, 2.5, 3.0}
```
Why it fails
The starting value sets the type of the running total, so each partial sum is stored as an int and the fractional parts are lost.
Do this instead
Write the starting value in the element type, such as 0.0 for doubles.
Common mistake
Using the wrong starting value for a product
What it looks like
```
std::accumulate(v.begin(), v.end(), 1, std::multiplies<>()) on {1.5, 2.5, 3.0}
```
Why it fails
The product needs a neutral starting point of 1, but an int 1 still forces the running product to be an int, so the fractional steps are truncated.
Do this instead
Use 1.0 as the starting value when the elements are doubles.
Common mistake
Expecting a loop-style order of operations to be visible in the code
What it looks like
Assuming you must write a loop to control the traversal
Why it fails
The library walks the range for you, so the traversal is handled inside the algorithm, not in your code.
Do this instead
Describe the range and the starting value, then trace the chain of running totals when checking a result.

Supplying the Operation Yourself

The reason the algorithm is called generalized is that you can change the operation while keeping the same traversal. Instead of adding, you can multiply the elements. The starting value changes to 1, because that is the neutral starting point for a product, and the operation is passed as the fourth argument. The source describes the same pattern: the traversal stays the same, and only the operation and the starting point change.

cpp

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

std::vector<double> v = {1.5, 2.5, 3.0};

double product = std::accumulate(v.begin(), v.end(), 1.0, std::multiplies<double>());
// product is 11.25

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

std::vector<double> v = {1.5, 2.5, 3.0};

double product = std::accumulate(v.begin(), v.end(), 1.0, std::multiplies<double>());
// product is 11.25

Output

11.25

Notes on the code

1.0 is the neutral starting point for a product, written as a double
std::multiplies<double>() is the operation passed as the fourth argument

Complex Numbers as a Template Family

The second topic in this section is complex numbers. The standard library supports a family of complex number types, all modeled on the same complex class. The key point is that complex is a template: one definition produces a whole family of types, each built around a different scalar type. The scalar is the type used to store the real and imaginary parts, and the source names float and double as examples.

cpp

#include <complex>

std::complex<float>  a(1.5f, 2.0f);
std::complex<double> b(1.5, 2.0);

#include <complex>

std::complex<float>  a(1.5f, 2.0f);
std::complex<double> b(1.5, 2.0);

Notes on the code

std::complex<float> stores its real and imaginary parts as float
std::complex<double> stores its real and imaginary parts as double

Choosing between the complex types comes down to which scalar you give the template. The choice 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. The standard also provides a long double specialization; its precision is implementation-defined, so check your compiler and reference before relying on a specific size.

Scalar type	Typical use	Precision note
float	Smaller storage when some precision loss is acceptable	Least precise of the three
double	The common default for numerical work	More precise than float
long double	When extra precision is needed	Precision is implementation-defined

Scalar types commonly used with complex<T>

Practice Tracing a Starting Value

MEDIUM

A colleague calls std::accumulate(v.begin(), v.end(), 0) on a vector<double> holding {0.5, 0.5, 0.5} and expects 1.5. Trace the running total step by step and say what is returned, then rewrite the call so the result is correct.

Hints

Ask first what type the running total has, given that the starting value is an int.
After each addition, check whether the fractional part survives the conversion to int.
The fix is to change the starting value so the running total has a floating-point type.

Your attempt (not saved)

Key Takeaways

A generalized numerical algorithm such as accumulate walks a standard library sequence for you, so you describe the range and the starting value instead of writing the loop.
accumulate combines a starting value with each element in turn, and the running total passes through every step, so an error can be located at the starting value, the range, or the operation.
The starting value's type sets the type of the running total, so an int starting value can silently truncate fractional elements; use 0.0 or 1.0 for doubles.
The operation is a parameter, so the same traversal can add, multiply, or do other work, with the starting value chosen as the neutral point for that operation.
The complex type is a template; the scalar you choose (float, double, or long double) decides the precision of the stored real and imaginary parts.

Related concepts

Standard Library Sequences and Iterators

More concepts starting with T

Predicting a Surprising Sum

Fixed Sums Versus Generalized Algorithms

Tracing the Running Total

Where a Result Goes Wrong

Supplying the Operation Yourself

Complex Numbers as a Template Family

Practice Tracing a Starting Value

Key Takeaways

Related Topics

Related concepts