std::partial_sum

Defined in header <numeric>

Defined in header `<numeric>`
template< class InputIt, class OutputIt > OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first );	(1)
template< class InputIt, class OutputIt, class BinaryOperation > OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first, BinaryOperation op );	(2)

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

(1)

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

(2)

Computes the partial sums of the elements in the subranges of the range [first, last) and writes them to the range beginning at d_first. The first version uses operator+ to sum up the elements, the second version uses the given binary function op, both applying std::move to their operands on the left hand side (since C++20).

Equivalent operation:

*(d_first)   = *first;
*(d_first+1) = *first + *(first+1);
*(d_first+2) = *first + *(first+1) + *(first+2);
*(d_first+3) = *first + *(first+1) + *(first+2) + *(first+3);
...

`op` must not have side effects.	(until C++11)
`op` must not invalidate any iterators, including the end iterators, or modify any elements of the range involved.	(since C++11)

Parameters

first, last	-	the range of elements to sum
d_first	-	the beginning of the destination range; may be equal to `first`
op	-	binary operation function object that will be applied. The signature of the function should be equivalent to the following: `Ret fun(const Type1 &a, const Type2 &b);` The signature does not need to have `const &`. The type `Type1` must be such that an object of type `iterator_traits<InputIt>::value_type` can be implicitly converted to `Type1`. The type `Type2` must be such that an object of type `InputIt` can be dereferenced and then implicitly converted to `Type2`. The type `Ret` must be such that an object of type `iterator_traits<InputIt>::value_type` can be assigned a value of type `Ret`.
Type requirements
-`InputIt` must meet the requirements of LegacyInputIterator.
-`OutputIt` must meet the requirements of LegacyOutputIterator.

Return value

Iterator to the element past the last element written.

Complexity

Exactly (last - first) - 1 applications of the binary operation.

Possible implementation

First version
template<class InputIt, class OutputIt> OutputIt partial_sum(InputIt first, InputIt last, OutputIt d_first) { if (first == last) return d_first; typename std::iterator_traits<InputIt>::value_type sum = first; d_first = sum; while (++first != last) { sum = std::move(sum) + first; // std::move since C++20 ++d_first = sum; } return ++d_first; // or, since C++14: // return std::partial_sum(first, last, d_first, std::plus<>()); }
Second version
template<class InputIt, class OutputIt, class BinaryOperation> OutputIt partial_sum(InputIt first, InputIt last, OutputIt d_first, BinaryOperation op) { if (first == last) return d_first; typename std::iterator_traits<InputIt>::value_type sum = first; d_first = sum; while (++first != last) { sum = op(std::move(sum), first); // std::move since C++20 ++d_first = sum; } return ++d_first; }

First version

template<class InputIt, class OutputIt>
OutputIt partial_sum(InputIt first, InputIt last, 
                     OutputIt d_first)
{
    if (first == last) return d_first;
 
    typename std::iterator_traits<InputIt>::value_type sum = *first;
    *d_first = sum;
 
    while (++first != last) {
       sum = std::move(sum) + *first; // std::move since C++20
       *++d_first = sum;
    }
    return ++d_first;
 
    // or, since C++14:
    // return std::partial_sum(first, last, d_first, std::plus<>());
}

Second version

template<class InputIt, class OutputIt, class BinaryOperation>
OutputIt partial_sum(InputIt first, InputIt last, 
                     OutputIt d_first, BinaryOperation op)
{
    if (first == last) return d_first;
 
    typename std::iterator_traits<InputIt>::value_type sum = *first;
    *d_first = sum;
 
    while (++first != last) {
       sum = op(std::move(sum), *first); // std::move since C++20
       *++d_first = sum;
    }
    return ++d_first;
}

Example

#include <numeric>
#include <vector>
#include <iostream>
#include <iterator>
#include <functional>
 
int main()
{
    std::vector<int> v = {2, 2, 2, 2, 2, 2, 2, 2, 2, 2}; // or std::vector<int>v(10, 2);
 
    std::cout << "The first 10 even numbers are: ";
    std::partial_sum(v.begin(), v.end(), 
                     std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
 
    std::partial_sum(v.begin(), v.end(), v.begin(), std::multiplies<int>());
    std::cout << "The first 10 powers of 2 are: ";
    for (auto n : v) {
        std::cout << n << " ";
    }
    std::cout << '\n';
}

Output:

The first 10 even numbers are: 2 4 6 8 10 12 14 16 18 20 
The first 10 powers of 2 are: 2 4 8 16 32 64 128 256 512 1024

adjacent_difference	computes the differences between adjacent elements in a range (function template)
accumulate	sums up a range of elements (function template)
inclusive_scan (C++17)	similar to `std::partial_sum`, includes the ith input element in the ith sum (function template)
exclusive_scan (C++17)	similar to `std::partial_sum`, excludes the ith input element from the ith sum (function template)