__partial_sort 实现部分排序，令 __first 到 __middle 的距离为 __len。函数对 __first 到 __last 中最小的 __len 个元素进行排序，并将前 __len 个最小元素排序后的序列放置到 __first 到 __middle 之间的位置。
函数首先对 __first 到 __middle 中的元素构造一个最大堆，for 循环中将最小的 __len 个元素移动到 __first 到 __middle 之间 (在堆中)。将余下的元素移动到 __middle 到 __last 之间。__pop_heap 函数每次将 first 所处的位置的元素(堆中的最大元素)弹出放置到 __i 所在的位置，并将原先 __i 所在的位置的元素插入到堆中，堆中的元素个数保持不变。最后调用 sort_heap 对最小的 __len 个元素进行排序。
template <class _RandomAccessIter, class _Tp>
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);
}
partial_sort 对 __first 到 __last 中的元素进行部分排序，通过调用上面定义的 __partial_sort 进行排序。
template <class _RandomAccessIter>
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));
}
函数 __partial_sort_copy 将 __first 到 __last 中部分排序的内容复制到 __result_first 到 __result_last 之间。令 __first 到 __last 的长度为 __l1，令 __result_first 到 __result_last 的元素个数为 __l2。函数最终会将 __first 到 __last 中 min(__l1, __l2) 个最小元素排好序后复制到 __result_first 到 __result_last 之间。
如果 __l1 < __l2 函数先将 __first 到 __last 的所有元素复制到 __result_first 到 __result_last 之间。否则将 __first 到 __last 的最小的 __l2 个元素复制到 __result_first 到 __result_last 之间。
在 __result_first 到 __result_real_last 之间的元素构造一个最大堆。如果 __first 不等于结束标记 __last ，while 循环中不断的将不属于 __first 到 __last 中 min(__l1, __l2) 个最小元素的元素移出最大堆，并将属于的元素替换进来。退出循环后，__result_first 到 __result_real_last 之间的元素是 __first 到 __last 中 min(__l1, __l2) 个最小元素。最后调用 sort_heap 对 __result_first 到 __result_real_last 之间的元素进行排序。
template <class _InputIter, class _RandomAccessIter, class _Distance,
class _Tp>
_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;
}
函数 partial_sort_copy 将 __first 到 __last 中部分排序的内容复制到 __result_first 到 __result_last 之间。
template <class _InputIter, class _RandomAccessIter>
inline _RandomAccessIter
partial_sort_copy(_InputIter __first, _InputIter __last,
_RandomAccessIter __result_first,
_RandomAccessIter __result_last) {
__STL_REQUIRES(_InputIter, _InputIterator);
__STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
__STL_CONVERTIBLE(typename iterator_traits<_InputIter>::value_type,
typename iterator_traits<_RandomAccessIter>::value_type);
__STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type,
_LessThanComparable);
__STL_REQUIRES(typename iterator_traits<_InputIter>::value_type,
_LessThanComparable);
return __partial_sort_copy(__first, __last, __result_first, __result_last,
__DISTANCE_TYPE(__result_first),
__VALUE_TYPE(__first));
}
函数 __nth_element 用来确定如果对 __first 到 __last 之间的元素进行排序，那么 __nth 位置(注意这里 __nth 是一个实际地址，而不是一个像序号一样的索引地址) 所在的元素。函数调用之前定义的 __unguarded_partition 将 __first 到 __last 之间的内容分割为两部分，使得第一部分的元素都小于第二部分的元素。二者的分割值为 __cut。
然后根据 __cut 和 __nth 的位置更新 __first 和 __last 的值，以保证 __cut 位置所在的元素始终包含在 __first 和 __last 之间。当 __first 和 __last 之间的差值小于 3 时，直接应用插入排序对 __first 到 __last 之间的元素进行排序，此时 __nth 位置的元素即为所求。
template <class _RandomAccessIter, class _Tp>
void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
_RandomAccessIter __last, _Tp*) {
while (__last - __first > 3) {
_RandomAccessIter __cut =
__unguarded_partition(__first, __last,
_Tp(__median(*__first,
*(__first + (__last - __first)/2),
*(__last - 1))));
if (__cut <= __nth)
__first = __cut;
else
__last = __cut;
}
__insertion_sort(__first, __last);
}
函数 __nth_element 求如果将 __first 到 __last 之间的元素进行排序，位置 __nth 上所在的元素。
template <class _RandomAccessIter>
inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
_RandomAccessIter __last) {
__STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
__STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type,
_LessThanComparable);
__nth_element(__first, __nth, __last, __VALUE_TYPE(__first));
}
函数 __lower_bound 求 __first 到 __last 之间的有序序列中从 __first 开始第一个第一个大于或者等于给定值 __val 的位置。如果大于等于 __val 的值存在，则返回从 __first 开始第一个大于等于 __val 的元素的位置。否则返回值为 __last 。
template <class _ForwardIter, class _Tp, class _Distance>
_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;
__middle = __first;
advance(__middle, __half);
if (*__middle < __val) {
__first = __middle;
++__first;
__len = __len - __half - 1;
}
else
__len = __half;
}
return __first;
}
函数 lower_bound 返回从 __first 开始第一个大于或者等于 __val 的元素的位置。函数调用 __lower_bound 来实现。
template <class _ForwardIter, class _Tp>
inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,
const _Tp& __val) {
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_REQUIRES_SAME_TYPE(_Tp,
typename iterator_traits<_ForwardIter>::value_type);
__STL_REQUIRES(_Tp, _LessThanComparable);
return __lower_bound(__first, __last, __val,
__DISTANCE_TYPE(__first));
}
函数 __upper_bound 返回 __first 到 __last 的有序序列中从 __first 开始第一个大于给定值 __val 的元素的位置。如果存在大于 __val 的元素，则返回从 __first 开始第一个大于给定值 __val 的元素的位置。 否则返回值为 __last 。
template <class _ForwardIter, class _Tp, class _Distance>
_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);
if (__val < *__middle)
__len = __half;
else {
__first = __middle;
++__first;
__len = __len - __half - 1;
}
}
return __first;
}
函数 upper_bound 返回从 __first 到 __last 的有序序列中第一个大于 __val 的元素的位置。
template <class _ForwardIter, class _Tp>
inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,
const _Tp& __val) {
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_REQUIRES_SAME_TYPE(_Tp,
typename iterator_traits<_ForwardIter>::value_type);
__STL_REQUIRES(_Tp, _LessThanComparable);
return __upper_bound(__first, __last, __val,
__DISTANCE_TYPE(__first));
}
函数 __equal_range 返回有序序列中值等于 __val 的序列的起始和截止位置(起始位置的元素值为 __val，但结束位置的元素值不为 __val)。
也是用二分法，通过取中间元素的值和 __val 进行对比，并根据比对大小，来更新 __first 和 __len 的值。如果存在等于 __val 的元素，那么等于 __val 的元素组成的序列在整个循环过程中都在 __first 到 __first + len 之间。
循环过程中如果找到一个等于 __val 的元素，则调用 lower_bound 和 upper_bound 函数，两个函数的返回值就分别为等于 __val 的元素序列的起始位置和截止位置。如果 __first 到 __last 之间不存在等于 __val 的元素，则返回值为 pair(__last, __last)
template <class _ForwardIter, class _Tp, class _Distance>
pair<_ForwardIter, _ForwardIter>
__equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
_Distance*)
{
_Distance __len = 0;
distance(__first, __last, __len);
_Distance __half;
_ForwardIter __middle, __left, __right;
while (__len > 0) {
__half = __len >> 1;
__middle = __first;
advance(__middle, __half);
if (*__middle < __val) {
__first = __middle;
++__first;
__len = __len - __half - 1;
}
else if (__val < *__middle)
__len = __half;
else {
__left = lower_bound(__first, __middle, __val);
advance(__first, __len);
__right = upper_bound(++__middle, __first, __val);
return pair<_ForwardIter, _ForwardIter>(__left, __right);
}
}
return pair<_ForwardIter, _ForwardIter>(__first, __first);
}
函数 equal_range 返回从 __first 到 __last 的有序序列中值等于 __val 的元素序列的起始位置和截止位置。
template <class _ForwardIter, class _Tp>
inline pair<_ForwardIter, _ForwardIter>
equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) {
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_REQUIRES_SAME_TYPE(_Tp,
typename iterator_traits<_ForwardIter>::value_type);
__STL_REQUIRES(_Tp, _LessThanComparable);
return __equal_range(__first, __last, __val,
__DISTANCE_TYPE(__first));
}
函数 binary_search 在从 __first 到 __last 的有序序列中查找等于 __val 的元素，函数调用 lower_bound 函数来实现，如果存在等于 __val 的元素，则lower_bound 的会返回一个值为 __val 的位置，否则会返回 __last 或者一个值大于 __val 的位置。通过判断 lower_bound 的返回值可以判断 __first 到 __last 之间是否存在值为 __val 的元素。
template <class _ForwardIter, class _Tp>
bool binary_search(_ForwardIter __first, _ForwardIter __last,
const _Tp& __val) {
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_REQUIRES_SAME_TYPE(_Tp,
typename iterator_traits<_ForwardIter>::value_type);
__STL_REQUIRES(_Tp, _LessThanComparable);
_ForwardIter __i = lower_bound(__first, __last, __val);
return __i != __last && !(__val < *__i);
}
函数 merge 将从 __first1 到 __last1 的有序序列和从 __first2 到 __last2 的有序序列进行合并。并且将合并的结果存储在 __result 开始的位置。
template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result) {
__STL_REQUIRES(_InputIter1, _InputIterator);
__STL_REQUIRES(_InputIter2, _InputIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
__STL_REQUIRES_SAME_TYPE(
typename iterator_traits<_InputIter1>::value_type,
typename iterator_traits<_InputIter2>::value_type);
__STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
_LessThanComparable);
while (__first1 != __last1 && __first2 != __last2) {
if (*__first2 < *__first1) {
*__result = *__first2;
++__first2;
}
else {
*__result = *__first1;
++__first1;
}
++__result;
}
return copy(__first2, __last2, copy(__first1, __last1, __result));
}
函数 __merge_without_buffer 将从 __first 到 __middle 的有序序列和从 __middle 到 __last 的有序序列进行合并，使得合并之后从 __first 到 __last 的序列是有序的。
令 __len1 为 __first 到 __middle 的距离，__len2 为 __middle 到 __last 的距离。如果 __len1 > __len2 ，令 __len11 = __len1 / 2。令 __first_cut 为 __first 之后的第 __len11 个位置。令 second_cut 为 __middle 到 __last 之间第一个大于或者等于 __first_cut 所在位置的元素的位置。
然后将 __first_cut 到 __middle 之间的内容和 __middle 到 __last 之间的内容通过 rotate 函数进行交换。返回值为 __new_middle。则此时 __first 到 __new_middle 之间的元素(小于或者等于交换之前 __first_cut 位置的元素值)都小于或者等于 __new_middle 到 __last 之间的元素(大于或者等于交换之前 __first_cut 所在位置的元素的元素值)。则递归的对 __first 到 __new_middle 和 __new_middle 到 __last 之间的元素调用 __merge_without_buffer 进行合并就可以了。
template <class _BidirectionalIter, class _Distance>
void __merge_without_buffer(_BidirectionalIter __first,
_BidirectionalIter __middle,
_BidirectionalIter __last,
_Distance __len1, _Distance __len2) {
if (__len1 == 0 || __len2 == 0)
return;
if (__len1 + __len2 == 2) {
if (*__middle < *__first)
iter_swap(__first, __middle);
return;
}
_BidirectionalIter __first_cut = __first;
_BidirectionalIter __second_cut = __middle;
_Distance __len11 = 0;
_Distance __len22 = 0;
if (__len1 > __len2) {
__len11 = __len1 / 2;
advance(__first_cut, __len11);
__second_cut = lower_bound(__middle, __last, *__first_cut);
distance(__middle, __second_cut, __len22);
}
else {
__len22 = __len2 / 2;
advance(__second_cut, __len22);
__first_cut = upper_bound(__first, __middle, *__second_cut);
distance(__first, __first_cut, __len11);
}
_BidirectionalIter __new_middle
= rotate(__first_cut, __middle, __second_cut);
__merge_without_buffer(__first, __first_cut, __new_middle,
__len11, __len22);
__merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
__len2 - __len22);
}
STL 的 算法 (algo) 分析（一）</br> STL 的 算法 (algo) 分析（二）</br> STL 的 算法 (algo) 分析（三）</br> STL 的 算法 (algo) 分析（四）</br> STL 的 算法 (algo) 分析（五）</br> STL 的 算法 (algo) 分析（六）</br> STL 的 算法 (algo) 分析（七）</br> STL 的 算法 (algo) 分析（八）</br>