std::partial_sort_copy

Определён в заголовочном файле `<algorithm>`
template< class InputIt, class RandomIt > RandomIt partial_sort_copy( InputIt first, InputIt last, RandomIt d_first, RandomIt d_last );	(1)	(constexpr с 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)
template< class InputIt, class RandomIt, class Compare > RandomIt partial_sort_copy( InputIt first, InputIt last, RandomIt d_first, RandomIt d_last, Compare comp );	(3)	(constexpr с 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 — это число элементов для сортировки (std::min(std::distance(first, last), d_last - d_first)). Порядок эквивалентных элементов не гарантируется.

1) Элементы сортируются относительно operator<(до C++20)std::less{}(с C++20).

3) Элементы сортируются относительно comp.

2,4) То же, что и (1,3), но выполняется согласно policy.

Эти перегрузки участвуют в разрешении перегрузки, только если значение следующего выражения равно true:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(до C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(с C++20)

Если *first нельзя записать в d_first, программа некорректна.

Если выполняется любое из следующих условий, поведение не определено:

Тип `*d_first` не удовлетворяет требованиям Swappable.	(до C++11)
`RandomIt` не удовлетворяет требованиям ValueSwappable. Тип `d_first` не удовлетворяет требованиям MoveConstructible. Тип `d_first` не удовлетворяет требованиям MoveAssignable.	(с C++11)

Параметры

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

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

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

Сложность

Пусть \(\scriptsize N\)N — std::distance(first, last), а \(\scriptsize D\)D — d_last - d_first:

1,2) Примерно \(\scriptsize N \cdot \log(\min(N,D))\)N·log(min(N,D)) сравнений с использованием operator<(до C++20)std::less{}(с C++20).

3,4) Примерно \(\scriptsize N \cdot \log(\min(N,D))\)N·log(min(N,D)) вызовов объекта сравнения comp.

Исключения

Перегрузки с параметром шаблона с именем 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, const auto& 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

Отчёты об ошибках

Следующие отчёты об ошибках, изменяющие поведение, были ретроактивно применены к ранее опубликованным стандартам C++.

Отчёт об ошибке	Применён к	Опубликованное поведение	Корректное поведение
P0896R4	C++98	Для `*first` не требовалось, чтобы в него можно было записывать из `d_first`	программа некорректна, если запись невозможна

См. также

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

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