std::partition
來自 cppreference.com
| 定義於標頭檔案 <algorithm> |
||
| template< class ForwardIt, class UnaryPred > ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPred p ); |
(1) | (C++20 起為 constexpr) |
| template< class ExecutionPolicy, class ForwardIt, class UnaryPred > ForwardIt partition( ExecutionPolicy&& policy, |
(2) | (C++17 起) |
1) 重新排列範圍
[first, last) 中的元素，使得謂詞 p 返回 true 的所有元素都排在謂詞 p 返回 false 的所有元素之前。元素的相對順序不保留。2) 同 (1)，但根據 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 的型別不是 Swappable(C++11 前)ForwardIt 不是 ValueSwappable(C++11 起)，則行為未定義。
目錄 |
[編輯] 引數
| first, last | - | 定義要重新排序的元素 範圍 的一對迭代器 |
| policy | - | 要使用的 執行策略 |
| p | - | 一元謂詞，若元素應排在其他元素之前則返回 true。 對於型別為 (可能為 const) |
| 型別要求 | ||
-ForwardIt 必須滿足 LegacyForwardIterator 的要求。 | ||
-UnaryPred 必須滿足 Predicate 的要求。 | ||
[編輯] 返回值
指向第二個組中第一個元素的迭代器。
[編輯] 複雜度
給定 N 為 std::distance(first, last)
1) 精確 N 次對 p 的應用。
2) O(N) 次對 p 的應用。
O(N·log(N)) 次交換。
[編輯] 異常
帶有名為 ExecutionPolicy 的模板引數的過載會按如下方式報告錯誤：
- 若演算法一部分呼叫的函式丟擲異常，且
ExecutionPolicy為 標準策略 之一，則呼叫 std::terminate。對於任何其他ExecutionPolicy，行為由實現定義。 - 如果演算法未能分配記憶體，則丟擲 std::bad_alloc。
[編輯] 可能的實現
實現過載 (1) 以保持 C++11 相容性。
template<class ForwardIt, class UnaryPred> ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPred p) { first = std::find_if_not(first, last, p); if (first == last) return first; for (auto i = std::next(first); i != last; ++i) if (p(*i)) { std::iter_swap(i, first); ++first; } return first; } |
[編輯] 示例
執行此程式碼
#include <algorithm> #include <forward_list> #include <iostream> #include <iterator> #include <vector> template<class ForwardIt> void quicksort(ForwardIt first, ForwardIt last) { if (first == last) return; auto pivot = *std::next(first, std::distance(first, last) / 2); auto middle1 = std::partition(first, last, [pivot](const auto& em) { return em < pivot; }); auto middle2 = std::partition(middle1, last, [pivot](const auto& em) { return !(pivot < em); }); quicksort(first, middle1); quicksort(middle2, last); } int main() { std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; std::cout << "Original vector: "; for (int elem : v) std::cout << elem << ' '; auto it = std::partition(v.begin(), v.end(), [](int i) {return i % 2 == 0;}); std::cout << "\nPartitioned vector: "; std::copy(std::begin(v), it, std::ostream_iterator<int>(std::cout, " ")); std::cout << "* "; std::copy(it, std::end(v), std::ostream_iterator<int>(std::cout, " ")); std::forward_list<int> fl {1, 30, -4, 3, 5, -4, 1, 6, -8, 2, -5, 64, 1, 92}; std::cout << "\nUnsorted list: "; for (int n : fl) std::cout << n << ' '; quicksort(std::begin(fl), std::end(fl)); std::cout << "\nSorted using quicksort: "; for (int fi : fl) std::cout << fi << ' '; std::cout << '\n'; }
可能的輸出
Original vector: 0 1 2 3 4 5 6 7 8 9 Partitioned vector: 0 8 2 6 4 * 5 3 7 1 9 Unsorted list: 1 30 -4 3 5 -4 1 6 -8 2 -5 64 1 92 Sorted using quicksort: -8 -5 -4 -4 1 1 1 2 3 5 6 30 64 92
[編輯] 缺陷報告
下列更改行為的缺陷報告追溯地應用於以前出版的 C++ 標準。
| 缺陷報告 | 應用於 | 釋出時的行為 | 正確的行為 |
|---|---|---|---|
| LWG 498 | C++98 | std::partition 要求 first 和last 為 LegacyBidirectionalIterator |
僅要求為 LegacyForwardIterator（傳統前向迭代器） |
| LWG 2150 | C++98 | std::partition 僅要求將一個滿足 p 的元素放置在一個不滿足 p 的元素之前 |
已更正 要求 |
[編輯] 參閱
| (C++11) |
判斷一個範圍是否按給定謂詞劃分 (函式模板) |
| 將元素分成兩組，同時保留它們的相對順序 (函式模板) | |
| (C++20) |
將一個範圍的元素分成兩組 (演算法函式物件) |
