std::ranges:: partial_sort
std::ranges
| Non-modifying sequence operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Modifying sequence operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Partitioning operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Sorting operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Binary search operations (on sorted ranges) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Set operations (on sorted ranges) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Heap operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Minimum/maximum operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Permutation operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Fold operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Operations on uninitialized storage | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Return types | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
定义于头文件
<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 起) |
[
first
,
middle
)
包含范围
[
first
,
last
)
中已排序的
middle
-
first
个最小元素。
[
middle
,
last
)
中剩余元素的顺序是
未指定的
。
本页面描述的函数式实体是 算法函数对象 （非正式称为 niebloids ），即：
目录 |
参数
| first, last | - | 定义待重排元素范围的 区间 的迭代器-哨位对 |
| r | - | 待重排的元素范围 |
| middle | - |
区间
[
first
,
middle
)
将被排序
|
| comp | - | 应用于投影元素的比较器 |
| proj | - | 应用于元素的投影 |
返回值
一个等于 last 的迭代器。
复杂度
\(\scriptsize \mathcal{O}(N\cdot\log{(M)})\) 𝓞(N·log(M)) 次比较和两倍的投影次数，其中 \(\scriptsize N\) N 是 ranges:: distance ( first, last ) ， \(\scriptsize M\) 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个元素
(函数模板) |