C++ STL源码学习之算法篇(三)
用__unguarded_insertion_sort以提高效率 __insertion_sort(__first, __first + __stl_threshold); __unguarded_insertion_sort(__first + __stl_threshold, __last); } else ///长度小于16时不必调用两次函数 __insertion_sort(__first, __last); } ///lg 2 为底 n的对数，用于计算一定长度的序列排序需要的快速排序 ///最大递归深度，以判断其效率是否已下降到不可接受的程度 template
inline _Size __lg(_Size __n) { _Size __k; for (__k = 0; __n != 1; __n >>= 1) ++__k; return __k; } ///部分排序，保证__first,__middle之间的元素最小并且有序 template
void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, _Tp*) { make_heap(__first, __middle); for (_RandomAccessIter __i = __middle; __i < __last; ++__i) if (*__i < *__first) __pop_heap(__first, __middle, __i, _Tp(*__i), __DISTANCE_TYPE(__first)); sort_heap(__first, __middle); } template
void __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*, _Size __depth_limit) { ///长度不大于16退出，由最后的插入排序处理 ///以减小递归深度 while (__last - __first > __stl_threshold) { if (__depth_limit == 0) { ///说明快速排序效率已经不可接受，转而采用堆排序 ///这里虽然调用partial_sort，但实际上使用了其完全的堆排序(__middle = __last) partial_sort(__first, __last, __last); return; } ///每进行一次递归调用，__depth_limit减少1次 --__depth_limit; ///快速排序的标志元用首、尾元素和中间元素的中间值得到，得到的值 ///一定大于等于first而小于等于__last-1，因而采用__unguarded_partition ///并根据中间值来划分子序列 _RandomAccessIter __cut = __unguarded_partition(__first, __last, _Tp(__median(*__first, *(__first + (__last - __first)/2), *(__last - 1)))); ///对后一半子序列进行递归调用快速排序 __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit); __last = __cut; ///在while循环中处理前一半子序列，从而减少了递归调用的次数 } } template
inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) { __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, _LessThanComparable); if (__first != __last) { __introsort_loop(__first, __last, __VALUE_TYPE(__first), __lg(__last - __first) * 2); ///最后的插入排序处理 __final_insertion_sort(__first, __last); } } template
_RandomAccessIter __partial_sort_copy(_InputIter __first, _InputIter __last, _RandomAccessIter __result_first, _RandomAccessIter __result_last, _Distance*, _Tp*) { if (__result_first == __result_last) return __result_last; _RandomAccessIter __result_real_last = __result_first; while(__first != __last && __result_real_last != __result_last) { *__result_real_last = *__first; ++__result_real_last; ++__first; } make_heap(__result_first, __result_real_last); while (__first != __last) { ///将源区间内剩余的较小元素调整至目标区间 if (*__first < *__result_first) __adjust_heap(__result_first, _Distance(0), _Distance(__result_real_last - __result_first), _Tp(*__first)); ++__first; } sort_heap(__result_first, __result_real_last); return __result_real_last; } /// nth_element() and its auxiliary functions. ///保证排序以后nth之前的元素均比nth小，nth之后的元素均比nth大 template
void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, _RandomAccessIter __last, _Tp*) { while (__last - __first > 3) { ///长度大于3时进行分割， _RandomAccessIter __cut = __unguarded_partition(__first, __last, _Tp(__median(*__first, *(__first + (__last - __first)/2), *(__last - 1)))); ///缩小分割区间 if (__cut <= __nth) __first = __cut; else __last = __cut; } ///区间长度不大于3时直接插入排序即可 __insertion_sort(__first, __last); } /// Binary search (lower_bound, upper_bound, equal_range, binary_search). ///看lower_bound和upper_bound实现的区别 template
_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, _Distance*) { _Distance __len = 0; distance(__first, __last, __len); _Distance __half; _ForwardIter __middle; while (__len > 0) { __half = __len >> 1; ///右移1位，相当于除2 __middle = __first; advance(__middle, __half); ///找到middle，并比较 ///只有当val > *__middle时才向后查找 if (*__middle < __val) { __first = __middle; ++__first; __len = __len - __half - 1; } else ///val <= *__middle时均向前查找 __len = __half; } return __first; } template
_ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, _Distance*) { _Distance __len = 0; distance(__first, __last, __len); _Distance __half; _ForwardIter __middle; while (__len > 0) { __half = __len >> 1; __middle = __first; advance(__middle, __half); ///只有当val < *__middle时才向前查找 if (__val < *__middle) __len = __half; else { ///val >= *__middle时均向后查找 __first = __middle;