Leonid Volnitsky Leonid Volnitsky - 25 days ago 25
C++ Question

Understanding std::accumulate

I want to know why

std::accumulate
(aka reduce) 3rd parameter is needed. For those who do not know what
accumulate
is, it's used like so:

vector<int> V{1,2,3};
int sum = accumulate(V.begin(), V.end(), 0);
// sum == 6


Call to
accumulate
is equivalent to:

sum = 0; // 0 - value of 3rd param
for (auto x : V) sum += x;


There is also optional 4th parameter, which allow to replace addition with any other operation.

Rationale that I've heard is that if you need let say not to add up, but multiply elements of a vector, we need other (non-zero) initial value:

vector<int> V{1,2,3};
int product = accumulate(V.begin(), V.end(), 1, multiplies<int>());


But why not do like Python - set initial value for
V.begin()
, and use range starting from
V.begin()+1
. Something like this:

int sum = accumulate(V.begin()+1, V.end(), V.begin());


This will work for any op. Why is 3rd parameter needed at all?

Answer

The way things are, it is annoying for code that knows for sure a range isn't empty and that wants to start accumulating from the first element of the range on. Depending on the operation that is used to accumulate with, it's not always obvious what the 'zero' value to use is.

If on the other hand you only provide a version that requires non-empty ranges, it's annoying for callers that don't know for sure that their ranges aren't empty. An additional burden is put on them.

One perspective is that the best of both worlds is of course to provide both functionality. As an example, Haskell provides both foldl1 and foldr1 (which require non-empty lists) alongside foldl and foldr (which mirror std::transform).

Another perspective is that since the one can be implemented in terms of the other with a trivial transformation (as you've demonstrated: std::transform(std::next(b), e, *b, f) -- std::next is C++11 but the point still stands), it is preferable to make the interface as minimal as it can be with no real loss of expressive power.

Comments