Generalized Algorithms

Generalizing here means two things.

Programming

Predicting a Sum Before Reading On

Generalized algorithms in the standard library let you compute an operation over a whole sequence with a single call. The most familiar case is a sum. Accumulate visits the elements of a sequence from beginning to end and builds a running total, starting from an initial value. The best way to learn it is to run a short program first and check your own reasoning against the result.

cpp

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

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

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

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

Output

Notes on the code

The vector holds three doubles.
v.begin() and v.end() are the two iterator arguments that bound the sequence.
0.0 is the initial value the running total starts from.

What do you think happens?

Before reading on, write down what the program prints. Which part of the call decides the total: the list, the two iterator arguments, or the 0.0?

Reveal answer

Answer:

The total depends on all three arguments together. The iterators select the three elements 1.5, 2.5 and 3.0, and the 0.0 is where the running total begins. Adding them in order gives 7.

Reading the Three Arguments of a Call

Every use of accumulate follows one template. You name a sequence, you pass its beginning and its end, and you pass a starting value. The three arguments do different jobs, and each one changes the result. Naming each argument as you read the call makes the template easy to recognize in any program.

Which positions does the begin and end iterator cover, and where does the initial value enter the calculation?

Argument	Job in the call	Effect on the result
begin	Marks the first element visited	Changing it changes which elements are included
end	Marks the position just past the last element visited	Elements at and after this position are excluded
initial value	Sets the starting point of the running total	Is the first value the total holds before any element is added

The three arguments of an accumulate call and what each one controls

Following the Running Total Step by Step

Accumulate begins with the initial value and takes in each element in turn, from the beginning of the sequence to its end. After each element, the running total holds the value so far, and the last total is what the call returns. Tracing this by hand, with exact values, lets you check each intermediate total against what you expect.

After each element is visited, what is the accumulated value so far, and how does it change from one step to the next?

Worked example

Tracing the sum of three doubles

Compute the result of accumulate over the list {1.5, 2.5, 3.0} with initial value 0.0.

1
Set the running total
The total starts at the initial value, 0.0.
2
Visit the first element
Add 1.5 to 0.0. The running total is now 1.5.
3
Visit the second element
Add 2.5 to 1.5. The running total is now 4.0.
4
Visit the third element
Add 3.0 to 4.0. The running total is now 7.0.
5
Reach the end
No elements remain, so the last total, 7.0, is what the call returns.

Result

7.0

Why the Algorithm Works on Any Operation

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. The operation applied to the elements can be supplied as an argument. The version you have seen so far applies the most common operator for this algorithm, which is addition for a sum. A more general version also exists, in which the operation is a parameter you can replace with a different one.

Rule

In this notation, s_0 is the initial value, x_k is the element visited at step k, and op is the operation supplied to the algorithm. The default sum is the case where op is addition. The traversal stays the same, from begin to end, and only the operation changes.

cpp

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

int main() {
    std::vector<double> v = {2.0, 3.0, 4.0};
    double product = std::accumulate(v.begin(), v.end(), 1.0, std::multiplies<double>());
    std::cout << product << std::endl;
    return 0;
}

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

int main() {
    std::vector<double> v = {2.0, 3.0, 4.0};
    double product = std::accumulate(v.begin(), v.end(), 1.0, std::multiplies<double>());
    std::cout << product << std::endl;
    return 0;
}

Output

Notes on the code

The same three-argument template is used, with an operation passed in as the fourth argument.
The initial value is 1.0 because the running product starts from the multiplicative identity.

How does the same traversal produce a different result when the operation changes from addition to multiplication?

Mistakes That Produce Unexpected Totals

When a result looks wrong, the most reliable fix is to trace the running total step by step and find the first point where it disagrees with your expectation. The mistakes below are the ones that most often cause that disagreement.

Common mistake
Treating the end argument as the last element included
What it looks like
```
std::accumulate(v.begin(), v.end() - 1, 0.0) on {1.5, 2.5, 3.0} visits only 1.5 and 2.5.
```
Why it fails
The end argument marks the position just past the last element visited, so the element at that position is excluded.
Do this instead
Read the end argument as one past the final element. For the full list, pass v.end().
Common mistake
Forgetting that the initial value sets the starting point of the total
What it looks like
Using 0.0 as the initial value in a product call, so every element is multiplied into a total that began at zero.
Why it fails
The running total begins at the initial value, so a starting value of 0 keeps the product at 0 for any list.
Do this instead
Choose the initial value that matches the operation, such as 1.0 for a product and 0.0 for a sum.
Common mistake
Assuming the default operation is always addition
What it looks like
Passing a multiplication operation and expecting a sum.
Why it fails
The version with the built-in sum applies addition, but the general version uses whatever operation you supply.
Do this instead
Check whether the call has an operation argument, and if it does, trace the total with that operation.

Tracing a Partial Range

MEDIUM

Given the vector v = {4.0, 1.0, 2.0} and the call std::accumulate(v.begin(), v.end() - 1, 0.0), write down each running total as the algorithm visits the elements, then state the value the call returns.

Hints

Identify the end position first. v.end() - 1 points at the last element, so that element is not visited.
Start the total at 0.0 and add 4.0, then 1.0.
The final total after the last visited element is the returned value.

Your attempt (not saved)

Key Points to Carry Forward

1
Accumulate computes an operation, such as a sum, over a sequence by visiting its elements from begin to end and building a running total from an initial value.
2
The three arguments are the start position, the end position and the initial value, and each one changes the result.
3
Generalized algorithms apply to every standard-library sequence and let the operation be supplied as an argument.
4
When a result looks wrong, trace the running total step by step to find the first point of disagreement.

Key Takeaways

Accumulate computes an operation, such as a sum, over a sequence by visiting its elements from begin to end and building a running total from an initial value.
The three arguments are the start position, the end position and the initial value, and each one changes the result.
Generalized algorithms apply to every standard-library sequence and let the operation be supplied as an argument.
When a result looks wrong, trace the running total step by step to find the first point of disagreement.

Related concepts

More concepts starting with G