std::ranges::partial_sort_copy() 算法

自 C++20 起

简化

// (1)
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 = {} );

// (2)
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 = {} );

参数类型是泛型的，并具有以下约束：

• I1, I2 - std::input_iterator, std::random_access_iterator
• S1, S2 - std::sentinel_for<I1>, std::sentinel_for<I2>
• R1, R2 - std::ranges::input_range, std::ranges::random_access_range
• Comp - （无）
• Proj1, Proj2 - (无)

对于所有重载，Proj1、Proj2 和 Comp 模板参数具有以下默认类型：std::identity、std::identity、ranges::less。

此外，每个重载都有以下约束

• (1):

  std::indirectly_copyable<I1, I2>
  && std::sortable<I2, Comp, Proj2>
  && std::indirect_strict_weak_order<
       Comp,
       std::projected<I1, Proj1>,
       std::projected<I2, Proj2>
     >
• (2):

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

详细

// (1)
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 = {} );

// (2)
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 = {} );

辅助类型定义如下：

template< class I, class O >
using partial_sort_copy_result = ranges::in_out_result<I, O>;

给定 L1 为 ranges::distance(first, last)，L2 为 ranges::distance(result_first, result_last)，N 为 ranges::min(L1, L2)

将源范围 [first; last) 中的前 N 个元素复制到目标范围 [result_first; result_first + N)，如同它已根据 comp 和 proj1 进行部分排序。

注意

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

• (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	应用于目标范围元素的投影。

返回值

给定 L1 为 ranges::distance(first, last)，L2 为 ranges::distance(result_first, result_last)，N 为 ranges::min(L1, L2)

类型为 ranges::partial_sort_copy_result 的对象，初始化如下

{
  last,
  result_first + N
}.

复杂度

给定 L1 为 ranges::distance(first, last)，L2 为 ranges::distance(result_first, result_last)，N 为 ranges::min(L1, L2)

最多 L1 * log(N) 次比较和 2 * L1 * log(N) 次投影。

异常

(无)

可能的实现

partial_sort_copy(1) 和 partial_sort_copy(2)

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};
        // copy first N elements
        for (; !(first == last or out_last == result_last); ++out_last, ++first)
            *out_last = *first;

        // convert N copied elements into a max-heap
        ranges::make_heap(result_first, out_last, comp, proj2);

        // process the rest of the input range (if any), preserving the heap property
        for (; first != last; ++first)
        {
            if (std::invoke(comp, std::invoke(proj1, *first),
                                  std::invoke(proj2, *result_first)))
            {
                // pop out the biggest item and push in a newly found smaller one
                ranges::pop_heap(result_first, out_last, comp, proj2);
                *(out_last - 1) = *first;
                ranges::push_heap(result_first, out_last, comp, proj2);
            }
        }

        // first N elements in the output range is still
        // a heap - convert it into a sorted range
        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 {};

示例

Main.cpp

#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