//sort函数源码：
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排序,其中__lg函数用于控制最大分割层数;
__introsort_loop(__first, __last,
__VALUE_TYPE(__first),
__lg(__last - __first) * 2);
__final_insertion_sort(__first, __last);//对序列进行插入排序;
}
}
-
1
-
2
-
3
-
4
-
5
-
6
-
7
-
8
-
9
-
10
-
11
-
12
-
13
//__lg函数源码：
//找出2^k<=n的最大值k；
template
inline _Size __lg(_Size __n) {
_Size __k; for (__k = 0; __n != 1; __n >>= 1) ++__k; return __k;
}
//__introsort_loop函数源码:
const int __stl_threshold = 16; //全局变量;
template
//_Tp为待排序元素类型, __depth_limit为最多允许分割的层数;
void __introsort_loop(_RandomAccessIter __first,
_RandomAccessIter __last, _Tp*,
_Size __depth_limit)
{ while (__last - __first > __stl_threshold) {//如果待排序元素个数大于阀值; if (__depth_limit == 0) {//如果允许分割层数为0;
partial_sort(__first, __last, __last);//对[first,last)进行堆排序; return;
}
--__depth_limit;//分割层数减1;
//__median函数用于选择一个枢轴，然后进行一次分割操作,其中cut为"右半段"的第一个元素;
_RandomAccessIter __cut =
__unguarded_partition(__first, __last,
_Tp(__median(*__first,
*(__first + (__last - __first)/2),
*(__last - 1))));
__introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit);//对"右半段"进行__introsort排序;
__last = __cut;//继续while循环,对由[first,last)表示的"左半段"进行introsort；
}
}
-
1
-
2
-
3
-
4
-
5
-
6
-
7
-
8
-
9
-
10
-
11
-
12
-
13
-
14
-
15
-
16
-
17
-
18
-
19
-
20
-
21
-
22
-
23
//__unguarded_paririon函数源码:
template
_RandomAccessIter __unguarded_partition(_RandomAccessIter __first,
_RandomAccessIter __last,
_Tp __pivot) //分割函数;
{ while (true) { while (*__first < __pivot)//如果first指向的元素小于枢轴;
++__first;
--__last; while (__pivot < *__last)//如果枢轴小于last指向的元素;
--__last; if (!(__first < __last))//如果first和last迭代器交错，first为右半段第一个元素; return __first;
iter_swap(__first, __last);//firtst和last指向的元素交换;
++__first;
}
}
-
1
-
2
-
3
-
4
-
5
-
6
-
7
-
8
-
9
-
10
-
11
-
12
-
13
-
14
-
15
-
16
-
17
//partial_sort函数源码:
template
inline void partial_sort(_RandomAccessIter __first,
_RandomAccessIter __middle,
_RandomAccessIter __last) {
__STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
__STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type,
_LessThanComparable);
__partial_sort(__first, __middle, __last, __VALUE_TYPE(__first));
}
template
void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
_RandomAccessIter __last, _Tp*) {
make_heap(__first, __middle);//建立大顶堆;
//分割[middle,last)为[first,last)的"右半段"; for (_RandomAccessIter __i = __middle; __i < __last; ++__i) if (*__i < *__first)
__pop_heap(__first, __middle, __i, _Tp(*__i),
__DISTANCE_TYPE(__first));
sort_heap(__first, __middle);//对[first,middle)区间(即左半段)进行堆排序;
}
-
1
-
2
-
3
-
4
-
5
-
6
-
7
-
8
-
9
-
10
-
11
-
12
-
13
-
14
-
15
-
16
-
17
-
18
-
19
-
20
-
21
// __final_insertion_sort函数源码:
//进行插入排序;
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);
}
//__insertion_sort函数源码:
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));
}
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 __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) {
_RandomAccessIter __next = __last;
--__next; while (__val < *__next) {
*__last = *__next;
__last = __next;
--__next;
}
*__last = __val;
}
-
1
-
2
-
3
-
4
-
5
-
6
-
7
-
8
-
9
-
10
-
11
-
12
-
13
-
14
-
15
-
16
-
17
-
18
-
19
-
20
-
21
-
22
-
23
-
24
-
25
-
26
-
27
-
28
-
29
-
30
//__unguarded_insertion_sort函数源码:
template
inline void __unguarded_insertion_sort(_RandomAccessIter __first,
_RandomAccessIter __last) {
__unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__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));
}
//参考文献《STL源码剖析》
阅读(3620) | 评论(0) | 转发(0) |
