std::partial_sort_copy

Определено в заголовке `<algorithm>`
	(1)
template< class InputIt, class RandomIt > RandomIt partial_sort_copy( InputIt first, InputIt last, RandomIt d_first, RandomIt d_last );		(до C++20)
template< class InputIt, class RandomIt > constexpr RandomIt partial_sort_copy( InputIt first, InputIt last, RandomIt d_first, RandomIt d_last );		(с C++20)
template< class ExecutionPolicy, class ForwardIt, class RandomIt > RandomIt partial_sort_copy( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, RandomIt d_first, RandomIt d_last );	(2)	(с C++17)
	(3)
template< class InputIt, class RandomIt, class Compare > RandomIt partial_sort_copy( InputIt first, InputIt last, RandomIt d_first, RandomIt d_last, Compare comp );		(до C++20)
template< class InputIt, class RandomIt, class Compare > constexpr RandomIt partial_sort_copy( InputIt first, InputIt last, RandomIt d_first, RandomIt d_last, Compare comp );		(с C++20)
template< class ExecutionPolicy, class ForwardIt, class RandomIt, class Compare > RandomIt partial_sort_copy( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, RandomIt d_first, RandomIt d_last, Compare comp );	(4)	(с C++17)

Сортирует часть элементов в диапазоне [first, last) в порядке возрастания, сохраняя результат в диапазоне [d_first, d_last).

Максимальное количество элементов, помещаемых в отсортированном виде в диапазон [d_first, d_first + n), равно d_last - d_first. n — это количество элементов для сортировки (n = min(last - first, d_last - d_first)). Порядок одинаковых элементов не гарантируется.

1) Элементы сравниваются с использованием operator<.

3) Элементы сравниваются с использованием заданной двоичной функции сравнения comp.

2,4) Также как в (1,3), но выполняются согласно policy. Эти перегрузки не участвуют в разрешении перегрузок, если

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>` является `true`.	(до C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>` является `true`.	(с C++20)

Параметры

first, last	-	диапазон элементов для сортировки
d_first, d_last	-	итераторы произвольного доступа, определяющие целевой диапазон
policy	-	политика выполнения. Подробности см. в политике выполнения.
comp	-	объект-функция сравнения (объект, удовлетворяющий требованиям Compare), возвращающий `true` если первый аргумент меньше (т.е. упорядочен раньше) второго. Подпись функции сравнения должна быть эквивалентной следующей: `bool cmp(const Type1& a, const Type2& b);` Хотя подпись не должна содержать const&, функция не должна изменять передаваемые ей объекты и должна уметь принимать все значения типа (возможно, const) `Type1` и `Type2` независимо от категории значения (следовательно, `Type1&` недопустимо, а также `Type1` если для `Type1` перемещение эквивалентно копированию(с C++11)). Типы Type1 и Type2 должны быть такими, чтобы объект типа RandomIt можно было разыменовать и затем неявно преобразовать в оба из них.
Требования к типу
-`InputIt` должно соответствовать требованиям LegacyInputIterator.
-`ForwardIt` должно соответствовать требованиям LegacyForwardIterator.
-`RandomIt` должно соответствовать требованиям ValueSwappable и LegacyRandomAccessIterator.
-Тип разыменованного `RandomIt` должен соответствовать требованиям MoveAssignable и MoveConstructible.

Возвращаемое значение

Итератор на элемент, определяющий верхнюю границу отсортированного диапазона, т.е. d_first + min(last - first, d_last - d_first).

Сложность

O(N·log(min(D,N)), где N = std::distance(first, last), D = std::distance(d_first, d_last) применения cmp.

Исключения

Перегрузки с параметром шаблона под названием ExecutionPolicy сообщают об ошибках следующим образом:

Если выполнение функции, вызываемой как часть алгоритма, вызывает исключение, и ExecutionPolicy является одной из стандартных политик, то std::terminate вызывается. Для любой другой ExecutionPolicy, поведение определяется реализацией.
Если алгоритм не может выделить память, то выбрасывается std::bad_alloc.

Возможная реализация

См. также реализации в libstdc++ и libc++.

Пример

Следующий код сортирует вектор целых чисел и копирует их в меньший и больший вектор.

#include <algorithm>
#include <functional>
#include <iostream>
#include <string_view>
#include <type_traits>
#include <vector>
 
void println(std::string_view rem, auto const& v)
{
    std::cout << rem;
    if constexpr (std::is_scalar_v<std::decay_t<decltype(v)>>)
        std::cout << v;
    else
        for (int e : v)
            std::cout << e << ' ';
    std::cout << '\n';
}
 
int main()
{
    const auto v0 = {4, 2, 5, 1, 3};
    std::vector<int> v1 {10, 11, 12};
    std::vector<int> v2 {10, 11, 12, 13, 14, 15, 16};
    std::vector<int>::iterator it;
 
    it = std::partial_sort_copy(v0.begin(), v0.end(), v1.begin(), v1.end());
    println("Writing to the smaller vector in ascending order gives: ", v1);
 
    if (it == v1.end())
        println("The return value is the end iterator", ' ');
 
    it = std::partial_sort_copy(v0.begin(), v0.end(), v2.begin(), v2.end(),
                                std::greater<int>());
 
    println("Writing to the larger vector in descending order gives: ", v2);
    println("The return value is the iterator to ", *it);
}

Вывод:

Writing to the smaller vector in ascending order gives: 1 2 3
The return value is the end iterator
Writing to the larger vector in descending order gives: 5 4 3 2 1 15 16
The return value is the iterator to 15

См. также

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

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