STL sort関数の内部実装

(1)STLで提供される様々なアルゴリズムの中で、sort()は最も複雑で最も巨大な一つである.このアルゴリズムはRandom Access Iteratorsだけを受け入れて、区間内のすべての要素を小さい時から大きい時まで並べ替えます.第二のバージョンは、ユーザが自分で順序付け基準として擬似関数を指定することを可能にする.
(2)関係型容器については、下の階に自分で自動並べ替え機能があるRB-Treeを採用しています.sortアルゴリズムは不要です.シーケンス型容器にはstack、queue、prority_queueは容器アダプタであり、いずれも特別な出入り口があり、ユーザーがそれを並べ替えることができません.残りのvector、dequeとlistは、前の2つのローズマリーはRandomAccess Iteratorsに属しています.sortアルゴリズムを使うのに適しています.listのローズマリーはBidirection Iteratorsに属しています.STL標準の列にはないslistです.リストまたはslistを並べ替えるなら、彼らは自分でメンバーfunction sortを提供するべきです.じゃなぜ一般的なアルゴリズムsortはRandom Access Iteratorsを要求しますか?
(3)STLのsort()アルゴリズムでは、データ量が大きい場合はQuick Sortを採用し、区分的に再帰的に並べ替えます.区分後のデータ量がある閾値より小さいと、Quick Sortの再帰的な呼び出しによる過剰なオーバヘッドを避けるために、Insertion Sortに切り替える.再帰的なレベルが深ければ、Heap Sortに変更されます.
(4)Insertion Sortを持ってビッグデータ量を処理すれば、そのO(N^2)の複雑さは納得できません.大きいデータ量はより良いソートアルゴリズムがあります.選択できます.ファーストクラスは現在知られている最速のソート方法で、平均複雑度はO(N log N)で、最悪の場合はO(N^2)です.しかし、IntroSort(Median-of-three QuickSortのようなきわめて似た順序付けアルゴリズム)は最悪の状況をO(NlogN)に進めることができ、初期のSTL sortアルゴリズムはすべてQuickSortを採用し、SGI STLはすでにIntroSortに変更されました.
QuickSortの精神は大区間を小区間に分割し、区分を並べ替え、各団地間の並べ替えが完了した後、大区間を連結して並べ替えを完了することです.最悪の場合は分割時に空のサブ区間が発生しました.それは完全に分割の予想効果に達していません.
(5)Median-of-Three(3点中)
いずれの要素も枢軸として選択できますが、その適性は早送り効率に影響します.要素が最初に入力された時に、ランダムによる劣化効果が足りないことを避けるために、一番理想的なのは、シーケンス全体の頭、尾、中央の3つの位置に行く要素で、その中の値を軸としています.これはmedian-of-three Quicksortといいます.中央位置の元素を素早く取り出せるようにするためには、明らかにローズマリーがランダムに位置決めできる必要があります.つまり、Random Access Iteratorsならなければなりません.
(6)閾値thresold
わずか10個の要素しかない小型のシーケンスに対して、Quicksortのように複雑で大量の演算が必要な高速の順序は不経済に見える.したがって、小さいデータ量の場合は、InsertionSortもQuickSortを超える可能性があります.Quickは小さいサブシーケンスのために多くの関数を再帰的に呼び出します.
この場合、シーケンスのサイズを適度に評価し、InsertionSortを採用するか、それともQuickSortを採用するかを決定します.
ヒープの並べ替えの比較と交換の回数は速い並べ替えより多いので、平均的には速い並べ替えより遅いです.つまり定数因子は高速の並べ替えより大きいです.もし必要なのが「並べ替え」なら、ほとんどの場合は他のO(nlogn)アルゴリズムよりも高速の並べ替えが必要です.しかし、時にはあなたが欲しいのは「並べ替え」ではなく、他のいくつかの並べ替えに関するものです.例えば、最大/小さい元素、topKなど、この時に積み上げられた順位の優位性が出てきます.ヒープで並べ替えてN個の元素の中でtop Kを見つけることができます.時間の複雑さはO(N log K)です.空間が複雑なのはO(K)です.高速で並べ替えられた空間の複雑さはO(N)です.つまり、多くの元素の中でいくつかのtop Kの元素を見つけたいなら、或いは巨大なデータの中でtop Kを見つけます.もう一つはheapを使うのに適した優先順位であり、一連の更新が必要なデータの中で常に最大/小さい要素を探しています.また、merge sortなどのアルゴリズムもO(nlogn)ですが、一般的にはN-way mergeといった特殊な場面でしか使えません.N個の順序が整っているデータストリームを一つの順序のデータストリームに統合できます.もちろん、このアルゴリズムは厳密にはmerge sortとは言えません.その中のいくつかのステップを使っていますが、考え方は同じです.
交換ベースの並べ替えでよく使われているのはこのようないくつかです.他のものは交換ベースではない並べ替え、例えばradix sort、bucket sortなどです.
std:sortのコードは以下の通りです.

