std::partial_sum

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)

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.

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 ranges involved.	(since C++11)

Parameters

first, last	-	the range of elements to sum
d_first	-	the beginning of the destination range
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 `InputIterator`.
- `OutputIt` must meet the requirements of `OutputIterator`.

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 = sum + *first;
       *++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(sum, *first);
       *++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 (parallelism TS)	similar to `std::partial_sum`, includes the ith input element in the ith sum (function template)
exclusive_scan (parallelism TS)	similar to `std::partial_sum`, excludes the ith input element from the ith sum (function template)

Links:

http://en.cppreference.com/w/cpp/algorithm/partial_sum

doc_CPP

2025-01-10 15:47:30

Comments