std::partial_sort_copy

定義於標頭檔案 `<algorithm>`
template< class InputIt, class RandomIt > RandomIt partial_sort_copy( InputIt first, InputIt last, RandomIt d_first, RandomIt d_last );	(1)	(C++20 起為 constexpr)
template< class ExecutionPolicy, class ForwardIt, class RandomIt > RandomIt partial_sort_copy( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, RandomIt d_first, RandomIt d_last );	(2)	(C++17 起)
template< class InputIt, class RandomIt, class Compare > RandomIt partial_sort_copy( InputIt first, InputIt last, RandomIt d_first, RandomIt d_last, Compare comp );	(3)	(C++20 起為 constexpr)
template< class ExecutionPolicy, class ForwardIt, class RandomIt, class Compare > RandomIt partial_sort_copy( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, RandomIt d_first, RandomIt d_last, Compare comp );	(4)	(C++17 起)

以升序對範圍 [first, last) 中的部分元素進行排序，並將結果儲存在範圍 [d_first, d_last) 中。

最多 d_last - d_first 個元素被排序並放置到範圍 [d_first, d_first + n) 中。n 是要排序的元素數量（std::min(std::distance(first, last), d_last - d_first)）。不保證相等元素的順序。

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 起)

若 *first 不可寫入到 d_first，則程式非良構。

如果滿足以下任何條件，則行為是未定義的：

*d_first 的型別不是可交換 (Swappable)。	(C++11 前)
`RandomIt` 不是可值交換的 (ValueSwappable)。 d_first 的型別不是可移動構造 (MoveConstructible)。 d_first 的型別不是可移動賦值 (MoveAssignable)。	(C++11 起)

first, last	-	定義待排序元素範圍的迭代器對
d_first, d_last	-	定義排序資料將要被賦值到的元素範圍的迭代器對
policy	-	要使用的執行策略
comp	-	比較函式物件（即滿足比較 (Compare) 要求的物件），若第一個引數小於（即在第二個引數之前排序）第二個引數，則返回 true。比較函式的簽名應等效於以下內容 bool cmp(const Type1& a, const Type2& b); 儘管簽名無需具有 const&，但函式必須不修改傳遞給它的物件，並且必須能夠接受 `Type1` 和 `Type2` 型別（可能是 const）的所有值，而不管值類別（因此，不允許 `Type1&`；除非對於 `Type1` 移動等效於複製，否則也不允許 `Type1`(C++11 起)）。型別 Type1 和 Type2 必須使得型別 RandomIt 的物件可被解引用，然後隱式轉換為兩者。
型別要求
- `InputIt` 必須滿足 LegacyInputIterator 的要求。
- `ForwardIt` 必須滿足 LegacyForwardIterator 的要求。
- `RandomIt` 必須滿足舊式隨機訪問迭代器 (LegacyRandomAccessIterator) 的要求。
- `Compare` 必須滿足 Compare 的要求。

[編輯] 返回值

指向定義排序範圍上邊界的元素的迭代器，即 d_first + std::min(std::distance(first, last), d_last - d_first)。

[編輯] 複雜度

給定 $\scriptsize N$ $N$ 為 std::distance(first, last)，$\scriptsize D$ $D$ 為 d_last - d_first

1,2) 大約

N\cdotlog(min(N,D))

次比較，使用 operator<(C++20 前)std::less{}(C++20 起)。

3,4) 大約

N\cdotlog(min(N,D))

次比較器 comp 的應用。

[編輯] 異常

帶有模板引數 ExecutionPolicy 的過載按如下方式報告錯誤

若作為演算法一部分呼叫的函式執行丟擲異常，且 ExecutionPolicy 為標準策略之一，則呼叫 std::terminate。對於任何其他 ExecutionPolicy，行為由實現定義。
如果演算法未能分配記憶體，則丟擲 std::bad_alloc。

[編輯] 可能的實現

另請參閱 libstdc++ 和 libc++ 中的實現。

[編輯] 示例

以下程式碼對一個整數向量進行排序，並將其複製到較小的和較大的向量中。

執行此程式碼

#include <algorithm>
#include <functional>
#include <iostream>
#include <string_view>
#include <type_traits>
#include <vector>
 
void println(std::string_view rem, const auto& v)
{
    std::cout << rem;
    if constexpr (std::is_scalar_v<std::decay_t<decltype(v)>>)
        std::cout << v;
    else
        for (int e : v)
            std::cout << e << ' ';
    std::cout << '\n';
}
 
int main()
{
    const auto v0 = {4, 2, 5, 1, 3};
    std::vector<int> v1{10, 11, 12};
    std::vector<int> v2{10, 11, 12, 13, 14, 15, 16};
    std::vector<int>::iterator it;
 
    it = std::partial_sort_copy(v0.begin(), v0.end(), v1.begin(), v1.end());
    println("Writing to the smaller vector in ascending order gives: ", v1);
 
    if (it == v1.end())
        println("The return value is the end iterator", ' ');
 
    it = std::partial_sort_copy(v0.begin(), v0.end(), v2.begin(), v2.end(),
                                std::greater<int>());
 
    println("Writing to the larger vector in descending order gives: ", v2);
    println("The return value is the iterator to ", *it);
}

輸出

Writing to the smaller vector in ascending order gives: 1 2 3
The return value is the end iterator
Writing to the larger vector in descending order gives: 5 4 3 2 1 15 16
The return value is the iterator to 15

[編輯] 缺陷報告

下列更改行為的缺陷報告追溯地應用於以前出版的 C++ 標準。

缺陷報告	應用於	釋出時的行為	正確的行為
P0896R4	C++98	*first 不需要可寫入 d_first	若不可寫入，則程式非良構

[編輯] 參閱

partial_sort	對一個範圍的前 N 個元素進行排序 (函式模板) [編輯]
sort	將一個範圍按升序排序 (函式模板) [編輯]
stable_sort	對一個範圍的元素進行排序，同時保留相等元素之間的順序 (函式模板) [編輯]
ranges::partial_sort_copy (C++20)	複製並部分排序一個範圍的元素 (演算法函式物件)[編輯]

編譯器支援
自由（freestanding）與宿主（hosted）
語言
標準庫
標準庫標頭檔案
具名要求
特性測試宏 (C++20)
語言支援庫
概念庫 (C++20)
診斷庫
記憶體管理庫
超程式設計庫 (C++11)
通用工具庫
容器庫
迭代器庫
範圍庫 (C++20)
演算法庫
字串庫
文字處理庫
數值庫
日期和時間庫
輸入/輸出庫
檔案系統庫 (C++17)
併發支援庫 (C++11)
執行控制庫 (C++26)
技術規範
符號索引
外部庫

cppreference.com

名稱空間

變體

檢視

操作