Namespaces
Variants

    std::nth_element

    来自 zh.cppreference.net
     
    C++
     
    算法库
    受约束算法和范围算法 (C++20)
    受约束算法，例如 ranges::copy、ranges::sort，...
    排序和相关操作
    划分操作
    (C++11)    
    (C++11)

    排序操作
    二分搜索操作
    (在已划分的范围上)
    集合操作（在已排序范围上）
    合并操作（在已排序范围上）
    堆操作
    最小/最大操作
    (C++11)
    (C++17)
    字典序比较操作
    (C++20)
    排列操作


     
    定义于头文件 <algorithm> 
    template< class RandomIt >
void nth_element( RandomIt first, RandomIt nth, RandomIt last );
    		(1) (C++20 起 constexpr) 
    template< class ExecutionPolicy, class RandomIt >
void nth_element( ExecutionPolicy&& policy,
                  RandomIt first, RandomIt nth, RandomIt last );
    		(2) (C++17 起) 
    template< class RandomIt, class Compare >
void nth_element( RandomIt first, RandomIt nth, RandomIt last,
                  Compare comp );
    		(3) (C++20 起 constexpr) 
    template< class ExecutionPolicy, class RandomIt, class Compare >
void nth_element( ExecutionPolicy&& policy,
                  RandomIt first, RandomIt nth, RandomIt last,
                  Compare comp );
    		(4) (C++17 起)

    nth_element 重新排列 [first, last) 中的元素，使得重新排列后：

    • nth 所指向的元素被更改为如果对整个 [first, last) 排序后将在该位置出现的元素。
    • 对于 i 中的每个迭代器 [first, nth) 和 j 中的每个迭代器 [nth, last)，满足以下条件：
    1,2) bool(*j < *i)(C++20 前)std::less{}(*j, *i)(C++20 起) 为 false。
    3,4) bool(comp(*j, *i)) 为 false。


    1) 元素根据 （在假设上）排序operator<(C++20 前)std::less{}(C++20 起)。
    3) 元素根据 comp（在假设上）排序。
    2,4) 同 (1,3)，但按 policy 执行。
    这些重载仅当以下表达式的值为 true 时才参与重载决议：

    std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>

    		(C++20 前)

    std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>

    		(C++20 起)

    如果满足以下任何条件，则行为未定义：

    (C++11 前)
    (C++11 起)

    参数

    first, last - 定义待部分排序元素 范围 的迭代器对
    nth - 定义排序分区点的随机访问迭代器
    policy - 使用的 执行策略
    comp - 比较函数对象（即满足 Compare 要求的对象），当第一个参数 小于 （即排序在 之前 ）第二个参数时返回​ true 。

    比较函数的签名应等价于：

    bool cmp ( const Type1 & a, const Type2 & b ) ;

    虽然签名不需要包含 const & ，但函数不得修改传递给它的对象，且必须能够接受所有（可能为const的） Type1 和 Type2 类型的值，无论其 值类别 为何（因此不允许 Type1& ，也不允许 Type1 ，除非对于 Type1 类型移动操作等价于拷贝操作 (C++11 起) ）。
    类型 Type1 和 Type2 必须使得 RandomIt 类型的对象在解引用后能隐式转换到这两个类型。 ​

    类型要求
    -
    RandomIt 必须满足 LegacyRandomAccessIterator 的要求。
    -
    Compare 必须满足 Compare 的要求。

    复杂度

    给定 N 为 last - first ：

    1) O(N) 次比较，平均使用 operator < (C++20 前) std:: less { } (C++20 起) 。
    2) O(N) 次比较（使用 operator < (C++20 前) std:: less { } (C++20 起) ），以及 O(N·log(N)) 次交换。
    3) O(N) 次比较器 comp 的平均调用次数。
    4) O(N) 次比较器 comp 的应用，以及 O(N·log(N)) 次交换。

    异常

    带有名为 ExecutionPolicy 模板参数的重载按以下方式报告错误：

    • 如果作为算法一部分调用的函数执行抛出异常，且 ExecutionPolicy 是某个 标准策略 ，则调用 std::terminate 。对于其他任何 ExecutionPolicy ，其行为由实现定义。
    • 如果算法无法分配内存，则抛出 std::bad_alloc 。

    可能的实现

    另请参阅以下实现： libstdc++ 、 libc++ 以及 MSVC STL 。

    注释

    所采用的算法通常是 Introselect ，但也允许使用其他具有合适平均情况复杂度的 Selection algorithm 。

    示例

    运行此代码 
    #include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <numeric>
#include <vector>
void printVec(const std::vector<int>& vec)
{
    std::cout << "v = {";
    for (char sep[]{0, ' ', 0}; const int i : vec)
        std::cout << sep << i, sep[0] = ',';
    std::cout << "};\n";
}
int main()
{
    std::vector<int> v{5, 10, 6, 4, 3, 2, 6, 7, 9, 3};
    printVec(v);
    auto m = v.begin() + v.size() / 2;
    std::nth_element(v.begin(), m, v.end());
    std::cout << "\nThe median is " << v[v.size() / 2] << '\n';
    // 第N个元素前后元素不等式关系的必然结果：
    assert(std::accumulate(v.begin(), m, 0) < std::accumulate(m, v.end(), 0));
    printVec(v);
    // 注意：比较函数已更改
    std::nth_element(v.begin(), v.begin() + 1, v.end(), std::greater{});
    std::cout << "\nThe second largest element is " << v[1] << '\n';
    std::cout << "The largest element is " << v[0] << '\n';
    printVec(v);
}

    可能的输出： 

    v = {5, 10, 6, 4, 3, 2, 6, 7, 9, 3};
中位数为 6
v = {3, 2, 3, 4, 5, 6, 10, 7, 9, 6};
第二大元素为 9
最大元素为 10
v = {10, 9, 6, 7, 6, 3, 5, 4, 3, 2};

    缺陷报告

    下列行为变更缺陷报告被追溯应用于先前发布的 C++ 标准。

    缺陷报告 适用范围 发布行为 正确行为
    LWG 2150 C++98 重排后仅要求 nth 前的一个元素
    不大于 nth 后的一个元素     		修正了
    要求条件
    LWG 2163 C++98 重载版本 ( 1 ) 使用 operator > 比较元素 改为使用 operator <
    P0896R4 C++98 未要求 [ first , nth ) 和 [ nth , last )
    是有效范围     		若任一范围无效
    则行为未定义

    另见

    		 返回给定范围中的最大元素
    (函数模板 &算法函数对象)
    (C++20)
    		返回给定范围中的最小元素
    (函数模板 &算法函数对象)
    (C++20)
    		复制并部分排序一个范围内的元素
    (函数模板 &算法函数对象)
    (C++20)
    		对一个范围内的元素排序，同时保持相等元素的相对顺序
    (函数模板 &算法函数对象)
    (C++20)
    		排序一个范围内的元素
    (函数模板 &算法函数对象)
    (C++20)
    (C++20)
    		 若范围已排序，则找到第 N 个元素
    (算法函数对象)