partial_sum()

Library:  Numerics

Function

• Local Index
• Summary
• Synopsis
• Description
• Complexity
• Example
• See Also
• Standards Conformance

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

#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);
}

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.

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

//
//  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!

Algorithms, <algorithm>

ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 26.4.3