std::ranges::partial_sort
來自 cppreference.com
| 定義於標頭檔案 <algorithm> |
||
| 呼叫簽名 (Call signature) |
||
| template< std::random_access_iterator I, std::sentinel_for<I> S, class Comp = ranges::less, class Proj = std::identity > |
(1) | (C++20 起) |
| template< ranges::random_access_range R, class Comp = ranges::less, class Proj = std::identity > |
(2) | (C++20 起) |
1) 重新排列元素，使得範圍
[first, middle) 包含範圍 [first, last) 中最小的 middle - first 個已排序元素。 相等元素的順序**不**保證保留。範圍
[middle, last) 中剩餘元素的順序**未指定**。 元素使用給定的二元比較函式 comp 進行比較，並使用 proj 函式物件進行投影。
本頁描述的類函式實體是 演算法函式物件（非正式地稱為 niebloids），即
目錄 |
[編輯] 引數
| first, last | - | 定義要重新排列元素的範圍的迭代器-哨兵對 |
| r | - | 要重新排列的元素範圍 |
| middle | - | 範圍 [first, middle) 將被排序 |
| comp | - | 應用於投影元素的比較器 |
| proj | - | 應用於元素的投影 |
[編輯] 返回值
一個等於 last 的迭代器。
[編輯] 複雜度
𝓞(N·log(M)) 次比較，兩倍的投影操作，其中 N 是 ranges::distance(first, last)，M 是 ranges::distance(first, middle)。
[編輯] 可能的實現
struct partial_sort_fn { template<std::random_access_iterator I, std::sentinel_for<I> S, class Comp = ranges::less, class Proj = std::identity> requires std::sortable<I, Comp, Proj> constexpr I operator()(I first, I middle, S last, Comp comp = {}, Proj proj = {}) const { if (first == middle) return ranges::next(first, last); ranges::make_heap(first, middle, comp, proj); auto it {middle}; for (; it != last; ++it) { if (std::invoke(comp, std::invoke(proj, *it), std::invoke(proj, *first))) { ranges::pop_heap(first, middle, comp, proj); ranges::iter_swap(middle - 1, it); ranges::push_heap(first, middle, comp, proj); } } ranges::sort_heap(first, middle, comp, proj); return it; } template<ranges::random_access_range R, class Comp = ranges::less, class Proj = std::identity> requires std::sortable<ranges::iterator_t<R>, Comp, Proj> constexpr ranges::borrowed_iterator_t<R> operator()(R&& r, ranges::iterator_t<R> middle, Comp comp = {}, Proj proj = {}) const { return (*this)(ranges::begin(r), std::move(middle), ranges::end(r), std::move(comp), std::move(proj)); } }; inline constexpr partial_sort_fn partial_sort {}; |
[編輯] 示例
執行此程式碼
#include <algorithm> #include <functional> #include <iostream> #include <string> #include <vector> void print(const auto& v) { for (const char e : v) std::cout << e << ' '; std::cout << '\n'; } void underscore(int n) { while (n-- > 0) std::cout << "^ "; std::cout << '\n'; } int main() { static_assert('A' < 'a'); std::vector<char> v {'x', 'P', 'y', 'C', 'z', 'w', 'P', 'o'}; print(v); const int m {3}; std::ranges::partial_sort(v, v.begin() + m); print(v), underscore(m); static_assert('1' < 'a'); std::string s {"3a1b41c5"}; print(s); std::ranges::partial_sort(s.begin(), s.begin() + m, s.end(), std::greater {}); print(s), underscore(m); }
輸出
x P y C z w P o C P P y z x w o ^ ^ ^ 3 a 1 b 4 1 c 5 c b a 1 3 1 4 5 ^ ^ ^
[編輯] 參閱
| (C++20) |
複製並部分排序一個範圍的元素 (演算法函式物件) |
| (C++20) |
將一個範圍按升序排序 (演算法函式物件) |
| (C++20) |
對一個範圍的元素進行排序，同時保留相等元素之間的順序 (演算法函式物件) |
| (C++20) |
部分排序給定的範圍，確保它被給定的元素劃分 (演算法函式物件) |
| (C++20) |
從一個元素範圍建立一個最大堆 (演算法函式物件) |
| (C++20) |
從一個最大堆中移除最大的元素 (演算法函式物件) |
| (C++20) |
向一個最大堆新增一個元素 (演算法函式物件) |
| (C++20) |
將一個最大堆轉換成一個按升序排序的元素範圍 (演算法函式物件) |
| 對一個範圍的前 N 個元素進行排序 (函式模板) |
