c++numericstl-algorithmc++17

What's the difference between std::partial_sum and std::inclusive_scan?


While reading about std::inclusive_scan, there does not appear to be any examples.
It strikes me as very similar to std::partial_sum.

partial_sum:

template< class InputIt, class OutputIt >
OutputIt partial_sum( InputIt first,
                      InputIt last, OutputIt d_first );

inclusive_scan:

template< class InputIt, class OutputIt >
OutputIt inclusive_scan( InputIt first,
                         InputIt last, OutputIt d_first );

Can someone elaborate on their differences? When would I choose one over the other?


Solution

  • Documentation of std::inclusive_scan states:

    In other words, the summation operations may be performed in arbitrary order. The behavior is nondeterministic if binary_op is not associative.

    Documentation of std::partial_sum states without any reservation that:

    *(d_first+k) = *first + *(first+1) + ... + *(first+k);
    

    Thus, std::inclusive_scan is equivalent to std::partial_sum only if binary_op is associative, i.e. when (aopb)opc = aop(bopc).

    In case of non-associative binary_op, std::partial_sum will produce a deterministic result, whereas you don't know what to expect from std::inclusive_scan.