std::nth_element() 算法

自 C++20 起

// (1)
template< class RandomIt >
constexpr void nth_element( RandomIt first, RandomIt nth, RandomIt last );

// (2)
template< class RandomIt, class Compare >
constexpr void nth_element( RandomIt first, RandomIt nth, RandomIt last, Compare comp );

// (3)
template< class ExecutionPolicy, class RandomIt >
void nth_element( ExecutionPolicy&& policy, RandomIt first, RandomIt nth, RandomIt last );

// (4)
template< class ExecutionPolicy, class RandomIt, class Compare >
void nth_element( ExecutionPolicy&& policy, RandomIt first, RandomIt nth, RandomIt last, Compare comp );

自 C++17 起

// (1)
template< class RandomIt >
void nth_element( RandomIt first, RandomIt nth, RandomIt last );

// (2)
template< class RandomIt, class Compare >
void nth_element( RandomIt first, RandomIt nth, RandomIt last, Compare comp );

// (3)
template< class ExecutionPolicy, class RandomIt >
void nth_element( ExecutionPolicy&& policy, RandomIt first, RandomIt nth, RandomIt last );

// (4)
template< class ExecutionPolicy, class RandomIt, class Compare >
void nth_element( ExecutionPolicy&& policy, RandomIt first, RandomIt nth, RandomIt last, Compare comp );

C++17 之前

// (1)
template< class RandomIt >
void nth_element( RandomIt first, RandomIt nth, RandomIt last );

// (2)
template< class RandomIt, class Compare >
void nth_element( RandomIt first, RandomIt nth, RandomIt last, Compare comp );

std::nth_element 是一个部分排序算法，它重新排列 [first; last) 中的元素，使得

• 由 nth 指向的元素更改为如果 [first; last) 已排序，则会出现在该位置的任何元素。
• 这个新的 nth 元素之前的所有元素都小于或等于新的 nth 元素之后的元素。
• 如果 nth == last，则该函数没有效果。

更正式地说，nth_element 以升序部分排序范围 [first; last)，以便对于范围 [first; nth) 中的任何 i 和范围 [nth; last) 中的任何 j，都满足条件 !(*j < *i) (对于 (1, 3)，或 !comp(*j, *i) 对于 (2, 4))。

放置在 nth 位置的元素正是如果范围完全排序，将出现在该位置的元素。

• (1) 元素使用 operator< 进行比较。

• (2) 元素使用给定的二元比较函数 comp 进行比较。

• (3, 4) 与 (1) 和 (2) 相同，但根据策略执行。

  重载决议

  这些重载只有在 std::is_execution_policy_v> 为 true 时才参与重载决议。  (直到 C++20) std::is_execution_policy_v> 为 true 时才参与重载决议。  (自 C++20 起)

参数

first last	要排序的元素范围。
nth	定义排序分区点的迭代器。
policy	要使用的执行策略。有关详细信息，请参阅执行策略。
cmp	比较函数对象（即满足 Compare 要求的对象）。比较函数的签名应等同于以下内容： bool cmp(const Type1 &a, const Type2 &b); 签名不需要有 `const&`，但不得修改参数。 必须接受所有（可能是 const）Type 和 Type2 类型的值，无论其值类别如何（因此不允许 Type1&，除非对于 Type1 移动等同于复制，否则也不允许 Type1  (自 C++11 起)） `Type1` 和 `Type2` 类型必须是 `RandomIt` 类型的对象可以隐式转换为它们两者的类型。

类型要求

RandomIt	ValueSwappable LegacyRandomAccessIterator
解引用RandomIt的类型	MoveAssignable MoveConstructible
Compare	Compare

返回值

(无)

复杂度

(1, 2) 平均而言，与 std::distance(first, last) 成线性关系。

(3, 4) 给定 N 为 last - first：谓词应用 O(N) 次，交换 O(N * log(N)) 次。

异常

带有模板参数 ExecutionPolicy 的重载报告错误如下

• 如果在算法中调用的函数执行时抛出异常且 ExecutionPolicy 是标准策略之一，则调用std::terminate。对于任何其他 ExecutionPolicy，行为是实现定义的.
• 如果算法未能分配内存，则抛出 std::bad_alloc。

备注

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

示例

Main.cpp

#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <numeric>
#include <vector>

void printVec(const std::vector<int>& vec)
{
    std::cout << "v = {";
    for (auto n {vec.size()}; const int i : vec)
        std::cout << i << (--n ? ", " : "");
    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';
    // The consequence of the inequality of elements before/after the Nth one:
    assert(std::accumulate(v.begin(), m, 0) < std::accumulate(m, v.end(), 0));
    printVec(v);

    // Note: comp function changed
    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};

The median is 6
v = {3, 2, 3, 4, 5, 6, 10, 7, 9, 6};

The second largest element is 9
The largest element is 10
v = {10, 9, 6, 7, 6, 3, 5, 4, 3, 2};