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

Defined in header `<algorithm>`
Call signature
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)	(since 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)	(since C++20)
Helper types
template< class I, class O > using partial_sort_copy_result = ranges::in_out_result<I, O>;	(3)	(since 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}.

Сложность

Максимум \(\scriptsize L_1 \cdot \log{(N)}\)L₁•log(N) сравнений и \(\scriptsize 2 \cdot L_1 \cdot \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};
        // 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 {};

Пример

#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

См. также

ranges::partial_sort (C++20)	сортирует первые N элементов диапазона (niebloid)
ranges::sort (C++20)	сортирует диапазон в порядке возрастания (niebloid)
ranges::stable_sort (C++20)	сортирует диапазон элементов, сохраняя порядок между равными элементами (niebloid)
ranges::sort_heap (C++20)	преобразует кучу в диапазон элементов, отсортированных в порядке возрастания (niebloid)
ranges::make_heap (C++20)	создаёт кучу из диапазона элементов (niebloid)
ranges::push_heap (C++20)	добавляет элемент в кучу (niebloid)
ranges::pop_heap (C++20)	удаляет наибольший элемент из кучи (niebloid)
partial_sort_copy	копирует и частично сортирует диапазон элементов (функция-шаблон)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/algorithm/ranges/partial_sort_copy