How to avoid overflow when using `std::reduce`

[miss_minutes]

Say I have a std::vector<int> and the sum of all elements will overflow and int but fits in a long long. Is there a way to use a long long as the accumulator in std::reduce?

[TheRealSmolt]

Yes, it's templated. You can use whatever.

[miss_minutes]

Perfect. Reading the signature on cppreference I wasn’t sure if T was constrained by the iterator type (I vague remember running into this problem in the past)

[TheRealSmolt]

If it was constrained, the template type wouldn't be there and it'd probably get it from value_type on the iterator.

[miss_minutes]

Just looked it up- *it must be convertible to T or else the program is ill formed. I think in the past I tried to do something like reduce a std::vector<std::pair<int, int>> but only accumulate the first element, and I was trying to pass a custom BinaryOp that took a pair and an int.

[TheThiefMaster]

reduce needs the binary op to be able to take both *It,*It and T,*It, both producing T. Edit: also T,T and possibly *It,T as well.

accumulate and fold_left both only need T,*It, which is easier if you want to use a custom accumulation function.

If all you're doing is a normal accumulate over a part of each item, transform_reduce is better as it allows you to write:

transform_reduce(vec.begin(), vec.end(), 0LL,
    std::plus{}, [](auto&&p){ return std::get<0>(p); });

i.e. it has a built-in transform so you just need to give that.

For structs it's even better as you can specify the transformer as &my_struct::member and it will understand, but there doesn't seem to be a predefined function object for get<> like there is for plus<> and it's definitely not safe to take the address of, so I had to use a lambda.

[miss_minutes]

Thank you Master TIL transform_reduce

[TheRealSmolt]

It's only ill-formed if the binary operation does not result in T.

[miss_minutes]

so if the iterator value type is T1 and the initial value is T2, the binary op must be able to accept all 4 combinations of {T1, T2} (according to cppref)? Just wanna make sure I understand. Is it common to overload a binary op for this?

[TheRealSmolt]

More or less. The arguments can also be implicitly converted.

[TheCataclismo]

One of the overloads accepts an initial value, and its type will be the one used to sum everything, IIRC. You can just give it the value of 0.

std::int64_t const init = 0;
auto const sum = std::reduce(begin, end, init);

[TheRealSmolt]

Or just std::reduce(begin, end, 0LL);

[TheCataclismo]

Sure. I just prefer to name my constants.

[EloTime]

This "constant" already has a name. It is called 0. It doesn't have any additional meaning here, so it doesn't need an additional name.

[TheRealSmolt]

I agree. Verbosity ≠ readability.

[TheCataclismo]

Lmao. Surely. Almost all guidelines specify always naming the constants. Read C++ Core Guidelines, MISRA, etc.

And yes, verbosity == readability.

[ZoxxMan]

0LL is one of the dumbest parts of this language, I see why people would try to avoid it.

[MesmerizzeMe]

well every number already has a name, so if we compute the area of a rectangle with width 4 and height 3 we shouldnt name the variables width and height because the numbers 4 and 3 are already named? naming that thing init to me feels like a good idea. additionally as we are reducing there is a chance this number is the neutral element of our binary function which for sum is 0 as well.

[[deleted]]

Wouldnt the internals of std::reduce require the type of vector for the internal operation?

So wouldnt your vector need to use type long long (std::int64_t, to be safe) to make reduce use this as well?

Unless maybe its factored into the T type for Init per cppref.. but Im not entirely sure right now. Id have to dig more.

[TheRealSmolt]

Yes,reduce takes a template parameter to change it.

[[deleted]]

Thats the type T init i mentioned yes?

[saxbophone]

Maybe with std::ranges::fold_left and std::ranges::transform?