C++ STL源码学习之算法篇(二)
irst, __middle, bidirectional_iterator_tag()); __reverse(__middle, __last, bidirectional_iterator_tag()); while (__first != __middle && __middle != __last) swap (*__first++, *--__last); if (__first == __middle) { ///__middle之前元素较少，因此需要将__middle,__last区间 ///（此区间未被交换）翻转到原来的顺序 __reverse(__middle, __last, bidirectional_iterator_tag()); return __last; } else { __reverse(__first, __middle, bidirectional_iterator_tag()); return __first; } } template
_RandomAccessIter __rotate(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, _Distance *, _Tp *) { _Distance __n = __last - __first; ///总元素数 _Distance __k = __middle - __first; ///__middle之前的元素数(不包括__middle) _Distance __l = __n - __k; ///__middle之后的元素数 _RandomAccessIter __result = __first + (__last - __middle); ///new middle if (__k == 0) return __last; else if (__k == __l) { ///__middle前后元素数目相同 swap_ranges(__first, __middle, __middle); return __result; } _Distance __d = __gcd(__n, __k); ///__d是__middle之前元素数和总元素数的最大公约数 for (_Distance __i = 0; __i < __d; __i++) { ///循环__d次即可 _Tp __tmp = *__first; _RandomAccessIter __p = __first; if (__k < __l) { ///__middle前面的元素数目小于后面 for (_Distance __j = 0; __j < __l/__d; __j++) { if (__p > __first + __l) { ///__p在new middle 之后 *__p = *(__p - __l); ///*(__p - __l)应该放在__p所在位置 __p -= __l; ///将__p退后__l } *__p = *(__p + __k); ///__p在new middle 之前时，这个赋值永远是精准地 __p += __k; } } else { for (_Distance __j = 0; __j < __k/__d - 1; __j ++) { if (__p < __last - __k) { *__p = *(__p + __k); __p += __k; } *__p = * (__p - __l); __p -= __l; } } *__p = __tmp; ++__first; ///每次循环将__first增1 } return __result; } /// partition, stable_partition, and their auxiliary functions template
_ForwardIter __partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred, forward_iterator_tag) { if (__first == __last) return __first; while (__pred(*__first)) ///找到第一个不符合条件的元素 if (++__first == __last) return __first; _ForwardIter __next = __first; while (++__next != __last) if (__pred(*__next)) { ///找到符合条件的next将其交换到前面 swap(*__first, *__next); ++__first; } return __first; } ///克服了前面由于forward_iter的限制而产生的重复交换 template
_BidirectionalIter __partition(_BidirectionalIter __first, _BidirectionalIter __last, _Predicate __pred, bidirectional_iterator_tag) { while (true) { while (true) if (__first == __last) return __first; else if (__pred(*__first)) ++__first; else break; --__last; while (true) if (__first == __last) return __first; else if (!__pred(*__last)) --__last; else break; iter_swap(__first, __last); ++__first; } } ///调用此函数需保证*__first<=__pivot<=*(__last-1),因为有这个前提条件 ///所以不需要判断是否越界 template
_RandomAccessIter __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last, _Tp __pivot) { while (true) { while (*__first < __pivot) ++__first; --__last; while (__pivot < *__last) --__last; if (!(__first < __last)) return __first; iter_swap(__first, __last); ++__first; } } ///STL sort函数，为了高效，可谓是把基本的排序算法都用到了 ///其主体采用快速排序和插入排序，当快速排序的效率变得不可接受时 ///采用堆排序。当划分的子区间小于等于一定程度(即下面的_stl_threshold)时 ///退出快速排序，留给最后的插入排序处理 ///下面是他的一些辅助函数和他本身的实现 const int __stl_threshold = 16; /// sort() and its auxiliary functions. ///插入函数：是插入排序的辅助函数 ///调用此函数同样必须保证*__first<__val,其中__first没有显式出现 ///因此，同样不需要判断越界 template
void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) { _RandomAccessIter __next = __last; --__next; while (__val < *__next) { *__last = *__next; __last = __next; --__next; } *__last = __val; } template
inline void __linear_insert(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*) { _Tp __val = *__last; if (__val < *__first) { copy_backward(__first, __last, __last + 1); *__first = __val; } else __unguarded_linear_insert(__last, __val); } ///插入排序，是排序的规模小到一定程度时采用的排序方法 template
void __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) { if (__first == __last) return; for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) __linear_insert(__first, __i, __VALUE_TYPE(__first)); } ///插入排序，此时必须保证*__first是最小值 template
void __unguarded_insertion_sort_aux(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*) { for (_RandomAccessIter __i = __first; __i != __last; ++__i) __unguarded_linear_insert(__i, _Tp(*__i)); } template
inline void __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) { __unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first)); } ///对部分排序的区间进行最后的整体排序 template
void __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) { if (__last - __first > __stl_threshold) { ///长度大于16时，对前面的16个元素进行_insertion_sort后 ///对后续元素则可直接调