<numeric>数値演算アルゴリズムひとめぐり

accumulate：総和

　accumulateはコンテナの総和を求めます。

list-5

int x[10];
iota(x, x+10, 1); // x[] = { 1, 2, 3, …… 10 }
int sum = accumulate(x, x+10, 0); // sum = 0 + 1 + 2 + ,,, 10

　accumulateのプロトタイプは二通り：

template<class InputIterator, class T> 
T accumulate(InputIterator first, InputIterator last, T init);

template<class InputIterator, class T, class BinaryOperation> 
T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op);

　後者は加算（operator+）に相当する二項関数オブジェクトを第4引数に与えます。2つの整数の比：a/bで現される有理数：rationalを定義し、rational列の総和をaccumulateで求めてみましょう：

list-6　rational.h

#ifndef RATIONAL_H_
#define RATIONAL_H_

#include <utility>

// 有理数:rational（first/second）
template<typename T=long> using rational = std::pair<T,T>;

// 分子（numerator） と 分母（denominator）
template<typename T>T inline numerator(const rational<T>& r)   { return r.first; }
template<typename T>T inline denominator(const rational<T>& r) { return r.second; }

// 最大公約数
template<typename T>
T gcd(T m, T n) { 
  if ( m < n ) { T t = m; m = n; n = t; }
  while ( n != T(0) ) {
    T t = m % n;
    m = n;
    n = t;
  }
  return m;
}

// 有理数の簡約化 
template<typename T>
rational<T> reduce(T num, T den) {
  if ( num == T(0) ) {
    return rational<T>(T(0),T(1));
  }
  bool neg = false;
  if ( den < T(0) ) { num = -num; den = -den; }
  if ( num < T(0) ) { num = -num; neg = true; }
  T g = gcd(num, den);
  return rational<T>(neg ? -num/g : num/g, den/g);
}

template<typename T>
inline rational<T> reduce(const rational<T>& r) 
  { return reduce(numerator(r), denominator(r)); }

// 簡約化したrationalを作る
template<typename T>
inline rational<T> make_rational(T num, T den = T(1)) { return reduce(num, den); }

#endif

list-7　rationalの総和

#include <numeric>
#include <vector>
#include <iostream>

#include "rational.h"
#include "sequence.h"

template<typename T>
std::ostream& operator<<(std::ostream& stream, const rational<T>& r) 
  { return stream << '(' << r.first << '/' << r.second << ')'; }

using namespace std;

int main() {
  const unsigned int N = 16;
  vector<rational<>> c(N, make_rational(0L));
  // c[] = 1/2, 1/4, 1/8 …… 1/65536
  iota(begin(c), end(c),
       sequence<rational<>>(make_rational(1L,2L), 
       [](const rational<>& x) 
         { return make_rational(numerator(x),denominator(x)*2L); }));

  // 総和を求める
  rational<> sum = accumulate(begin(c), end(c), make_rational(0L), 
              [](const rational<>& a, const rational<>& b) // 有理数の和 
                { return make_rational(numerator(a)*denominator(b) + numerator(b)*denominator(a),
                                       denominator(a)*denominator(b)); });
  cout << sum << endl; // (65535/65536)

}