std::ranges::partial_sort_copy, std::ranges::partial_sort_copy_result

定义于头文件 `<algorithm>`
调用签名
template< std::input_iterator I1, std::sentinel_for<I1> S1, std::random_access_iterator I2, std::sentinel_for<I2> S2, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity > requires std::indirectly_copyable<I1, I2> && std::sortable<I2, Comp, Proj2> && std::indirect_strict_weak_order<Comp, std::projected<I1, Proj1>, std::projected<I2, Proj2>> constexpr partial_sort_copy_result<I1, I2> partial_sort_copy( I1 first, S1 last, I2 result_first, S2 result_last, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(1)	(自 C++20)
template< ranges::input_range R1, ranges::random_access_range R2, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity > requires std::indirectly_copyable<ranges::iterator_t<R1>, ranges::iterator_t<R2>> && std::sortable<ranges::iterator_t<R2>, Comp, Proj2> && std::indirect_strict_weak_order<Comp, std::projected<ranges::iterator_t<R1>, Proj1>, std::projected<ranges::iterator_t<R2>, Proj2>> constexpr partial_sort_copy_result<ranges::borrowed_iterator_t<R1>, ranges::borrowed_iterator_t<R2>> partial_sort_copy( R1&& r, R2&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(2)	(自 C++20)
辅助类型
template< class I, class O > using partial_sort_copy_result = ranges::in_out_result<I, O>;	(3)	(自 C++20)

将源范围 N 的前 [first, last) 个元素（如同按 comp 和 proj1 进行了部分排序）复制到目标范围 [result_first, result_first + N)，其中 $\scriptsize N = \min{(L_1, L_2)}$ $N = min(L₁, L₂)$ ，$\scriptsize L_1$ $L₁$ 等于 ranges::distance(first, last)，且 $\scriptsize L_2$ $L₂$ 等于 ranges::distance(result_first, result_last)。

相等元素的顺序不保证得以保留。

1) 源范围元素使用函数对象 proj1 进行投影，目标元素使用函数对象 proj2 进行投影。

2) 与 (1) 相同，但使用 r 作为源范围，result_r 作为目标范围，如同使用 ranges::begin(r) 作为 first，ranges::end(r) 作为 last，ranges::begin(result_r) 作为 result_first，以及 ranges::end(result_r) 作为 result_last 一样。

此页面上描述的函数式实体是 算法函数对象（非正式地称为 niebloids），即：

调用它们中的任何一个时都不能指定显式模板实参列表。
它们中的任何一个都对参数依赖查找不可见。
当任何一个通过正常无限定查找被发现作为函数调用运算符左侧的名称时，参数依赖查找被禁止。

参数

first, last	-	定义待复制元素来源范围的迭代器-哨位对
r	-	待复制的来源范围
result_first, result_last	-	定义目标元素范围的迭代器-哨位对
result_r	-	目标范围
comp	-	应用于投影元素的比较器
proj1	-	应用于来源范围元素的投影器
proj2	-	应用于目标范围元素的投影器

返回值

一个等于 { last, result_first + N } 的对象。

复杂度

最多进行 $L₁•log(N)$ 次比较和 $2•L₁•log(N)$ 次投影。

可能的实现

