// <algorithm> 
// 默认(1)
template <class RandomAccessIterator>
    void nth_element (
        RandomAccessIterator first,
        RandomAccessIterator nth,
        RandomAccessIterator last);
// 自定义(2)
template <class RandomAccessIterator, class Compare>
    void nth_element (
        RandomAccessIterator first, 
        RandomAccessIterator nth,           
        RandomAccessIterator last, Compare comp);

部份排序指定范围中的元素,使得范围按给定位置处的元素划分。

该函数等价于:

template<class _RanIt,
class _Pr> inline
void _Nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last, _Pr _Pred)
{    // order Nth element, using _Pred
    for (; _ISORT_MAX < _Last - _First; )
    {    // divide and conquer, ordering partition containing Nth
        pair<_RanIt, _RanIt> _Mid =
            _Unguarded_partition(_First, _Last, _Pred);
        if (_Mid.second <= _Nth)
            _First = _Mid.second;
        else if (_Mid.first <= _Nth)
            return;    // Nth inside fat pivot, done
        else
            _Last = _Mid.first;
    }
    _Insertion_sort(_First, _Last, _Pred);    // sort any remainder
}
  • firstlast

    分别指向被划分序列中初始及末尾位置的随机访问迭代器(Random-access Iterators)。这个范围即 [first,last) ,包括 first 到 last 间的所有元素,包括 first 指向的元素,但不包括 last 指向的元素。

    nth

    C++11

    指向范围 [first,last) 中某个元素的随机访问迭代器。

    C++14

    指向范围 [first,last) 中某个元素的随机访问迭代器。

    如果指向 last,当前函数将无任何效果。

    comp

    二元谓词(Binary)函数,以两个元素为参数,然后返回一个可转换成 bool 类型的值。

    其返回值表明按所指定的严格弱序排序(Strict weak ordering)时,第一个参数所传进来的元素是否在第二个参数所传进来的元素前面。

    该函数不能修改其参数。

    可以是函数指针(Function pointer)类型或函数对象(Function object)类型。

  • 无。

  • 如果希望了解与自定义函数谓词、函数对象谓词、排序对象数组、lambda C++11 表达式、初始化列表 std::initializer_list 等相关的例子,请同时参照 std::sort

    例 1

    #include <iostream>
    #include <algorithm>
    #include <iterator>
    #include <vector>
    
    #define CLASSFOO_VECTOR(type, name, ...) \
    static const type name##_a[] = __VA_ARGS__; \
    std::vector<type> name(name##_a, name##_a + sizeof(name##_a) / sizeof(*name##_a))
    
    namespace ClassFoo{
        void NthElement_1() {
            CLASSFOO_VECTOR(int, BigVector1, { 8, 23, -5, 7, 29, 0, 5, 7, -7, 1, -1 });
    
            std::nth_element(
                std::begin(BigVector1),
                std::begin(BigVector1) + 6, // 按第 7 个元素(值为 5)划分
                std::end(BigVector1)
                );
    
            // 输出结果
            std::copy(
                BigVector1.begin(),
                BigVector1.end(),
                std::ostream_iterator<int>(std::cout, " "));
            std::cout << std::endl;
        }
    }
    int main()
    {
        ClassFoo::NthElement_1();
        return 0;
    }

    -7 -5 -1 0 1 5 7 7 8 23 29 

  • 复杂度

    O(n)n 等值为 std::distance(first,last)

    数据争用相关

    范围 [first,last) 中的元素都有可能被被修改过。

    异常安全性相关

    如果元素比较(Compare)、元素交换(Swap)、元素移动(Move)或操作某个迭代器抛异常,该函数才会抛异常。

    注意 无效参数将导致未定义行为(Undefined behavior)