std::partial_sort

Определён в заголовочном файле `<algorithm>`
template< class RandomIt > void partial_sort( RandomIt first, RandomIt middle, RandomIt last );	(1)	(начиная с C++20, constexpr)
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)	(начиная с C++20, constexpr)
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`, если первый аргумент меньше второго (то есть упорядочен перед ним). Сигнатура функции сравнения должна быть эквивалентна следующей: boolcmp(constType1&a,constType2&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) Приблизительно \(\scriptsize N \cdot \log(M)\)N·log(M) сравнений с использованием operator<(до C++20)std::less{}(начиная с C++20).

3,4) Приблизительно \(\scriptsize N \cdot \log(M)\)N·log(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); }

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

Примечания

Алгоритм

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

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

После выбора используется сортировка кучей, чтобы отсортировать [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 элементов диапазона (объект-функция алгоритма)

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