Way of writing "reduce"

[Malcolm McLean]

"reduce" takes a collection of objects, and applies a binary operation to pairs that returns an objet of the same type, until only one object remains.

Here's my attempt.

#include <iostream>
#include <vector>

template<class Iterator, typename func_t>
typename Iterator::value_type reduce(Iterator start, Iterator end, func_t op )
{
typename Iterator::value_type answer = *start;
start++;
while (start != end)
{
answer = op(answer, *start);
start++;
}
return answer;
}

int main() {
const std::vector<double> array = { 1, 2, 3, 4};
double v = reduce(array.begin(), array.end(),
[](double a, double b){return a < b ? a : b;});
std::cout << "Result " << v << "\n";
return 0;
}

Can this be improved??

[Bonita Montero]

Am 04.03.2022 um 20:27 schrieb Malcolm McLean:

> template<class Iterator, typename func_t>
> typename Iterator::value_type reduce(Iterator start, Iterator end, func_t op )

typename std::iterator_traits<Iterator>::value_type

> {
> typename Iterator::value_type answer = *start;

typename std::iterator_traits<Iterator>::value_type

So this works also with pointers.

[Cholo Lennon]

Maybe adding the initial value.

More information about the (old?) C++ implementation:
https://en.cppreference.com/w/cpp/algorithm/accumulate

Or the new one
https://en.cppreference.com/w/cpp/algorithm/reduce

Regards

--
Cholo Lennon
Bs.As.
ARG

[Juha Nieminen]

Malcolm McLean <malcolm.ar...@gmail.com> wrote:
> template<class Iterator, typename func_t>
> typename Iterator::value_type reduce(Iterator start, Iterator end, func_t op )
> {
> typename Iterator::value_type answer = *start;
> start++;
> while (start != end)

This doesn't work for empty ranges. (Good design dictates that range-based
functions should always work on empty ranges, unless there's a very good
reason why they can't.)

Also you are needlessly copying the values. (With elementary types
that's not a problem, but with larger types it introduces needless
inefficiency. Of course it could be that this particular operation
simply cannot be done without copying the values, but I haven't
studied the problem you are trying to solve with enough detail
to know for certain it can be implemented without copying the
values around.)

[Bonita Montero]

I think this couldn't be more flexible:

#include <iterator>
#include <cassert>

template<typename Iterator, typename Func>
concept reduce_concept =
std::input_iterator<Iterator>
&&
requires( typename std::iterator_traits<Iterator>::value_type value,
Func func )
{
{ value = func( value, value ) };
};

template<typename Iterator, typename Func>
requires reduce_concept<Iterator, Func>
typename std::iterator_traits<Iterator>::value_type reduce( Iterator
begin, Iterator end, typename std::iterator_traits<Iterator>::value_type
init, Func func )
{
for( ; begin != end; ++begin )
init = func( init, *begin );
return init;
}

template<typename Iterator, typename Func>
requires reduce_concept<Iterator, Func>
&&
requires( typename std::iterator_traits<Iterator>::value_type value )
{
{ value = value };
}
typename std::iterator_traits<Iterator>::value_type reduce( Iterator
begin, Iterator end, Func func )
{
assert(begin != end);
using T = typename std::iterator_traits<Iterator>::value_type;
T init = *begin;
return reduce( ++begin, end, init, func );
}

#include <iostream>
#include <vector>
#include <random>

using namespace std;

int main()
{
vector<int> vi( 0x100 );
mt19937_64 mt;
uniform_int_distribution<int> uid( -256, 255 );
for( int &i : vi )
i = uid( mt );
cout << reduce( vi.begin(), vi.end(), []( int a, int b ) { return a +
b; } ) << endl;
}

[Bonita Montero]

> template<typename Iterator, typename Func>
> concept reduce_concept =
>     std::input_iterator<Iterator>
>     &&
>     requires( typename std::iterator_traits<Iterator>::value_type
> value, Func func )

requires( typename std::iterator_traits<Iterator>::value_type

&value, Func func )

[Bonita Montero]

> This doesn't work for empty ranges. (Good design dictates that range-based
> functions should always work on empty ranges, unless there's a very good
> reason why they can't.)

What sense should empty ranges make here if the result is always
dependent of the first element in a row ?

[Manfred]

You may drop "maybe".

According to
https://en.cppreference.com/w/cpp/algorithm/reduce

reduce(1) (the one with implicit init) is the "same as reduce(first,
last, typename std::iterator_traits<InputIt>::value_type{})"

which means that in the example above the result should be zero, instead
of 1.

[Manfred]

Which yields the trivial implementation:

#include <iostream>
#include <vector>

template<class Iterator, typename T, typename func_t>
typename Iterator::value_type reduce(Iterator start, Iterator end, T
init, func_t op )
{
typename Iterator::value_type answer = init;

for (; start != end; ++start)
{
answer = op(answer, *start);
}

return answer;

}

template<class Iterator, typename func_t>
typename Iterator::value_type reduce(Iterator start, Iterator end,
func_t op )
{

return reduce(start, end, typename Iterator::value_type{}, op);

}

int main()
{
const std::vector<double> array = { 1, 2, 3, 4};
double v = reduce(array.begin(), array.end(),
[](double a, double b){return a < b ? a : b;});
std::cout << "Result " << v << "\n";
return 0;
}


>>

[Juha Nieminen]

I don't think the standard std::reduce requires a non-empty range.

It's always good design that any function taking an iterator range support
empty ranges.