std::partial_sort

Определён в заголовке `<algorithm>`
template< class RandomIt > void partial_sort( RandomIt first, RandomIt middle, RandomIt last );	(1)	(constexpr начиная с C++20)
template< class ExecutionPolicy, class RandomIt > void partial_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt middle, RandomIt last );	(2)	(начиная с C++17)
template< class RandomIt, class Compare > void partial_sort( RandomIt first, RandomIt middle, RandomIt last, Compare comp );	(3)	(constexpr начиная с C++20)
template< class ExecutionPolicy, class RandomIt, class Compare > void partial_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt middle, RandomIt last, Compare comp );	(4)	(начиная с C++17)

Переставляет элементы так, чтобы диапазон [first, middle) содержал отсортированные middle − first наименьших элементов в диапазоне [first, last).

Порядок равных элементов не гарантируется. Порядок остальных элементов в диапазоне [middle, last) не определён.

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, middle) или [middle, last) не является допустимым диапазоном.

Тип `*first` не является Swappable.	(до C++11)
`RandomIt` не является ValueSwappable. Тип `first` не является MoveConstructible. Тип `first` не является MoveAssignable.	(начиная с C++11)

Параметры

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

Сложность

Пусть $\scriptsize M$ $M$ = middle - first, $\scriptsize N$ $N$ = last - first:

1,2) Приблизительно

N\cdotlog(M)

сравнений с использованием operator<(до C++20)std::less{}(начиная с C++20).

3,4) Приблизительно

N\cdotlog(M)

применений компаратора comp.

Исключения

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

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

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

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

partial_sort (1)

template<typename RandomIt>
constexpr //< since C++20
void partial_sort(RandomIt first, RandomIt middle, RandomIt last)
{
    typedef typename std::iterator_traits<RandomIt>::value_type VT;
    std::partial_sort(first, middle, last, std::less<VT>());
}

partial_sort (3)

namespace impl
{
    template<typename RandomIt, typename Compare>
    constexpr //< since C++20
    void sift_down(RandomIt first, RandomIt last, const Compare& comp)
    {
        // sift down element at “first”
        const auto length = static_cast<std::size_t>(last - first);
        std::size_t current = 0;
        std::size_t next = 2;
        while (next < length)
        {
            if (comp(*(first + next), *(first + (next - 1))))
                --next;
            if (!comp(*(first + current), *(first + next)))
                return;
            std::iter_swap(first + current, first + next);
            current = next;
            next = 2 * current + 2;
        }
        --next;
        if (next < length && comp(*(first + current), *(first + next)))
            std::iter_swap(first + current, first + next);
    }

    template<typename RandomIt, typename Compare>
    constexpr //< since C++20
    void heap_select(RandomIt first, RandomIt middle, RandomIt last, const Compare& comp)
    {
        std::make_heap(first, middle, comp);
        for (auto i = middle; i != last; ++i)
        {
            if (comp(*i, *first))
            {
                std::iter_swap(first, i);
                sift_down(first, middle, comp);
            }
        }
    }
} // namespace impl

template<typename RandomIt, typename Compare>
constexpr //< since C++20
void partial_sort(RandomIt first, RandomIt middle, RandomIt last, Compare comp)
{
    impl::heap_select(first, middle, last, comp);
    std::sort_heap(first, middle, comp);
}

Примечания

Алгоритм

Обычно используется алгоритм heap select для выбора наименьших элементов, и heap sort для сортировки выбранных элементов в куче по возрастанию.

Для выбора элементов используется куча (см. heap). Например, для operator< в качестве функции сравнения используется max-heap для выбора middle − first наименьших элементов.

Heap sort используется после выбора для сортировки [first, middle) выбранных элементов (см. std::sort_heap).

Предполагаемое использование

std::partial_sort Алгоритмы предназначены для использования с малым константным числом [first, middle) выбранных элементов.

Пример

Запустить этот код

#include <algorithm>
#include <array>
#include <functional>
#include <iostream>

void print(const auto& s, int middle)
{
    for (int a : s)
        std::cout << a << ' ';
    std::cout << '\n';
    if (middle > 0)
    {
        while (middle-- > 0)
            std::cout << "--";
        std::cout << '^';
    }
    else if (middle < 0)
    {
        for (auto i = s.size() + middle; --i; std::cout << "  ")
        {}
        
        for (std::cout << '^'; middle++ < 0; std::cout << "--")
        {}
    }
    std::cout << '\n';
};

int main()
{
    std::array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
    print(s, 0);
    std::partial_sort(s.begin(), s.begin() + 3, s.end());
    print(s, 3);
    std::partial_sort(s.rbegin(), s.rbegin() + 4, s.rend());
    print(s, -4);
    std::partial_sort(s.rbegin(), s.rbegin() + 5, s.rend(), std::greater{});
    print(s, -5);
}

Возможный вывод:

5 7 4 2 8 6 1 9 0 3

0 1 2 7 8 6 5 9 4 3
------^
4 5 6 7 8 9 3 2 1 0
          ^--------
4 3 2 1 0 5 6 7 8 9
        ^----------

Отчёты о дефектах

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

DR	Применён к	Поведение в опубликованном виде	Корректное поведение
P0896R4	C++98	`[first,` `middle)` и `[middle,` `last)` не требовались как допустимые диапазоны	поведение не определено если любой из них недействителен

Смотри также

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

Поддержка компиляторов
Автономное и размещённое
Язык
Стандартная библиотека
Заголовки стандартной библиотеки
Именованные требования
Макросы тестирования возможностей (C++20)
Библиотека поддержки языка
Библиотека концепций (C++20)
Библиотека диагностики
Библиотека управления памятью
Библиотека метапрограммирования (C++11)
Библиотека общих утилит
Библиотека контейнеров
Библиотека итераторов
Библиотека диапазонов (C++20)
Библиотека алгоритмов
Библиотека строк
Библиотека обработки текста
Библиотека численных операций
Библиотека даты и времени
Библиотека ввода/вывода
Библиотека файловой системы (C++17)
Библиотека поддержки параллелизма (C++11)
Библиотека управления выполнением (C++26)
Технические спецификации
Индекс символов
Внешние библиотеки

ru.cppreference.net

Namespaces

Variants