Standard C++ Library
Copyright 1998, Rogue Wave Software, Inc.
NAME
partial_sum
- Calculates successive partial sums of a range of values.
SYNOPSIS
#include <numeric>
template <class InputIterator, class OutputIterator>
OutputIterator partial_sum (InputIterator first,
InputIterator last,
OutputIterator result);
template <class InputIterator,
class OutputIterator,
class BinaryOperation>
OutputIterator partial_sum (InputIterator first,
InputIterator last,
OutputIterator result,
BinaryOperation binary_op);
DESCRIPTION
The partial_sum algorithm creates a new sequence in which
every element is formed by adding all the values of the pre-
vious elements, or, in the second form of the algorithm, by
applying the operation binary_op successively on every pre-
vious element. That is, partial_sum assigns to every itera-
tor i in the range [result, result + (last - first)) a
value equal to:
((...(*first + *(first + 1)) + ... ) +
*(first + (i - result)))
or, in the second version of the algorithm:
binary_op(binary_op(..., binary_op (*first,
*(first + 1)),...),*(first + (i - result)))
For instance, applying partial_sum to (1,2,3,4,) yields
(1,3,6,10).
The partial_sum algorithm returns result + (last - first).
If result is equal to first, the elements of the new
sequence successively replace the elements in the original
sequence, effectively turning partial_sum into an inplace
transformation.
COMPLEXITY
Exactly (last - first) - 1 applications of the default +
operator or binary_op are performed.
EXAMPLE
//
// partsum.cpp
//
#include <numeric> //for accumulate
#include <vector> //for vector
#include <functional> //for times
#include <iostream>
using namespace std;
int main()
{
//Initialize a vector using an array of ints
int d1[10] = {1,2,3,4,5,6,7,8,9,10};
vector<int> v(d1, d1+10);
//Create an empty vectors to store results
vector<int> sums((size_t)10), prods((size_t)10);
//Compute partial_sums and partial_products
partial_sum(v.begin(), v.end(), sums.begin());
partial_sum(v.begin(), v.end(), prods.begin(),
times<int>());
//Output the results
cout << "For the series: " << endl << " ";
copy(v.begin(),v.end(),
ostream_iterator<int,char>(cout," "));
cout << endl << endl;
cout << "The partial sums: " << endl << " " ;
copy(sums.begin(),sums.end(),
ostream_iterator<int,char>(cout," "));
cout <<" should each equal (N*N + N)/2" << endl << endl;
cout << "The partial products: " << endl << " ";
copy(prods.begin(),prods.end(),
ostream_iterator<int,char>(cout," "));
cout << " should each equal N!" << endl;
return 0;
}
Program Output
For the series:
1 2 3 4 5 6 7 8 9 10
The partial sums:
1 3 6 10 15 21 28 36 45 55 should each equal (N*N + N)/2
The partial products:
1 2 6 24 120 720 5040 40320 362880 3628800 should each
equal N!
WARNINGS
If your compiler does not support default template parame-
ters, then you always need to include the Allocator template
argument. For instance, you need to write:
vector<int, allocator<int> >
instead of:
vector<int>
If your compiler does not support namespaces, then you do
not need the using declaration for std.