stlのいくつかの美しいアルゴリズム

STLのアルゴリズムについては、主にlist用のsort、パワー、そしてラドム用のアルゴリズムが印象的です.access_iteratorのqsort、listはbidirectionalです.iteratorは、そのために自分のsortアルゴリズムを設計しました.主な思想はmergsortです.
まずリストの中の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のプロセス全体は、私たちが1つのバイナリ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]は空です.全体の過程はこのようにして、かなりの過程は1つのmergsortの過程です.分かりません.分かりましたか?
もう一つの面白いのはstlのパワーです.例えば、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を中の境界として、前の1つの後に、もう2つのパーティションを同じ操作して、分割して配列を並べ替えます.理想的には、アルゴリズムの複雑さはO(lg(n)であるが、理想的でない場合は、理論的にはO(n^2)であるが、それよりもむしろO(n^2)の順序付けアルゴリズムのほうがはるかに悪い.qsortの性能に影響するのは主に以下の点で要約できます.
(1)ピvotの選択は、もしピvotが不幸にも配列の中で最大または最小の値を選択した場合、空いているパーティションとn−1のパーティションを形成します.つまり、全プロセスは最大または最小値を探し出しました.だからstlの内省庁の高速の列のintrsortの中で、それは1つのmedianを使います.of_threeはpivotを選択し、少なくとも空いているパーティションを除外した場合.
(2)ただし、極端に言えば、一つの要素しかないパーティションとn-2個のパーティションを得ることができます.つまり、パーティションの効果はやはりよくないです.分割が悪化したことを検出した場合(良い場合は、logn回に戻りますので、転送の深さでパーティションが悪化したかどうかを検出できます.)は、heappsortを使用します.実はheappsortの複雑さもOです.
(3)大きな配列に対しては、再帰的な価格比は比較的高いが、小さい配列に対しては再帰的であり、価格性能比はまだそれらの複雑度がO(n^2)の再帰的でない何かのinsertsortなどに及ばないかもしれないので、配列の長さがある閾値を下回る場合は再帰しない.Qsortを通してデータの分布がよくなりましたので、もう一つfinnalを使ってもいいです.insertion_ソトはそれを統合します.これはsgi stlのintrocsortの物語で、総じて言えば、median_を利用しています.of_three、heappsortとinsertion_そしてqsortを最適化します.コードのリストを書きません.
これはstlの中で印象的ないくつかのアルゴリズムです.先日テンセントに面接に行った時、面接官からstlのソースコードを見た後、一番印象に残ったのは何ですか?私はこのいくつかのアルゴリズムを頭の中で思い出しました.もちろん、メモリ管理や抽出メカニズムを利用して、効率のために、stl大家たちは本当に何も使いませんでした.