struct partial_sort_copy_fn
{
    template<std::input_iterator I1, std::sentinel_for<I1> S1,
             std::random_access_iterator I2, std::sentinel_for<I2> S2,
             class Comp = ranges::less, class Proj1 = std::identity,
             class Proj2 = std::identity>
    requires std::indirectly_copyable<I1, I2> && std::sortable<I2, Comp, Proj2> &&
             std::indirect_strict_weak_order<Comp, std::projected<I1, Proj1>,
             std::projected<I2, Proj2>>
    constexpr ranges::partial_sort_copy_result<I1, I2>
        operator()(I1 first, S1 last, I2 result_first, S2 result_last,
                   Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        if (result_first == result_last)
            return {std::move(ranges::next(std::move(first), std::move(last))),
                    std::move(result_first)};
        auto out_last{result_first};
        // 复制前N个元素
        for (; !(first == last or out_last == result_last); ++out_last, ++first)
            *out_last = *first;
        // 将已复制的N个元素转换为最大堆
        ranges::make_heap(result_first, out_last, comp, proj2);
        // 处理输入范围的剩余部分（如有），保持堆属性
        for (; first != last; ++first)
        {
            if (std::invoke(comp, std::invoke(proj1, *first),
                                  std::invoke(proj2, *result_first)))
            {
                // 弹出最大项并推入新发现的较小项
                ranges::pop_heap(result_first, out_last, comp, proj2);
                *(out_last - 1) = *first;
                ranges::push_heap(result_first, out_last, comp, proj2);
            }
        }
        // 输出范围的前N个元素仍为堆 - 将其转换为有序范围
        ranges::sort_heap(result_first, out_last, comp, proj2);
        return {std::move(first), std::move(out_last)};
    }
    template<ranges::input_range R1, ranges::random_access_range R2,
             class Comp = ranges::less, class Proj1 = std::identity,
             class Proj2 = std::identity>
    requires std::indirectly_copyable<ranges::iterator_t<R1>, ranges::iterator_t<R2>> &&
             std::sortable<ranges::iterator_t<R2>, Comp, Proj2> &&
             std::indirect_strict_weak_order<Comp, std::projected<ranges::iterator_t<R1>,
             Proj1>, std::projected<ranges::iterator_t<R2>, Proj2>>
    constexpr ranges::partial_sort_copy_result<ranges::borrowed_iterator_t<R1>,
              ranges::borrowed_iterator_t<R2>>
        operator()(R1&& r, R2&& result_r, Comp comp = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        return (*this)(ranges::begin(r), <span class="kw290

示例

运行此代码

#include <algorithm>
#include <forward_list>
#include <functional>
#include <iostream>
#include <ranges>
#include <string_view>
#include <vector>
void print(std::string_view rem, std::ranges::input_range auto const& v)
{
    for (std::cout << rem; const auto& e : v)
        std::cout << e << ' ';
    std::cout << '\n';
}
int main()
{
    const std::forward_list source{4, 2, 5, 1, 3};
    print("按升序写入较小的向量: ", "");
    std::vector dest1{10, 11, 12};
    print("常量源列表: ", source);
    print("目标范围: ", dest1);
    std::ranges::partial_sort_copy(source, dest1);
    print("partial_sort_copy: ", dest1);
    print("按降序写入较大的向量:", "");
    std::vector dest2{10, 11, 12, 13, 14, 15, 16};
    print("常量源列表: ", source);
    print("目标范围: ", dest2);
    std::ranges::partial_sort_copy(source, dest2, std::greater{});
    print("partial_sort_copy: ", dest2);
}

输出:

按升序写入较小的向量:
常量源列表: 4 2 5 1 3
目标范围: 10 11 12
partial_sort_copy: 1 2 3
按降序写入较大的向量:
常量源列表: 4 2 5 1 3
目标范围: 10 11 12 13 14 15 16
partial_sort_copy: 5 4 3 2 1 15 16

另见

ranges::partial_sort (C++20)	排序范围中的前 N 个元素（算法函数对象）
ranges::sort (C++20)	排序范围中的元素（算法函数对象）
ranges::stable_sort (C++20)	排序范围中的元素，保持等价元素间的相对顺序（算法函数对象）
ranges::sort_heap (C++20)	将最大堆转换为一个排序的范围（算法函数对象）
ranges::make_heap (C++20)	从一个范围中创建一个最大堆（算法函数对象）
ranges::push_heap (C++20)	向最大堆中添加一个元素（算法函数对象）
ranges::pop_heap (C++20)	从最大堆中移除最大元素（算法函数对象）
partial_sort_copy	复制并部分排序一个范围内的元素（函数模板）

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

zh.cppreference.net

Namespaces

Variants

std::ranges::partial_sort_copy, std::ranges::partial_sort_copy_result

目录

参数

返回值

复杂度

可能的实现

示例

另见