Difference between revisions of "cpp/algorithm/ranges/partial sort copy"

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 {};