作者：qtl4431541 | 来源：互联网 | 2023-10-11 14:53
直接贴第一段代码：nth_element()anditsauxiliaryfunctions.templatevoid__nth_element(_RandomAcces
直接贴第一段代码：
// nth_element() and its auxiliary functions.
template
void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
_RandomAccessIter __last, _Tp*) {
while (__last - __first > 32) {
_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);
}
template
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));
}
这里是直接调用partion（）来把序列分为两个部分，如果Nth在左边就所有左边的第n位置，如果左边的size直到序列的长度小于32，就用插入排序，这时迭代器指向的左边元素都小于等于它，右边都大于等于它，然后迭代器的位置就是你要找的位置了。
刚才说到了调用分类排序的方法partition（），现在再来说说partition的源码：
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;
}
}
源码很简单，就是快排的那个比k大k小的元素的那个交换步骤。
STL源码剖析------nth_element()&&partition(),布布扣,bubuko.com
京公网安备 11010802041100号