__unguarded_linear_insert 函数用来将给定值 __val 插入到以 __last 为结束位置的有序序列中。函数将所有大于 __val 的元素都整体往后移动一个位置，然后将 __val 插入到挪出来的位置上。
template <class _RandomAccessIter, class _Tp>
void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) {
_RandomAccessIter __next = __last;
--__next;
while (__val < *__next) {
*__last = *__next;
__last = __next;
--__next;
}
*__last = __val;
}
函数 __unguarded_linear_insert 将给定值 __val 插入到以 __last 为结束位置的有序序列中。函数通过自定义的比较函数来比较元素的大小，并将所有大于 __val 的元素都整体往后移动一个位置，然后将 __val 插入到挪出来的位置上。
template <class _RandomAccessIter, class _Tp, class _Compare>
void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val,
_Compare __comp) {
_RandomAccessIter __next = __last;
--__next;
while (__comp(__val, *__next)) {
*__last = *__next;
__last = __next;
--__next;
}
*__last = __val;
}
函数 __linear_insert 将 __last 所在位置的元素插入到从 __first 到 __last(不包括 __last 所在的位置) 的有序序列中。函数首先判断 __last 所在位置的元素是否比 __first 所在位置的元素要小，如果是，则调用 copy_backward 将 __first 到 __last 之间的所有元素整体往后移动一个位置，然后将原先 __last 所在位置的元素插入到原先 __first 所在的位置。否则调用 __unguarded_linear_insert 函数将 __last 所在位置的元素插入到有序序列中。
template <class _RandomAccessIter, class _Tp>
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);
}
函数 __linear_insert 将 __last 所在位置的元素插入到 __first 到 __last(不包括 __last 所在位置的元素) 的有序序列中，并通过自定义的比较函数 __comp 来比较元素的大小。如果 __last 所在位置的元素比 __first 所在位置的元素要小，则调用 copy_backward 函数将 __first 到 __last 之间的所有元素都整体往后移动一个位置，并将原先 __last 所在位置的元素插入到原先 __first 所在的位置。否则调用 __unguarded_linear_insert 函数实现想要实现的功能。
template <class _RandomAccessIter, class _Tp, class _Compare>
inline void __linear_insert(_RandomAccessIter __first,
_RandomAccessIter __last, _Tp*, _Compare __comp) {
_Tp __val = *__last;
if (__comp(__val, *__first)) {
copy_backward(__first, __last, __last + 1);
*__first = __val;
}
else
__unguarded_linear_insert(__last, __val, __comp);
}
函数 __insertion_sort 实现插入排序，借助辅助程序 __linear_insert 函数来实现。
template <class _RandomAccessIter>
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));
}
函数 __insertion_sort 实现插入排序，并且通过自定义的比较函数来比较元素的大小，借助辅助成员 __linear_insert 来实现。
template <class _RandomAccessIter, class _Compare>
void __insertion_sort(_RandomAccessIter __first,
_RandomAccessIter __last, _Compare __comp) {
if (__first == __last) return;
for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
__linear_insert(__first, __i, __VALUE_TYPE(__first), __comp);
}
__unguarded_linear_insertion_sort_aux 为 __first 到 __last 之间的内容实现插入排序。
template <class _RandomAccessIter, class _Tp>
void __unguarded_insertion_sort_aux(_RandomAccessIter __first,
_RandomAccessIter __last, _Tp*) {
for (_RandomAccessIter __i = __first; __i != __last; ++__i)
__unguarded_linear_insert(__i, _Tp(*__i));
}
__unguarded_insertion_sort 为 __first 到 __last 之间的内容实现插入排序。
template <class _RandomAccessIter>
inline void __unguarded_insertion_sort(_RandomAccessIter __first,
_RandomAccessIter __last) {
__unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first));
}
函数 __final_insertion_sort 为 __first 到 __last 之间的内容实现插入排序。其中 __stl_threhold 是当前文件中定义的一个全局的整型常量。
template <class _RandomAccessIter>
void __final_insertion_sort(_RandomAccessIter __first,
_RandomAccessIter __last) {
if (__last - __first > __stl_threshold) {
__insertion_sort(__first, __first + __stl_threshold);
__unguarded_insertion_sort(__first + __stl_threshold, __last);
}
else
__insertion_sort(__first, __last);
}
函数 __lg 求给定值 __n 以 2 为底的对数。求得的值是整型。
template <class _Size>
inline _Size __lg(_Size __n) {
_Size __k;
for (__k = 0; __n != 1; __n >>= 1) ++__k;
return __k;
}
函数 __introsort_loop 为 __first 到 __last 之间的内容进行排序，但实现的是一个初步排序，并没有完成最终的排序，只是将 __first 到 __last 之间的元素分成一个一个长度小于 __stl_threhold 的段。其中前面的段中的任何元素都小于或者等于后面的段中的任何元素。
函数采用一种综合的排序方式。其中定义了一些限制方式，首先只有 __first 到 __last 之间的元素个数大于 __stl_threhold 时才会对其进行排序，其次函数中有一个形参用来限制递归的深度。当 __depth_limit 为 0 时，不允许再进行递归，调用 partial_sort 对其进行排序，partial_sort 在后面定义，它采用的是堆排序。
如果 __depth_limit 的值大于 0 ，则首先调用 unguarded_partition 用 __first, __last 和 __first 到 __last 的中间位置这三个位置所在的元素的中间元素作为 pivot 对 __first 到 __last 之间的内容进行分割，取得分割位置为 __cut。利用尾递归方法对 __cut 到 __last 之间的内容进行递归排序。递归完毕后，将 __last 更新为 __cut 。利用循环再对 __first 到 __cut 之间的内容进行排序。
template <class _RandomAccessIter, class _Tp, class _Size>
void __introsort_loop(_RandomAccessIter __first,
_RandomAccessIter __last, _Tp*,
_Size __depth_limit)
{
while (__last - __first > __stl_threshold) {
if (__depth_limit == 0) {
partial_sort(__first, __last, __last);
return;
}
--__depth_limit;
_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;
}
}
函数 sort 对 __first 到 __last 之间的内容进行排序，函数首先调用 __introsort_loop 将 __first 到 __last 之间的内容分割成一个个长度小于 __stl_threhold 的段，使得前面的段中的元素都小于后面的段中的元素。然后调用 __final_insertion_sort 采用插入排序的方式为 __first 到 __last 之间的元素进行排序。最后的插入排序的所需的时间渐进认为是线性的。
template <class _RandomAccessIter>
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);
}
}
函数 __inplace_stable_sort 对 __first 到 __last 之间的元素实现原地的稳定排序。如果 __first 到 __last 之间的元素个数小于 15 ，则直接对 __first 到 __last 之间的元素实施插入排序(插入排序是稳定的)。否则先递归的对 __first 的前半部分进行 __inplace_stable_sort 排序，然后对 __first 到 __last 的后半部分进行 __inplace_stable_sort 排序，最后将这已排序的两部分调用 __merge_without_buffer 进行合并。
template <class _RandomAccessIter>
void __inplace_stable_sort(_RandomAccessIter __first,
_RandomAccessIter __last) {
if (__last - __first < 15) {
__insertion_sort(__first, __last);
return;
}
_RandomAccessIter __middle = __first + (__last - __first) / 2;
__inplace_stable_sort(__first, __middle);
__inplace_stable_sort(__middle, __last);
__merge_without_buffer(__first, __middle, __last,
__middle - __first,
__last - __middle);
}
merge_sort_loop 用来对 __first 到 __last 之间的内容进行合并，对于 __first 到 __last 之间的内容，从 __first 开始将其分成长度为 __step_size 的一段一段。除最后一段的长度小于或者等于 __step_size 之外，其他的段的长度都等于 __step_size，并且每一段都是已排序的。
while 循环中将相邻两个已排序的段调用 merge 函数进行合并，将其变成长度为 2 * __step_size 的已排序的段，并将合并结果放在 __result 中, merge 的返回值是合并结果存放在 __result 中的结束位置，__result 获取到该返回值后，下次的合并结果就会存放到当前合并结果的后面。
while 循环结束之后，可能余下一段或者两段，再将余下的部分也调用 merge 函数进行合并，但合并之后得到的段的长度可能比 2 * __step_size 要小。
template <class _RandomAccessIter1, class _RandomAccessIter2,
class _Distance>
void __merge_sort_loop(_RandomAccessIter1 __first,
_RandomAccessIter1 __last,
_RandomAccessIter2 __result, _Distance __step_size) {
_Distance __two_step = 2 * __step_size;
while (__last - __first >= __two_step) {
__result = merge(__first, __first + __step_size,
__first + __step_size, __first + __two_step,
__result);
__first += __two_step;
}
__step_size = min(_Distance(__last - __first), __step_size);
merge(__first, __first + __step_size, __first + __step_size, __last,
__result);
}
__chunk_insertion_sort 函数将 __first 到 __last 之间的内容分割为长度为 __stl_chunk_size 的段(除最后一段的长度可能小于 __stl_chunk_size 之外，其他的每段的长度都等于 __stl_chunk_size)。然后对每段之内的内容进行插入排序。
template <class _RandomAccessIter, class _Distance>
void __chunk_insertion_sort(_RandomAccessIter __first,
_RandomAccessIter __last, _Distance __chunk_size)
{
while (__last - __first >= __chunk_size) {
__insertion_sort(__first, __first + __chunk_size);
__first += __chunk_size;
}
__insertion_sort(__first, __last);
}
__merge_sort_with_buffer 函数对 __first 到 __last 之间的内容进行归并排序。函数先将 __first 到 __last 之间的元素分成长度为 __stl_chunk_size 的段，并调用 __chunk_insertion_sort 先对每段元素进行插入排序。在 while 循环中将相邻两段之内的元素进行合并，因为调用了辅助空间 __buffer。while 循环中第一次调用 __merge_sort_loop 得到的合并结果存储在 __buffer 开始的空间。而第二次调用 __merge_sort_loop 将 __first 开始的地址空间作为辅助空间，得到的合并结果再次回到 __first 开始的地址空间。
template <class _RandomAccessIter, class _Pointer, class _Distance>
void __merge_sort_with_buffer(_RandomAccessIter __first,
_RandomAccessIter __last,
_Pointer __buffer, _Distance*) {
_Distance __len = __last - __first;
_Pointer __buffer_last = __buffer + __len;
_Distance __step_size = __stl_chunk_size;
__chunk_insertion_sort(__first, __last, __step_size);
while (__step_size < __len) {
__merge_sort_loop(__first, __last, __buffer, __step_size);
__step_size *= 2;
__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
__step_size *= 2;
}
}
函数 __stable_sort_adaptive 对 __first 到 __last 之间的内容进行稳定的排序。在排序过程中借助从 __buffer 开始长度为 __buffer_size 的辅助空间。其中辅助空间 __buffer 可能可供使用的长度比 __first 到 __last 之间的长度要短，函数会根据 __buffer_size 的长度大小自适应的选择合适的方式进行排序。
令 __len 为 __first 到 __last 的长度的一半。同时令 __middle = __first + __len 。如果 __len 大于 __buffer_size ，则递归调用 __stable_sort_adaptive 用自适应的排序方法来分别对 __first 到 __middle 和 __middle 到 __last 之间的内容进行排序。
否则如果 __len 小于或者等于 __buffer_size ，因为辅助空间 __buffer 的长度是足够的，则调用 __merge_sort_with_buffer 分别对 __first 到 __middle 和 __middle 到 __last 之间的内容进行排序。最后使用 __merge_adaptive 对 __first 到 __middle 和 __middle 到 __last 这两段已排序的内容进行合并。
template <class _RandomAccessIter, class _Pointer, class _Distance>
void __stable_sort_adaptive(_RandomAccessIter __first,
_RandomAccessIter __last, _Pointer __buffer,
_Distance __buffer_size) {
_Distance __len = (__last - __first + 1) / 2;
_RandomAccessIter __middle = __first + __len;
if (__len > __buffer_size) {
__stable_sort_adaptive(__first, __middle, __buffer, __buffer_size);
__stable_sort_adaptive(__middle, __last, __buffer, __buffer_size);
}
else {
__merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0);
__merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0);
}
__merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
_Distance(__last - __middle), __buffer, __buffer_size);
}
函数 __stable_sort_aux 对 __first 到 __last 之间的内容进行稳定的排序。函数首先申请长度和 __first 到 __last 相当的临时空间，如果临时空间申请失败，则调用 __inplace_stable_sort 对 __first 到 __last 之间的内容进行原地的稳定排序。否则调用 __stable_sort_adpative 对 __first 到 __last 之间的内容进行稳定排序。
template <class _RandomAccessIter, class _Tp, class _Distance>
inline void __stable_sort_aux(_RandomAccessIter __first,
_RandomAccessIter __last, _Tp*, _Distance*) {
_Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);
if (buf.begin() == 0)
__inplace_stable_sort(__first, __last);
else
__stable_sort_adaptive(__first, __last, buf.begin(),
_Distance(buf.size()));
}
函数 stable_sort 调用 __stable_sort_aux 对 __first 到 __last 之间的内容进行稳定的排序。
template <class _RandomAccessIter>
inline void stable_sort(_RandomAccessIter __first,
_RandomAccessIter __last) {
__STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
__STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type,
_LessThanComparable);
__stable_sort_aux(__first, __last,
__VALUE_TYPE(__first),
__DISTANCE_TYPE(__first));
}
STL 的 算法 (algo) 分析（一）</br> STL 的 算法 (algo) 分析（二）</br> STL 的 算法 (algo) 分析（三）</br> STL 的 算法 (algo) 分析（四）</br> STL 的 算法 (algo) 分析（五）</br> STL 的 算法 (algo) 分析（六）</br> STL 的 算法 (algo) 分析（七）</br> STL 的 算法 (algo) 分析（八）</br>