std::ranges::partial_sort
来自cppreference.com
| 定义于头文件 <algorithm>
|
||
| 调用签名 |
||
| 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 函数对象投影元素。2) 同 (1) ，但以
r 为范围，如同以 ranges::begin(r) 为 first 并以 ranges::end(r) 为 last 。此页面上描述的仿函数实体是 niebloid ，即：
实际上，它们能以函数对象，或以某些特殊编译器扩展实现。
参数
| first, last | - | 定义要排序的范围的迭代器-哨位对 |
| r | - | 要排序的范围 |
| 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); std::ranges::partial_sort(v, v.begin() + 3); print(v); underscore(3); static_assert('1' < 'a'); std::string s{"3a1b41c5"}; print(s); std::ranges::partial_sort(s.begin(), s.begin() + 3, s.end(), std::greater{}); print(s); underscore(3); }
输出：
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) |
对范围内的元素进行复制并部分排序 (niebloid) |
| (C++20) |
将范围按升序排序 (niebloid) |
| (C++20) |
将范围内的元素排序，同时保持相等的元素之间的顺序 (niebloid) |
| (C++20) |
将给定的范围部分排序，确保其按给定元素划分 (niebloid) |
| (C++20) |
从一个元素范围创建出一个最大堆 (niebloid) |
| (C++20) |
从最大堆中移除最大元素 (niebloid) |
| (C++20) |
将一个元素加入到一个最大堆 (niebloid) |
| (C++20) |
将一个最大堆变成一个按升序排序的元素范围 (niebloid) |
| 排序一个范围的前 N 个元素 (函数模板) |