std:: nth_element

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

• 由 nth 指向的元素将被更改为：若 [ first , last ) 区间经过排序，该位置原本会出现的元素。
• 对于 [ first , nth ) 区间内的每个迭代器 i ，以及 [ nth , last ) 区间内的每个迭代器 j ，均满足以下条件：

若满足以下任一条件，则行为未定义：

• [ first , nth ) 或 [ nth , last ) 不是有效的 范围 。

参数

复杂度

给定 \(\scriptsize N\) N 为 last - first ：

异常

带有名为 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++ 标准。

参见