 Jonathan Boccara's blog

Recent Posts

# (std::)Accumulate Knowledge On STL Algorithms

Published October 17, 2017 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:

So for a collection of numbers `std::accumulate` adds them up:

Now there is a little pitfall here. The above piece of code works with `int`s but look at this piece of code with non integral numbers:

Can you predict its output?

Click here to see the value of `sum`:

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`:

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.`:

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:

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:

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::accumulate` models 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`:

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`:

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::accumulate` is 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:

And a lot more.

`accumulate` is a powerful hammer. Use it , but with care.

Related articles:

Become a Patron!