blob: 1505d557bcd1676dd668336e06e195e4e70869b2 [file] [log] [blame]
 partial_sum()
Apache C++ Standard Library Reference Guide

partial_sum()

Library:  Numerics

Function

Local Index

No Entries

Summary

Generalized numeric operation that calculates successive partial sums of a range of values

Synopsis

#include <numeric>

namespace std {
template <class InputIterator, class OutputIterator>
OutputIterator partial_sum(InputIterator start,
InputIterator finish,
OutputIterator result);

template <class InputIterator,
class OutputIterator,
class BinaryOperation>
OutputIterator partial_sum(InputIterator start,
InputIterator finish,
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 previous elements, or, in the second form of the algorithm, by applying the operation binary_op successively on every previous element. That is, partial_sum() assigns to every iterator i in the range [result, result + (finish - start)) a value equal to:

((...(*start + *(start + 1)) + ... ) +
*(start + (i - result)))

or, in the second version of the algorithm:

binary_op(binary_op(..., binary_op (*start,
*(start + 1)),...),*(start + (i - result)))

For instance, applying partial_sum() to (1,2,3,4,) yields (1,3,6,10).

The partial_sum() algorithm returns result + (finish - start).

If result is equal to start, the elements of the new sequence successively replace the elements in the original sequence, effectively turning partial_sum() into an inplace transformation.

Complexity

Exactly (finish - start) - 1 applications of the default + operator or binary_op are performed.

Example

//
//  partsum.cpp
//

#include <algorithm>  // for copy
#include <functional> // for multiplies
#include <iostream>   // for cout, endl
#include <iterator>   // for ostream_iterator
#include <numeric>    // for partial_sum
#include <vector>     // for vector

int main ()
{
typedef std::vector<int, std::allocator<int> > Vector;
typedef std::ostream_iterator<int, char,
std::char_traits<char> >
Iter;

// Initialize a vector using an array of integers.
const Vector::value_type a[] = { 1, 2, 3, 4, 5,
6, 7, 8, 9, 10 };
Vector v (a + 0, a + sizeof a / sizeof *a);

// Create an empty vectors to store results.
Vector sums  (Vector::size_type (10));
Vector prods (Vector::size_type (10));

// Compute partial_sums and partial_products.
std::partial_sum (v.begin (), v.end (), sums.begin ());
std::partial_sum (v.begin (), v.end (), prods.begin (),
std::multiplies<Vector::value_type>());

// Output the results.
std::cout << "For the series: \n     ";
std::copy (v.begin (), v.end (), Iter (std::cout, " "));

std::cout << "\n\nThe partial sums: \n     ";
std::copy (sums.begin (), sums.end (), Iter (std::cout,
" "));
std::cout << " should each equal (N*N + N)/2\n\n";

std::cout << "The partial products: \n     ";
std::copy (prods.begin (), prods.end (), Iter (std::cout,
" "));
std::cout << " should each equal N!" << std::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!