function template
<numeric>
std::partial_sum
sum (1) | template <class InputIterator, class OutputIterator>
OutputIterator partial_sum (InputIterator first, InputIterator last,
OutputIterator result);
|
---|
custom (2) | template <class InputIterator, class OutputIterator, class BinaryOperation>
OutputIterator partial_sum (InputIterator first, InputIterator last,
OutputIterator result, BinaryOperation binary_op);
|
---|
Compute partial sums of range
Assigns to every element in the range starting at result the partial sum of the corresponding elements in the range [first,last)
.
If x represents an element in [first,last)
and y represents an element in result, the ys can be calculated as:
y0 = x0
y1 = x0 + x1
y2 = x0 + x1 + x2
y3 = x0 + x1 + x2 + x3
y4 = x0 + x1 + x2 + x3 + x4
... ... ...
The default operation is to add the elements up, but a different operation can be specified as binary_op instead.
The behavior of this function template is equivalent to:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
|
template <class InputIterator, class OutputIterator>
OutputIterator partial_sum (InputIterator first, InputIterator last,
OutputIterator result)
{
if (first!=last) {
typename iterator_traits<InputIterator>::value_type val = *first;
*result = val;
while (++first!=last) {
val = val + *first; // or: val = binary_op(val,*first)
*++result = val;
}
++result;
}
return result;
}
| |
Parameters
- first, last
- Input iterators to the initial and final positions in a sequence. The range used is
[first,last)
, which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
- result
- Output iterator to the initial position in the destination sequence where the partial sums are stored. The range starts at result and shall have a size large enough to contain as many elements as the range above (
[first,last)
).
- binary_op
- Binary operation taking two elements of the type pointed by the InputIterator as arguments, and returning the result of the replacement for the sum operation.
This can either be a function pointer or a function object.
Return value
An iterator pointing to past the last element of the destination sequence where resulting elements have been stored, or result if [first,last)
is an empty range.
Example
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
|
// partial_sum example
#include <iostream> // std::cout
#include <functional> // std::multiplies
#include <numeric> // std::partial_sum
int myop (int x, int y) {return x+y+1;}
int main () {
int val[] = {1,2,3,4,5};
int result[5];
std::partial_sum (val, val+5, result);
std::cout << "using default partial_sum: ";
for (int i=0; i<5; i++) std::cout << result[i] << ' ';
std::cout << '\n';
std::partial_sum (val, val+5, result, std::multiplies<int>());
std::cout << "using functional operation multiplies: ";
for (int i=0; i<5; i++) std::cout << result[i] << ' ';
std::cout << '\n';
std::partial_sum (val, val+5, result, myop);
std::cout << "using custom function: ";
for (int i=0; i<5; i++) std::cout << result[i] << ' ';
std::cout << '\n';
return 0;
}
| |
Output:
using default partial_sum: 1 3 6 10 15
using functional operation multiplies: 1 2 6 24 120
using custom function: 1 4 8 13 19
|
Complexity
Linear in the distance between first and last, minus one (in number of additions or applications of binary_op).
Data races
The elements in the range [first,last)
are accessed (each object is accessed exactly once).
The elements in the range beginning at result are modified.
Exceptions
Throws if any of binary_op, the assignments or an operation on an iterator throws.
Note that invalid arguments cause undefined behavior.
See also
- accumulate
- Accumulate values in range (function template
)
- inner_product
- Compute cumulative inner product of range (function template
)
- adjacent_difference
- Compute adjacent difference of range (function template
)