template <class RandomAccessIterator>
inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
    if (first != last) {
        __introsort_loop(first, last, value_type(first), __lg(last - first) * 2);
        __final_insertion_sort(first, last);
    }
}
template <class RandomAccessIterator, class T, class Size>
void __introsort_loop(RandomAccessIterator first,
                      RandomAccessIterator last, T*,
                      Size depth_limit) {
    while (last - first > __stl_threshold) {
        if (depth_limit == 0) {
            partial_sort(first, last, last);
            return;
        }
        --depth_limit;
        RandomAccessIterator cut = __unguarded_partition
          (first, last, T(__median(*first, *(first + (last - first)/2),
                                   *(last - 1))));
        __introsort_loop(cut, last, value_type(first), depth_limit);
        last = cut;
    }
}

再帰的深さ閾値
これから循環条件とif文に注目します.イントロソートloopの最後のパラメータdepth_limitは、前述したように、分割挙動が悪化傾向にあるかどうかを判断する閾値であり、すなわち再帰的な深さを許容し、調合者によって伝達される値は2 logNである.注意if文を見てください.再帰回数が閾値を超えた場合、関数はpartial_を呼び出します.ソト、それは積み上げ順序です.

template <class RandomAccessIterator, class T, class Compare>
void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
	RandomAccessIterator last, T*, Compare comp) {
	make_heap(first, middle, comp);
	for (RandomAccessIterator i = middle; i < last; ++i)
	if (comp(*i, *first))
		__pop_heap(first, middle, i, T(*i), comp, distance_type(first));
	sort_heap(first, middle, comp);
}

template <class RandomAccessIterator, class Compare>
inline void partial_sort(RandomAccessIterator first,
	RandomAccessIterator middle,
	RandomAccessIterator last, Compare comp) {
	__partial_sort(first, middle, last, value_type(first), comp);
}

前述したように、このとき、ヒープ順序を採用することによって、急速な順序付けの効率がO(N 2)からO(N logN)に引き上げられ、過度の再帰によるオーバヘッドがなくなる.ヒープの並べ替えが終わったら、現在の再帰を直接終了します.

template <class RandomAccessIterator, class T>
RandomAccessIterator __unguarded_partition(RandomAccessIterator first,
	RandomAccessIterator last,
	T pivot) {
	while (true) {
		while (*first < pivot) ++first;
		--last;
		while (pivot < *last) --last;
		if (!(first < last)) return first;
		iter_swap(first, last);
		++first;
	}
}

Insertion Sort(挿入ソート)
同じように挿入並べ替えです.insertion_ソトとウウungurarded_insertion_sortは何が違っていますか?どうしてungardedといいますか?STLの実装を見てみます.

template <class RandomAccessIterator, class T>
void __unguarded_linear_insert(RandomAccessIterator last, T value) {
	RandomAccessIterator next = last;
	--next;
	while (value < *next) {
		*last = *next;
		last = next;
		--next;
	}
	*last = value;
}

template <class RandomAccessIterator, class T>
inline void __linear_insert(RandomAccessIterator first,
	RandomAccessIterator last, T*) {
	T value = *last;
	if (value < *first) {
		copy_backward(first, last, last + 1);
		*first = value;
	}
	else
		__unguarded_linear_insert(last, value);
}

template <class RandomAccessIterator>
void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
	if (first == last) return;
	for (RandomAccessIterator i = first + 1; i != last; ++i)
		__linear_insert(first, i, value_type(first));
}

同前finalinsertion_ソフト

template <class RandomAccessIterator>
void __final_insertion_sort(RandomAccessIterator first,
	RandomAccessIterator last) {
	if (last - first > __stl_threshold) {
		__insertion_sort(first, first + __stl_threshold);
		__unguarded_insertion_sort(first + __stl_threshold, last);
	}
	else
		__insertion_sort(first, last);
}
template <class RandomAccessIterator, class T>
void __unguarded_insertion_sort_aux(RandomAccessIterator first,
	RandomAccessIterator last, T*) {
	for (RandomAccessIterator i = first; i != last; ++i)
		__unguarded_linear_insert(i, T(*i));
}

template <class RandomAccessIterator>
inline void __unguarded_insertion_sort(RandomAccessIterator first,
	RandomAccessIterator last) {
	__unguarded_insertion_sort_aux(first, last, value_type(first));
}

詳細住所を添付します.http://www.udpwork.com/item/12284.html