stl中的几个精美算法

关于STL中的算法，我印象比较深刻的主要有用于list的sort、power以及用于random_access_iterator的qsort，list是一种bidirectional_iterator，因此设计了自己的一个sort算法，主要思想是mergesort。

首先看一下list中的sort:

template<class T, class Alloc>
void list<T, Alloc>::sort(){
	//这一段主要用于判断列表是否为空，或者只有一个节点
	if( node->next == node || link_type(node->next)->next == node )
		return;
	//一些新的lists,用于作为mergesort的中转区
	list<T, Alloc> carry;		//听这两个名字，就像二进制中的加减计算器，事实上我感觉跟它是有点关系的
	list<T, Alloc> counter[64];	//counter[i]里存放2^i个元素
	int fill = 0;			//fill用于记录到目前为止counter中不为空的那个最大的counter[i]的下标i+1（好绕啊）
	while( !empty() ){
		//把链表的头一个元素放到carry中去，作为carry的头一个元素
		//每次这个时候，carry都是为空的
		carry.splice( carry.begin(), *this, begin() );
		int i = 0;
		//就像二进制进位，一直进到遇到0的时候才停下来（对应这里的空列表）
		//或者是超出原先的最高位了，这时候i==fill，所以后面的fill就要加1了
		while( i<fill && !counter[i].empty() ){
			counter[i].merge(carry);
			carry.swap(counter[i++]);
		}//只有在这个while中才有可能出现counter[i]的元素个数大于i^2
		carry.swap( counter[i] );
		if( i==fill ) ++fill;
	}

	for( int i=1; i<fill; ++i )
		counter[i].merge(counter[i-1]);
	swap(counter[fill-1]);
}

list的整个过程就像我们对一个二进制x从0开始一步一步地加1，一开始x=0，第0位都是为空，所以counter[0]为空，fill为0，意思是说所有的counter[i]都为空。carry是中转站，代表一个1，但是它是第几位的，由i来标识。加入一个元素相当于一个加1操作，0+1=1，加完后counter[0]有一个元素，fill=1，没有进位，现在最高位在0位上。然后又加入一个元素，结果产生了进位，于是由carry来管理，现在i=1，所以应该把它加在counter[1]上，此时counter[1]为空（相当于为0），所以没有进位。整个过程就是这样，相当的过程就是一个mergesort的过程。不知道我讲明白了没。。

另一个比较有意思的是stl的power，例如我们现在要算x^7，其可以转换成下面的计算过程：
x^7 = (x^6)*x = ((x^3)^2)*x = (((x^2)*x)^2)*x
本来如果一个x一个x地去乘的话，需要乘以7次，转换成上面的算法，就只需要进行4次乘法。复杂度由O(n)降为O(lgn)。

template<class T>
T power( T x, int n ){
	if( n == 0 )
		return 1;
	while( (n&1) == 0 ){
		x = x*x;
		n >>= 1;
	}//把x^n转换成x^t的平方的平方的平方，直到n为0或n为奇数

	T result = x;		//现在，result=x^t，且n为奇数
	n >>= 1;
	while( n != 0 ){
		x = x*x;
		if( (n&1) != 0 )
			result *= x;
		n >>= 1;
	}
	return result;
}

我们都知道qsort是怎么回事，找一个pivot，以它为中值进行分区，以这个pivot为中界，一前一后，然后再对两个分区进行同样的操作，分而治之地将数组进行排序。理想情况下，算法的复杂度为O(lg(n))，可是不理想的情况下，理论上是O(n^2)，但是比起那些本来就是O(n^2)的排序算法要糟糕得多，因为它用的是递归。影响qsort性能的主要可以由下面几点来概括：
（1）pivot的选择，如果pivot不幸正好选到的是数组中最大的或最小的值，那么将形成一个空分区和一个n-1的分区，也就是说，整个过程就是找出了一个最大或最小值；因此在stl的内省快排introsort中，它用一个median_of_three来选择pivot，至少排除了空分区的情况；
（2）但是极端的说，可能会得到一个只有一个元素的分区和一个有n-2个幸免于难的分区，也就是分区效果还是不好，当检测到分割恶化时（因为比较好的情况下是递归了logn次，所以可以通过递归的深度来检测是否出现分区恶化的情况），转而使用heapsort，其实heapsort的复杂度也是O(logn)。
（3）对于大数组，递归的性价比比较高可是对于小数组还进行递归，性价比可能还不如那些复杂度为O(n^2)的非递归的什么insertsort之类的，所以当数组的长度低于某个阈值时，不再递归下去。由于通过qsort后数据的分布已经很好了，所以可以再用一个finnal_insertion_sort对其进行一次整合。这就是sgi stl中的introsort的故事，总的来说，它利用了median_of_three，heapsort和insertion_sort来优化qsort。我就不列出代码了。

这是stl中我印象比较深刻的几个算法。前几天去腾讯面试的时候，面试官问我，你看完stl源码后，印象最深刻的是什么？我当时脑子里就想起这几个算法来，当然，还有它的内存管理，以及利用萃取机制，为了效率，stl大师们真是无所不用其极啊。