STL源码剖析之——数值算法

C++ STL 的数值算法(Numeric algorithms)是一组对容器元素进行数值计算的模板函数，包括容器元素求和 accumulate 、两序列元素的内积 inner_product 、容器元素的一系列部分元素和 partial_sum 、容器每对相邻元素的差adjacent_difference。

1、accumulate

/*
*	函数名：	accumulate
*	功能：    将指定区间内的元素累加
*/
// 版本1，算法缺省行为
template <class InputIterator,class T>
T accumulate(InputIterator first, InputIterator last, T init)
{
	for (; first != last; first++)
	{
		init = init + *first;	
	}
	return init;
}

// 版本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;
}

2、adjacent_differencee

/*
*	函数名：	adjacent_differencee
*	功能：	计算[first,last)中相邻元素的差额，首元素内容不变
*	说明：	与partial_sum互为逆运算
*/
// 版本1，算法缺省行为
template <class InputIterator, class OutputIterator>
OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result)
{
	if (first == last)
	{
		return result;	// 区间内容为空直接返回result
	}
	*result = *first;	// 首先记录第一个元素(即原容器中第一个元素内容不变)
	iterator_traits<InputIterator>::value_type value = *first;
	while (++first != last)	// 之后的元素为本位置-前一个位置的值
	{
		T tmp = *first;
		*++first = tmp - value;
		value = tmp;
	}
	return ++result;
}

// 版本2，接收外界传入一个仿函数
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
	}
	*result = *first;	// 首先记录第一个元素(即原容器中第一个元素内容不变)
	iterator_traits<InputIterator>::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 <class InputIterator, class OutputIterator>
OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result)
{
	if (first == last)
	{
		return result;	// 区间内容为空直接返回result
	}
	*result = *first;	// 首先记录第一个元素(即原容器中第一个元素内容不变)
	iterator_traits<InputIterator>::value_type value = *first;
	while (++first != last)	// 之后的元素为本位置+前一个位置的值
	{
		value = value + *first;
		*++result = value;
	}
	return ++result;
}

// 版本2，接收外界传入一个仿函数
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
	}
	*result = *first;	// 首先记录第一个元素(即原容器中第一个元素内容不变)
	iterator_traits<InputIterator>::value_type value = *first;
	while (++first != last)	
	{
		value = binary_op(value, *first);
		*++result = value;
	}
	return ++result;
}

4、power

考虑x^23，可以先从x ->x^2 -> x^4 -> x^8 -> x^16 取result1 = x^16，然后23-16=7。
我们只要计算x^7再与result1相乘就可以得到x^23。对于x^7也可以采用这种方法

取result2 = x^4，然后7-4=3，只要计算x^3再与result2相乘就可以得到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)。

此函数可以在相乘O(logN)次内计算x的n次幂，且避免了重复计算。但还可以作进一步的优化，如像48=110000(二进制)这种低位有很多0的数，可以先过滤掉低位的0再进行计算，这样也会提高一些效率。程序如下：

参考来源：https://blog.csdn.net/morewindows/article/details/7174143

/*
*	函数名：	power
*	功能：	对自己进行某种运算n次，缺省值是乘方
*/
// 版本1，算法缺省行为
template <class T, class Integer>
inline T power(T x, Integer n)
{
	return power(x,n,multiplies<T>());	// multiplies<T>()是一个仿函数的临时对象，意为相乘
}

// 版本2，如果指定为乘方运算，则当n >= 0时返回x^n
// MonoidOperation必须满足结合律，可不满足交换律
template <class T, class Integer, class MonoidOperation op>
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 <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;
}

template <class InputIterator1, class InputIterator2, 
		class BinaryOperation1, class BinaryOperation2, class T>
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 <class ForwardIterator, class T>
void iota(ForwardIterator first, ForwardIterator last, T value)
{
	while (first != last)
	{
		*first = value++;
	}
}