“cpp/algorithm/ranges/partial sort”的版本间的差异

来自cppreference.com

2025年2月14日 (五) 19:28的最后版本

在标头 `<algorithm>` 定义
调用签名
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 partial_sort( I first, I middle, S last, Comp comp = {}, Proj proj = {} );	(1)	(C++20 起)
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> partial_sort( R&& r, ranges::iterator_t<R> middle, Comp comp = {}, Proj proj = {} );	(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），即：

调用它们中的任何一个时不能显式指定模板实参。
它们都不对实参依赖查找可见。
在通过函数调用运算符左侧的名字进行无限定查找，找到它们之一时，禁止实参依赖查找。

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
^ ^ ^

[编辑] 参阅

ranges::partial_sort_copy (C++20)	复制范围中元素并部分排序 (算法函数对象) [编辑]
ranges::sort (C++20)	将范围按升序排序 (算法函数对象) [编辑]
ranges::stable_sort (C++20)	将范围中元素排序，同时保持相等元之间的顺序 (算法函数对象) [编辑]
ranges::nth_element (C++20)	将给定范围部分排序，确保其按给定元素划分 (算法函数对象) [编辑]
ranges::make_heap (C++20)	从元素范围创建最大堆 (算法函数对象) [编辑]
ranges::pop_heap (C++20)	移除最大堆中最大元 (算法函数对象) [编辑]
ranges::push_heap (C++20)	添加元素到最大堆 (算法函数对象) [编辑]
ranges::sort_heap (C++20)	将最大堆变成按升序排序的元素范围 (算法函数对象) [编辑]
partial_sort	将范围中前 N 个元素排序 (函数模板) [编辑]

来自“https://zh.cppreference.com/mwiki/index.php?title=cpp/algorithm/ranges/partial_sort&oldid=98844”

@@ 第2行： / 第2行： @@
 {{cpp/algorithm/ranges/navbar}}
 {{dcl begin}}
-{{dcl header | algorithm}}
+{{dcl header|algorithm}}
-{{dcl h |调用签名}}
+{{dcl h|调用签名}}
-{{dcl | since=c++20 | num=1 |1=
+{{dcl|since=c++20|num=1|1=
-template <std::random_access_iterator I, std::sentinel_for<I> S,
+template< std::random_access_iterator I, std::sentinel_for<I> S,
-         class Comp = ranges::less, class Proj = std::identity>
+class Comp = ranges::less, class Proj = std::identity >
 requires std::sortable<I, Comp, Proj>
 constexpr I
 partial_sort( I first, I middle, S last, Comp comp = {}, Proj proj = {} );
 }}
-{{dcl | since=c++20 | num= 2 |1=
+{{dcl|since=c++20|num=2|1=
-template <ranges::random_access_range R, class Comp = ranges::less,
+template< ranges::random_access_range R,
-         class Proj = std::identity>
+class Comp = ranges::less, class Proj = std::identity >
 requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
 constexpr ranges::borrowed_iterator_t<R>
-partial_sort( R&& r, ranges::iterator_t<R> middle, Comp comp = {}, Proj proj = {} );
+partial_sort( R&& r, ranges::iterator_t<R> middle, Comp comp = {},
+Proj proj = {} );
 }}
 {{dcl end}}
-@1@ 重排元素使得范围 {{tt|[first, middle)}} 含有范围 {{tt|[first, last)}} 中 {{tt|middle - first}} 个最小的元素。
+@1@ 重排元素 使得范围 {{|firstmiddle}} 含有范围 {{|firstlast}} 中 {{|middle - first}} 个最小的元素。
-@@ ''不''保证保持相等元素的顺序。范围 {{tt|[middle, last)}} 中剩余元素的顺序''未指定''。
+@@ ''不''保证保持相等元素 的顺序。范围 {{|middlelast}} 中剩余元素的顺序''未指定''。
-@@ 用给定的二元比较函数 {{tt|comp}} 比较，用 {{tt|proj}} 函数对象投影元素。
+@@ 用给定的二元比较函数 {{|comp}} 比较，用 {{|proj}} 函数对象投影元素。
-@2@ 同 {{v|1}}  ，但以 {{tt|r}} 为范围，如同以 {{c|ranges::begin(r)}} 为 {{tt|first}} 并以 {{c|ranges::end(r)}} 为 {{tt|last}}  。
+@2@ 同 {{v|1}}，但以 {{|r}} 为范围，如同以 {{c|ranges::begin(r)}} 为 {{|first}} 并以 {{c|ranges::end(r)}} 为 {{|last}}。
 {{cpp/ranges/niebloid}}
@@ 第32行： / 第33行： @@
 ===参数===
 {{par begin}}
-{{par | first, last | 定义 要排 序 的 范围的迭代器-哨位对}}
+{{par |要 排的}}
-{{par | r |  要排 序 的范围}}
+{{par|r|要 排的 范围}}
-{{par | middle |  定义要 排序 的末元素的迭代器}}
+{{par|middle| 排序}}
-{{par | comp |  应用到投影后元素的比较器}}
+{{par|comp|应用到投影后元素的比较器}}
-{{par | proj |  应用到元素的投影}}
+{{par|proj|应用到元素的投影}}
 {{par end}}
 ===返回值===
- 等于 {{tt|last}} 的迭代器。
+ 等于 {{|last}} 的迭代器。
 ===复杂度===
-{{mathjax-or|\(\scriptsize \mathcal{O}(N\cdot\log{(M)})\)|𝓞(N&middot;log(M))}} 次比较和二倍次数的投影，其中 {{mathjax-or|\(\scriptsize N\)|N}} 为 {{c|ranges::distance(first, last)}}  ， {{mathjax-or|\(\scriptsize M\)|M}} 为 {{c|ranges::distance(first, middle)}}  。
+{{mathjax-or|\(\scriptsize \mathcal{O}(N\cdot\log{(M)})\)|𝓞(N&middot;log(M))}} 次比较和二倍次数的投影，其中 {{mathjax-or|\(\scriptsize N\)|N}} 为 {{c|ranges::distance(first, last)}}，{{mathjax-or|\(\scriptsize M\)|M}} 为 {{c|ranges::distance(first, middle)}}。
 ===可能的实现===
-{{eq fun | 1=
+{{eq fun|1=
-struct partial_sort_fn {
+struct partial_sort_fn
-     template <std::random_access_iterator I, std::sentinel_for<I> S,
+{
+     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 {
+operator()(I first, I middle, S last, Comp comp = {}, Proj proj = {}) const
-         if (first == middle) return ranges::next(first, last);
+{
+         if (first == middle)
+return ranges::next(first, last);
          ranges::make_heap(first, middle, comp, proj);
          auto it {middle};
-         for (; it != last; ++it) {
+         for (; it != last; ++it)
-             if (std::invoke(comp, std::invoke(proj, *it), std::invoke(proj, *first))) {
+{
+             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);
@@ 第67行： / 第73行： @@
      }
-     template <ranges::random_access_range R, class Comp = ranges::less,
+     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 {
+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));
@@ 第77行： / 第84行： @@
 };
-inline constexpr partial_sort_fn partial_sort{};
+inline constexpr partial_sort_fn partial_sort {};
 }}
 ===示例===
-{{example| code=
+{{example|code=
 #include <algorithm>
 #include <functional>
@@ 第88行： / 第95行： @@
 #include <vector>
-void print(const auto& v) {
+void print(const auto& v)
-     for (const char e : v) { std::cout << e << ' '; }
+{
+     for (const char e : v)
+std::cout << e << ' ';
      std::cout << '\n';
 }
-void underscore(int n) {
+void underscore(int n)
-     while (n-- > 0) { std::cout << "^ "; }
+{
+     while (n-- > 0)
+std::cout << "^ ";
      std::cout << '\n';
 }
@@ 第101行： / 第112行： @@
 {
      static_assert('A' < 'a');
-     std::vector<char> v{'x', 'P', 'y', 'C', 'z', 'w', 'P', 'o'};
+     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);
+     std::ranges::partial_sort(v, v.begin() + );
+     print(v)underscore();
      static_assert('1' < 'a');
-     std::string s{"3a1b41c5"};
+     std::string s {"3a1b41c5"};
      print(s);
-     std::ranges::partial_sort(s.begin(), s.begin() + 3, s.end(), std::greater{});
+     std::ranges::partial_sort(s.begin(), s.begin() + , s.end(), std::greater {});
-     print(s); underscore(3);
+     print(s)underscore();
 }
-| output=
+|output=
 x P y C z w P o
 C P P y z x w o
@@ 第123行： / 第135行： @@
 ===参阅===
 {{dsc begin}}
-{{dsc inc | cpp/algorithm/ranges/dsc partial_sort_copy}}
+{{dsc inc|cpp/algorithm/ranges/dsc partial_sort_copy}}
-{{dsc inc | cpp/algorithm/ranges/dsc sort}}
+{{dsc inc|cpp/algorithm/ranges/dsc sort}}
-{{dsc inc | cpp/algorithm/ranges/dsc stable_sort}}
+{{dsc inc|cpp/algorithm/ranges/dsc stable_sort}}
-{{dsc inc | cpp/algorithm/ranges/dsc nth_element}}
+{{dsc inc|cpp/algorithm/ranges/dsc nth_element}}
-{{dsc inc | cpp/algorithm/ranges/dsc make_heap}}
+{{dsc inc|cpp/algorithm/ranges/dsc make_heap}}
-{{dsc inc | cpp/algorithm/ranges/dsc pop_heap}}
+{{dsc inc|cpp/algorithm/ranges/dsc pop_heap}}
-{{dsc inc | cpp/algorithm/ranges/dsc push_heap}}
+{{dsc inc|cpp/algorithm/ranges/dsc push_heap}}
-{{dsc inc | cpp/algorithm/ranges/dsc sort_heap}}
+{{dsc inc|cpp/algorithm/ranges/dsc sort_heap}}
-{{dsc inc | cpp/algorithm/dsc partial_sort}}
+{{dsc inc|cpp/algorithm/dsc partial_sort}}
 {{dsc end}}
 {{langlinks|de|en|es|fr|it|ja|pt|ru}}

编译器支持
自立实现与有宿主实现
语言
标准库
标准库标头
具名要求
功能特性测试宏 (C++20)
语言支持库
概念库 (C++20)
诊断库
内存管理库
元编程库 (C++11)
通用工具库
容器库
迭代器库
范围库 (C++20)
算法库
字符串库
文本处理库
数值库
日期和时间库
输入/输出库
文件系统库 (C++17)
并发支持库 (C++11)
执行控制库 (C++26)
技术规范
符号索引
外部库

first, last	-	要重排的元素范围的迭代器-哨位对
r	-	要重排的元素范围
middle	-	将对范围 `[`first`,` middle`)` 排序
comp	-	应用到投影后元素的比较器
proj	-	应用到元素的投影

cppreference.com

名字空间

变换

查看

操作

“cpp/algorithm/ranges/partial sort”的版本间的差异

2025年2月14日 (五) 19:28的最后版本

目录

[编辑] 参数

[编辑] 返回值

[编辑] 复杂度

[编辑] 可能的实现

[编辑] 示例

[编辑] 参阅

导航

工具箱