STLソース解析アルゴリズムstl_numeric.h

この記事はsenlieオリジナルです。転載はこの住所を残してください。http://blog.csdn.net/zhengsenlie
説明、ソースコード、例のversion 1：通常の操作バージョンversion 2：汎化操作バージョン1.accumutlate説明：initとfirst、lastのすべての要素の合計のソースコードを計算します。

//version 1
template <class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init) {
  for ( ; first != last; ++first)
    init = init + *first;
  return init;
}


//version 2
template <class InputIterator, class T, class BinaryOperation>
T accumulate(InputIterator first, InputIterator last, T init,
             BinaryOperation binary_op) {
  for ( ; first != last; ++first)
    init = binary_op(init, *first);
  return init;
}

例:

int main()
{
  int A[] = {1, 2, 3, 4, 5};
  const int N = sizeof(A) / sizeof(int);


  cout << "The sum of all elements in A is " 
       << accumulate(A, A + N, 0) // 15
       << endl;


  cout << "The product of all elements in A is "
       << accumulate(A, A + N, 1, multiplies<int>()) //120
       << endl;
}

2.inneranner uplroduct
記述：計算[first 1,last 1]と[first 2,first 2+(last 1-first 1)の内部積 
ソース:

//version 1
template <class InputIterator1, class InputIterator2, class T>
T inner_product(InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, T init) {
  for ( ; first1 != last1; ++first1, ++first2)
    init = init + (*first1 * *first2);
  return init;
}


//version 2
template <class InputIterator1, class InputIterator2, class T,
          class BinaryOperation1, class BinaryOperation2>
T inner_product(InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, T init, BinaryOperation1 binary_op1,
                BinaryOperation2 binary_op2) {
  for ( ; first1 != last1; ++first1, ++first2)
    init = binary_op1(init, binary_op2(*first1, *first2));
  return init;
}

例:

int main()
{
  int A1[] = {1, 2, 3};
  int A2[] = {4, 1, -2};
  const int N1 = sizeof(A1) / sizeof(int);


  cout << "The inner product of A1 and A2 is " 
       << inner_product(A1, A1 + N1, A2, 0) //0
       << endl;
}

3.partial_sum
説明：局所総和を計算します。
ソース:

//version 1
template <class InputIterator, class OutputIterator, class T>
OutputIterator __partial_sum(InputIterator first, InputIterator last,
                             OutputIterator result, T*) {
  T value = *first;
  while (++first != last) {
    value = value + *first;
    *++result = value;
  }
  return ++result;
}


template <class InputIterator, class OutputIterator>
OutputIterator partial_sum(InputIterator first, InputIterator last,
                           OutputIterator result) {
  if (first == last) return result;
  *result = *first;
  return __partial_sum(first, last, result, value_type(first));
}


//version 2
template <class InputIterator, class OutputIterator, class T,
          class BinaryOperation>
OutputIterator __partial_sum(InputIterator first, InputIterator last,
                             OutputIterator result, T*,
                             BinaryOperation binary_op) {
  T value = *first;
  while (++first != last) {
    value = binary_op(value, *first);
    *++result = value;
  }
  return ++result;
}


template <class InputIterator, class OutputIterator, class BinaryOperation>
OutputIterator partial_sum(InputIterator first, InputIterator last,
                           OutputIterator result, BinaryOperation binary_op) {
  if (first == last) return result;
  *result = *first;
  return __partial_sum(first, last, result, value_type(first), binary_op);
}

例:

int main()
{
  const int N = 10;
  int A[N];


  fill(A, A+N, 1);
  cout << "A:                 ";
  copy(A, A+N, ostream_iterator<int>(cout, " ")); // 1 2 3 4 5 6 7 8 9 10
  cout << endl; 


  cout << "Partial sums of A: ";
  partial_sum(A, A+N, ostream_iterator<int>(cout, " ")); // 1 3 6 10 15 21 28 36 45 55
  cout << endl;
}  

4.adjacent＿udference
説明：隣接元素の差額を計算する。
ソース:

//version 1
template <class InputIterator, class OutputIterator, class T>
OutputIterator __adjacent_difference(InputIterator first, InputIterator last, 
                                     OutputIterator result, T*) {
  T value = *first;
  while (++first != last) {
    T tmp = *first;
    *++result = tmp - value;
    value = tmp;
  }
  return ++result;
}


template <class InputIterator, class OutputIterator>
OutputIterator adjacent_difference(InputIterator first, InputIterator last, 
                                   OutputIterator result) {
  if (first == last) return result;
  *result = *first;
  return __adjacent_difference(first, last, result, value_type(first));
}


//version 2
template <class InputIterator, class OutputIterator, class T, 
          class BinaryOperation>
OutputIterator __adjacent_difference(InputIterator first, InputIterator last, 
                                     OutputIterator result, T*,
                                     BinaryOperation binary_op) {
  T value = *first;
  while (++first != last) {
    T tmp = *first;
    *++result = binary_op(tmp, value);
    value = tmp;
  }
  return ++result;
}


template <class InputIterator, class OutputIterator, class BinaryOperation>
OutputIterator adjacent_difference(InputIterator first, InputIterator last,
                                   OutputIterator result,
                                   BinaryOperation binary_op) {
  if (first == last) return result;
  *result = *first;
  return __adjacent_difference(first, last, result, value_type(first),
                               binary_op);
}

例:

int main()
{
  int A[] = {1, 4, 9, 16, 25, 36, 49, 64, 81, 100};
  const int N = sizeof(A) / sizeof(int);
  int B[N];


  cout << "A[]:         ";
  copy(A, A + N, ostream_iterator<int>(cout, " ")); //1 4 9 16 25 36 49 64 81 100
  cout << endl;
  
  adjacent_difference(A, A + N, B);
  cout << "Differences: ";
  copy(B, B + N, ostream_iterator<int>(cout, " ")); // 3 5 7 9 11 13 15 17 19
  cout << endl;


  cout << "Reconstruct: ";
  partial_sum(B, B + N, ostream_iterator<int>(cout, " ")); //1 4 9 16 25 36 49 64 81 100
  cout << endl;
}

5.パワー 
説明：ある数のn乗乗次を計算します。SGIは専属的で、STL規格ではありません。
ソース:

// Returns x ** n, where n >= 0.  Note that "multiplication"
//  is required to be associative, but not necessarily commutative.
    
template <class T, class Integer, class MonoidOperation>
T power(T x, Integer n, MonoidOperation op) { //      Russian Peasant Algorithm
  if (n == 0)
    return identity_element(op);
  else {
    while ((n & 1) == 0) {
      n >>= 1;
      x = op(x, x);
    }


    T result = x;
    n >>= 1;
    while (n != 0) {
      x = op(x, x);
      if ((n & 1) != 0)
        result = op(result, x);
      n >>= 1;
    }
    return result;
  }
}


template <class T, class Integer>
inline T power(T x, Integer n) {
  return power(x, n, multiplies<T>());
}

例:

int main() {
  cout << "2 ** 30 = " << power(2, 30) << endl;  // -->        。        power ，    include   <numeric> 
}

6.iota
説明：ある区間の内容を設定し、その内の各要素を指定されたvalue値からインクリメント状態にする。
ソース:

template <class ForwardIterator, class T>
void iota(ForwardIterator first, ForwardIterator last, T value) {
  while (first != last) *first++ = value++;
}

例:

int main()
{
  vector<int> V(10);


  iota(V.begin(), V.end(), 7);
  copy(V.begin(), V.end(), ostream_iterator<int>(cout, " ")); // 7 8 9 10 11 12 13 14 15 16
  cout << endl; 
}