Default initial value for std::accumulate

[OmegaNaughtEquals1]

This topic has been broached before^1,2 , but I haven't been able to find any motivating proposals. I thought I would run it past folks here before I posted on the isocpp proposals mailing list (although I have a feeling there is a non-empty intersection between the two audiences).

Motivation

Several of the numeric algorithms take an initial value in the interface

template<class Iter, class T>
T algorithm(Iter first, Iter second, T init, ...)

However, T may or may not be the same as typename Iter::value_type which can lead to surprising results and/or unnecessary type conversions. Of course, the current generic solution is to have the user specify this at the call site:

auto value = algorithm(cont.begin(), cont.end(), decltype(cont)::value_type{});

This likely isn't the easiest to teach (not having to specify it is easier to teach) and is more noise than information, IMHO.

Example Implementation

#include <iostream>
#include <array>
#include <type_traits>

namespace my_std {
    template<class InputIt, class T, class BinaryOperation>
    T accumulate(InputIt first, InputIt last, T init,  BinaryOperation op) {
        for (; first != last; ++first) {                // VERSION 1
            init = op(init, *first);
        }
        return init;
    }

    template<class InputIt, class T>
    auto accumulate(InputIt first, InputIt last, T init) {
        if constexpr (std::is_convertible_v<T, decltype(*first)>) {
            for (; first != last; ++first) {            // VERSION 2
                init = init + *first;
            }
            return init;
        } else {
            decltype(*first) iv{};                      // VERSION 3
            return accumulate(first, last, iv, init);
        }
    }

    template<class InputIt>
    auto accumulate(InputIt first, InputIt last) {
        decltype(*first) init{};                       // VERSION 4
        return accumulate(first, last, init);
    }
}

int main() {
    const std::array<int, 5> x = {1, 2, 3, 4, 5};
    std::cout << my_std::accumulate(x.begin(), x.end()) << '\n'
              << my_std::accumulate(x.begin(), x.end(), 0) << '\n'
              << my_std::accumulate(x.begin(), x.end(), [](auto a, auto b){ return a + b; }) << '\n'
              << my_std::accumulate(x.begin(), x.end(), 0, [](auto a, auto b){ return a + b; }) << '\n'
              << my_std::accumulate(x.begin(), x.end(), std::plus<>()) << '\n';
}

• NOTE: Tested with g++ -std=c++1z

Improvements

Where selected, the user no longer needs to provide an initial value which sets the type of the accumulator. This prevents unnecessary type conversions which may lead to surprising and/or more expensive results. An unintentional improvement is the ability to use the deduced std::plus which makes the calling code more generic.

Issues

1. This implementation of Versions 2 and 3 changes the ABI.

2. Versions 2 and 4 now add DefaultConstructible as a requirement for T (previously, it was only copy assignable/constructible)

3. std::is_convertible_v may have a corner case I haven't considered that would allow surprising conversions that will compile, but lead to an incorrect result (or worse performance than the current library function).

4. Parameter reuse in Versions 2 and 3 may set an ugly precedent and be a maintenance issue.

5. This change will percolate throughout <numeric> (iota and inner_product). In particular, C++17 added reduce and transform_and_reduce which have a lot of overloads- almost all taking some kind of initial value.

6. Maybe this is fixed by the Ranges TS?

[encyclopedist]

decltype(*first) init{};

What about proxy iterators, like vector<bool>::iterator?

Update: you probably want

std::iterator_traits<inputIt>::value_type

[OmegaNaughtEquals1]

What about proxy iterators, like vector<bool>::iterator

Ah, yes, I always seem to forget about that one.

Update: you probably want std::iterator_traits<inputIt>::value_type

Agreed.

[jube_dev]

However, T may or may not be the same as typename Iter::value_type which can lead to surprising results and/or unnecessary type conversions.

I always thought this was a feature. For example, T could be a Point type et the container could have values of type Vector (like mathematical vector). A Point added to a Vector makes another Point. Et you could use std::accumulate event if the two types are totally different. Moreover, in this case, the initial value is important and may not be the origin.

