std::nth_element

出自cppreference.com
 
C++
 
算法庫
受約束算法及範圍上的算法 (C++20)
包含算法例如 ranges::copy, ranges::sort, ...
執行策略 (C++17)
排序和相關操作
劃分操作
排序操作
二分搜索操作（在已劃分範圍上）
集合操作（在有序範圍上）
歸併操作（在有序範圍上）
堆操作
最小/最大操作
(C++11)
(C++17)
字典序比較操作
(C++20)
排列操作
C 庫

數值運算
(C++11)                       
在未初始化內存上的操作
 
在標頭 <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) 已排序則該位置會出現的元素。
  • [first, nth) 中的每個迭代器 i 和 [nth, last) 中的每個迭代器 j 滿足以下條件：
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 執行。
這些重載只有在滿足以下所有條件時才會參與重載決議：

std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> 是 true。

(C++20 前)

std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> 是 true。

(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 中的實現。

註解

典型地使用內省選擇算法，但也允許其他擁有適合平均情況複雜度的選擇算法。

示例

運行此代碼
#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 << "\n中值为 " << 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 << "\n第二大的元素是 " << v[1] << '\n';
    std::cout << "最大的元素是 " << 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)
 將給定範圍部分排序，確保其按給定元素劃分
(算法函數對象) [編輯]