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

来自cppreference.com
< cpp‎ | algorithm‎ | ranges
 
 
算法库
受约束算法及范围上的算法 (C++20)
受约束算法: std::ranges::copy, std::ranges::sort, ...
执行策略 (C++17)
不修改序列的操作
(C++11)(C++11)(C++11)
(C++17)
修改序列的操作
Partitioning operations
划分操作
排序操作
(C++11)
二分搜索操作
集合操作(在已排序范围上)
堆操作
(C++11)
最小/最大操作
(C++11)
(C++17)

排列
数值运算
未初始化存储上的操作
(C++17)
(C++17)
(C++17)
C 库
 
受约束算法
不修改序列的操作
修改序列的操作
划分操作
排序操作
ranges::partial_sort_copy
二分搜索操作
集合操作(在已排序范围上)
堆操作
最小/最大操作
排列
未初始化存储上的操作
返回类型
 
在标头 <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 起)

复制来自源范围 [first, last) 的首 N 个元素,如同它按照 compproj1 部分排序,到目标范围 [result_first, result_first + N) ,其中 N = min(L₁, L₂)L₁ 等于 ranges::distance(first, last)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

此页面上描述的仿函数实体是 niebloid,即:

实际上,它们能以函数对象,或者某些特殊编译器扩展实现。

参数

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), ranges::end(r),
                       ranges::begin(result_r), ranges::end(result_r),
                       std::move(comp), std::move(proj1), std::move(proj2));
    }
};
 
inline constexpr partial_sort_copy_fn partial_sort_copy{};

示例

#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("Write to the smaller vector in ascending order: ", "");
 
    std::vector dest1{10, 11, 12};
    print("const source list: ", source);
    print("destination range: ", dest1);
    std::ranges::partial_sort_copy(source, dest1);
    print("partial_sort_copy: ", dest1);
 
    print("Write to the larger vector in descending order:", "");
 
    std::vector dest2{10, 11, 12, 13, 14, 15, 16};
    print("const source list: ", source);
    print("destination range: ", dest2);
    std::ranges::partial_sort_copy(source, dest2, std::greater{});
    print("partial_sort_copy: ", dest2);
}

输出:

Write to the smaller vector in ascending order:
const source list: 4 2 5 1 3
destination range: 10 11 12
partial_sort_copy: 1 2 3
Write to the larger vector in descending order:
const source list: 4 2 5 1 3
destination range: 10 11 12 13 14 15 16
partial_sort_copy: 5 4 3 2 1 15 16

参阅

排序一个范围的前 N 个元素
(niebloid)
将范围按升序排序
(niebloid)
将范围内的元素排序,同时保持相等的元素之间的顺序
(niebloid)
将一个最大堆变成一个按升序排序的元素范围
(niebloid)
从一个元素范围创建出一个最大堆
(niebloid)
将一个元素加入到一个最大堆
(niebloid)
从最大堆中移除最大元素
(niebloid)
对范围内的元素进行复制并部分排序
(函数模板)