STLソース分析の――数値アルゴリズム

C++STLの数値アルゴリズム(Numeric algorithms)は、コンテナ要素を数値的に計算するテンプレート関数のセットであり、コンテナ要素求和accumulate、2つのシーケンス要素の内積inner_Product、コンテナ要素の一連の部分要素とpartial_sum、コンテナの隣接する要素のペアごとの差adjacent_difference.
1、accumulate

/*
*	   ：	accumulate
*	  ：               
*/
//   1，      
template 
T accumulate(InputIterator first, InputIterator last, T init)
{
	for (; first != last; first++)
	{
		init = init + *first;	
	}
	return init;
}

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

2、adjacent_differencee

/*
*	   ：	adjacent_differencee
*	  ：	  [first,last)        ，       
*	  ：	 partial_sum     
*/
//   1，      
template 
OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result)
{
	if (first == last)
	{
		return result;	//           result
	}
	*result = *first;	//          (              )
	iterator_traits::value_type value = *first;
	while (++first != last)	//          -       
	{
		T tmp = *first;
		*++first = tmp - value;
		value = tmp;
	}
	return ++result;
}

//   2，           
template 
OutputIterator adjacent_difference(InputIterator first, InputIterator last, 
									OutputIterator result, BinaryOperation binary_op)
{
	if (first == last)
	{
		return result;	//           result
	}
	*result = *first;	//          (              )
	iterator_traits::value_type value = *first;
	while (++first != last)	
	{
		T tmp = *first;
		*++first = binary_op(tmp, value);
		value = tmp;
	}
	return ++result;
}

3、partial_sum

/*
*	   ：	partial_sum
*	  ：	  [first,last)        ，       
*	  ：	 adjacent_difference     
*/
//   1，      
template 
OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result)
{
	if (first == last)
	{
		return result;	//           result
	}
	*result = *first;	//          (              )
	iterator_traits::value_type value = *first;
	while (++first != last)	//          +       
	{
		value = value + *first;
		*++result = value;
	}
	return ++result;
}

//   2，           
template 
OutputIterator partial_sum(InputIterator first, InputIterator last, 
							OutputIterator result, BinaryOperation binary_op)
{
	if (first == last)
	{
		return result;	//           result
	}
	*result = *first;	//          (              )
	iterator_traits::value_type value = *first;
	while (++first != last)	
	{
		value = binary_op(value, *first);
		*++result = value;
	}
	return ++result;
}

4、power
x^23を考慮すると、result 1=x^16をx->x^2->x^4->x^8->x^16から取得し、23-16=7にすることができます.x^7を計算してresult 1に乗算すればx^23が得られる.x^7に対してもこの方法を採用することができる
result 2=x^4を取り、7-4=3をとり、x^3を計算してresult 2に乗算すればx^7が得られます.これにより、x^23をx^16*x^4*x^2*x、すなわち23=16+4+2+1、23=10111(バイナリ)と書くことができるので、nをバイナリ化して低位から高位まで順にi位が1であればresult*=x^(2^i)と判断する.
この関数は、xのn乗べき乗をO(logn)乗で計算し、繰り返し計算を回避することができる.しかし、48=10000(バイナリ)のような低位に0の数が多い場合は、低位の0をフィルタリングして計算することで、効率を向上させることもできる.手順は次のとおりです.
参照元:https://blog.csdn.net/morewindows/article/details/7174143

/*
*	   ：	power
*	  ：	         n ，      
*/
//   1，      
template 
inline T power(T x, Integer n)
{
	return power(x,n,multiplies());	// multiplies()           ，    
}

//   2，         ，  n >= 0   x^n
// MonoidOperation       ，       
template 
T power(T x, Integer n, MonoidOperation op)
{
	if (n == 0)	//     1  
	{
		return identity_element(op);	//       
	}
	else	//      0
	{
		while ((n & 1) == 0)
		{
			n >>= 1;	// n    
			x = op(x, x);	// x = x op 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;
}

5、inner_product

/*
*	   ：	inner_product
*	  ：	  [first1,last1) [first2,first2+(last1 - first1))     
*/
//   1，      
template 
T inner_product(InputIterator1 first1, InputIterator1 last1,
				InputIterator2 first2, T init)
{
	//         ，         
	for (; first1 != last1; ++first1, ++first2)
	{
		init = init + (*first1 * *first2);	//           
	}
	return init;
}

template 
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;
}

6、iota

/*
*	   ：	iota
*	  ：	   [first,last)  value,value+1,value+2,value+3
*/
template 
void iota(ForwardIterator first, ForwardIterator last, T value)
{
	while (first != last)
	{
		*first = value++;
	}
}