(std::)Accumulate Knowledge On STL Algorithms
If there’s one algorithm that lets you do all sorts of things, that must be std::accumulate.
It is important to know how to use it, and also how not to use it.
This post is part of the STL Learning Resource.
Basic usage
Numeric types
The first thing to know about std::accumulate is its location: the <numeric> header, away from its algorithms friends that live in the <algorithm> header.
As Scott Meyers puts it in Item 37 of Effective STL, std::accumulate is made to summarize a range. In other terms, this means that std::accumulate takes a collection of elements and returns only one value.
If you don’t specify anything, std::accumulate does the sum of all the elements in the range that it takes. This sum being done with operator+. And since we need two values to call operator+, we also need a initial value to start off the algorithm.
Here is its prototype:
template<typename InputIterator, typename T> T accumulate(InputIterator first, InputIterator last, T initialValue);
So for a collection of numbers std::accumulate adds them up:
std::vector<int> numbers = { 2, 9, -4, 2 };
int sum = std::accumulate(begin(numbers), end(numbers), 0);
Now there is a little pitfall here. The above piece of code works with ints but look at this piece of code with non integral numbers:
std::vector<double> doubles = { 1.5, 2, 3.5 };
double sum = std::accumulate(begin(doubles), end(doubles), 0);
Can you predict its output?
Click here to see the value of sum:
sum is 6
It’s surprising since 1.5 + 2 + 3.5 equals 7, not 6.
To understand what’s going on, look again at the prototype of std::accumulate:
template<typename InputIterator, typename T> T accumulate(InputIterator first, InputIterator last, T initialValue);
Note that the type T is not necessarily related to the type of the elements in the range. And in our call it is deduced from the third parameter, 0. And 0 is… an int! So T is int. So std::accumulate works with int and truncates the result of every sum.
A simple fix for this is to pass a double instead: 0.:
std::vector<double> doubles = { 1.5, 2, 3.5 };
double sum = std::accumulate(begin(doubles), end(doubles), 0.);
And then sum is 7.
This example is worth paying attention to because in it the code compiles and fails silently.
Other types
Nothing prevents using std::accumulate on other types than numeric types. Every type that implements an operator+ is a good candidate.
On std::string, operator+ does a concatenation:
std::vector<std::string> words = { "Winter ", "is ", "Coming." };
std::string sentence = std::accumulate(begin(words), end(words), std::string(""));
Note that we need to pass std::string("") and not just "" as an initial value, because the latter leads to T being const char* and not std::string, and does not compile.
In fact, even if the type of the elements in the range does not implement operator+, it can still fit into std::accumulate with its second overload that takes a function (or function object) to replace operator+.
The two parameters of this function may even be of different types. Here is an example to illustrate.
Let’s take a lift that can carry several people but only if their total weight is less than a certain limit. The following code computes the total weight of the group of people in the lift:
double totalWeight = std::accumulate(begin(group), end(group), 0.,
[](double currentWeight, Person const& person)
{
return currentWeight + person.getWeight();
});
Look at the last parameter that the algorithm takes. It represents a function (here a lambda) that takes a current value which is initialized with the third parameter (here 0.) and a new element to “absorb” into the current value. The algorithm returns this current value once it has “absorbed”, or “accumulated” every element of the range.
std::accumulate doesn’t model function application
This overload offers a lot of possibilities. But some of them you should avoid, because they make for code that takes an axe to disentangle. Or even a chainsaw in some cases.
We’ll get to an example but the principle is this:
std::accumulatemodels a summary of a range into one value. That’s it. In particular, it doesn’t model function application.
Indeed, imagine we want the weight of each of the people in our lift. This could be achieved the following way with std::accumulate:
std::accumulate(begin(group), end(group), &weights,
[](std::vector<double>* currentWeights, Person const& person)
{
currentWeights->push_back(person.getWeight());
return currentWeights;
});
But this is wrong. I’ve seen this in code. Hell, I’ve done it myself before I knew better about algorithms.
Why is it wrong? Because this code traverses a range, applies a function on each element and puts the results in a new collection. This is what std::transform would express in code.
Instead, this code uses std::accumulate that is made for summarizing a range into one value, and distorts its usage. The result is a lot of code that doesn’t tell much, and tells it wrong. In other terms it kills expressiveness of code.
To make it more expressive we use std::transform:
std::transform(begin(group), end(group), std::back_inserter(weights),
[](Person const& person){ return person.getWeight();});
You know when having a hammer makes everything look like a nail? Well, using accumulate for expressing function application is like using a hammer for sweeping the floor. You’ll have a hard time doing it and your neighbours (read: your fellow developers) will hate you for it.
Want a tip for spotting such bad usages of accumulate?
When the return value of
std::accumulateis discarded, it is a sign that it is not the right tool to use.
Going further with std::accumulate
All the above will let you be efficient when using accumulate. But there is even more to it than that!
I’ve realized this by watching Ben Deane’s CppCon talk std::accumulate: Exploring an Algorithmic Empire.
As a teaser to entice you to watch it, Ben shows in it that pretty much every algorithm of the STL can be implemented by using std::accumulate! Also, accumulate can be used to implement an equivalent of std::all_of, but that doesn’t short circuit:
std::accumulate(std::begin(booleans), std::end(booleans), true, std::logical_and<>())
And a lot more.
accumulate is a powerful hammer. Use it , but with care.
Related articles:
Don't want to miss out ? Follow:
Share this post!