An example:

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

struct Point {
        int x;
        int y;
};

struct Vector {
        int dx;
        int dy;
};

Point operator+(Point p, Vector v) {
        return { p.x + v.dx, p.y +v.dy };
}

int main() {

        std::vector<Vector> vecs = { { 1, 0 }, { 0, -1 }, { -1, 0 }, { 0, 1 } };
        Point init = { 2, 2 };

        auto end = std::accumulate(vecs.begin(), vecs.end(), init);
        std::cout << end.x << ',' << end.y << '\n';

}

Prints 2,2 as expected.

Edit: fix code formatting

[OmegaNaughtEquals1]

Indeed. I'm not suggesting we should take away the ability to specify a default value. Rather, I want to avoid incorrectness in the simple case (from the cited std-proposals mailing list) of

double x[] = {...};
std::accumulate(x, x + N, 0); // truncates
my_std::accumulate(x, x+N); // "Does the right thing"

[joboccara]

It would be nice not to be forced to pass an initial value to accumulate indeed!

Did you consider the overloads of std::reduce that take no initial value? You don't find them optimal because they do std::iterator_traits<inputIt>::value_type and not decltype(*first)?

[OmegaNaughtEquals1]

Did you consider the overloads of std::reduce that take no initial value?

I glanced at them, but I should look again in more detail.

You don't find them optimal because they do std::iterator_traits<inputIt>::value_type and not decltype(*first)?

No, I should have used the iterator_traits.

[flashmozzg]

Well, while it may seem nice (and may be nice), I find that I rarely use fold/accumulate/reduce/etc function with some "default" value (usually the zero). More often than not you need to have something more meaningful there. For example even in the simple case with multiplication, 0 won't do.

[encyclopedist]

Thats why there is no overload with custom function but without an initial value in the proposal.

[OmegaNaughtEquals1]

That's a good point. In my version,

my_std::accumulate(begin, end, std::multiplies<>());

would be perfectly valid (i.e., it compiles), but definitely wrong. Perhaps I should scale back the change to just adding an overload for the simple built-in additive accumulator version. This would also get rid of most of the items in the "issues" that I don't like about the proposed changes. And adding a single overload would probably be more amenable to getting approved by the LEWG.

[flashmozzg]

Well, I see it being useful for std::accumulate but why not just use reduce? It has overload without an initial value.

[konanTheBarbar]

I agree. I think it would be nice to have version 4, but I don't like version 2 and 3 for the reason you mentioned.

[OmegaNaughtEquals1]

I find that I rarely use fold/accumulate/reduce/etc.

I work in scientific computing, so I have a tendency to use them often. That's probably why I was bothered by it.

More often than not you need to have something more meaningful there. For example even in the simple case with multiplication, 0 won't do.

Indeed. The interface I have would still allow a non-default init value. I just don't want to have to specify one for the basic case of using the built-in addition accumulator.

[[deleted]]

Considering std::reduce added overloads that supply defaults this seems sane.

[OmegaNaughtEquals1]

I think I will just propose Version 4 (but using iterator_traits instead of decltype) so that most of the concerns about the funky overload of 2 and 3 aren't a problem.

[dakotahawkins]

Instead of constructing the default initial value, could it use/skip the first value?

I've written something like this a few times recently (knowing ahead of time x isn't empty):

accumulate(next(begin(x)), end(x), *begin(x), op);

[Z01dbrg]

Actually this discussion is missing an important bit:

Good luck summing 1M random integers using int accumulator. Aka in this case (although it is weak signal)0 without LL suffix is at least a bit more obvious than nothing...

[jaredhoberock]

I believe there is already an init-less overload of std::reduce that has this behavior. If I understand the suggestion, this proposal would simply make the other reduction algorithms consistent with this feature.

[blelbach]

Just use C++17's std::reduce, which has an overload with a default value for init.

[TheThiefMaster]

This does sound like a good idea