C++ STL（第十七篇：算法）

1、算法的概述

算法，就是一个问题的解法。以有限的步骤，解决逻辑或数学上的问题。STL 收录了极具复用价值的 70 个算法，包括和赫赫有名的排序、查找、排列、组合等。

有的算法需要搭配特定的数据结构。例如 binary search tree（二叉查找树）和 RB-tree 便是为了解决查找问题而发展出来的特殊数据结构，hashtable 拥有快速查找的能力。map-heap可以协助完成所谓的堆排序。

通常评价一个算法的好坏，是通过两个维度，时间复杂度 和 空间复杂度，这两个在整理 算法及其复杂度分析 中进行了详细的说明，这里就不赘述了。

算法也可以分为两大类，质变算法 和 非质变算法。

质变算法，是指运算过程中会更改区间内的元素内容。如拷贝（copy）、互换（swap）、替换（replace）、删除（remove）等。

非质变算法，是指运算过程中不会更改区间内的元素内容。如查找（find）、匹配（search）、计数（count）、巡访（for_each）、寻找极致（max，min）等。

2、算法的一般形式

所有的泛型算法的前面两个参数都是一对迭代器，通常称为 first 和 last，用以标示算法的操作区间。STL 习惯采用前闭后开区间表示法，写成 [first, last)，表示区间涵盖 first 与 last 之间的所有元素。 当 first == last 时，表示是一个空区间。

这个[first, last) 区间的必要条件是，必须能够通过累加操作，从 first 到达 last。编译器本身无法强求这一点，如果这个条件不成立，会导致未可预期的结果。

前面整理迭代器时，我们知道迭代器可分为 5 类。每一个 STL 算法的声明，都表现出它所要求的最低迭代器类型。例如，find() 需要一个 inputIterator，这是它的最低要求，但它也可以接受更高类型的迭代器。

许多 STL 算法不止支持一个版本。这一类算法的某个版本采用缺省运算行为，另一个版本提供额外参数，接受外界传入一个仿函数，以便采用其他策略。例如，unique() 缺省情况下使用equality操作符来比较两个相邻元素，但如果这些元素的型别并未提供 equality 操作符，或用户自定义 equality 操作符，便可以传一个仿函数给另一个版本 unique()。

质变算法通常提供两个版本：一个是 in-place（就地进行）版，就地改变其操作对象；另一个是 copy（另地进行）版，将操作对象的内容复制一份副本，然后在副本上进行修改并返回该副本。

下面就整理几个简单的算法，之后会对复杂的算法进行整理。

3、最简单算法（数值算法）

accumulate 计算区间内的总和，其参数 init 是用来明确定义的值，如果计算区间 first 与 last 之间的总和，可把 init 设为0。代码如下：

//版本1
template<class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init)
{
	for(;first != last; ++first)
		init = init + *first;				//将每个元素值累加到初值 init 身上
	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;
}
           

adjacent_difference 用来计算 [first, last) 中相邻元素的差额。其核心代码如下：

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

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

当然它也有第二个版本的函数，传入一个仿函数，这里就不做具体整理了。adjacent_difference 算法就是将 *first 赋值给 *result，并针对 [first+1, last) 内的每个迭代器 i，将 *i - *(i-1) 的值赋值给 *(result+(i - first))。

inner_product 计算 [first1, last1) 和 [first2, first2+(last1-first1)) 的一般内积。代码如下：

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

其中参数 init 和 accumulate 中的参数 init 一样，用来明确定义的结果。

partial_sum 用来计算局部总和。它会将 *first 赋值给 *result，将 *first 和 *(first+1) 的和赋值给 *(result+1)，依次类推。代码如下：

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

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

partial_sum 和 adjacent_difference 互为逆运算。如果对区间值 1,2,3,4,5 执行 partial_sum，结果为 1,3,6,10,15，在对此结果执行 adjacent_difference，获得原始区间值 1,2,3,4,5。

感谢大家，我是假装很努力的YoungYangD（小羊）。

参考资料：

《STL源码剖析》