std::partial_sort

Определено в заголовке `<algorithm>`
	(1)
template< class RandomIt > void partial_sort( RandomIt first, RandomIt middle, RandomIt last );		(до C++20)
template< class RandomIt > constexpr void partial_sort( RandomIt first, RandomIt middle, RandomIt last );		(с C++20)
template< class ExecutionPolicy, class RandomIt > void partial_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt middle, RandomIt last );	(2)	(с C++17)
	(3)
template< class RandomIt, class Compare > void partial_sort( RandomIt first, RandomIt middle, RandomIt last, Compare comp );		(до C++20)
template< class RandomIt, class Compare > constexpr void partial_sort( RandomIt first, RandomIt middle, RandomIt last, Compare comp );		(с 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<.

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	-	итераторы произвольного доступа, определяющие диапазон
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` должен удовлетворять требованиям ValueSwappable и LegacyRandomAccessIterator.
-Тип дезаргументированного `RandomIt` должен удовлетворять требованиям MoveAssignable и MoveConstructible.

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

(нет)

Сложность

Приблизительно (last-first)log(middle-first) применений cmp.

Исключения

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

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

Примечания

Алгоритм

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

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

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

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

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

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

См. также реализации в 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 void sift_down(RandomIt first, RandomIt last, const Compare& comp) { // sift down element at 'first' const auto length = static_cast<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 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
    void sift_down(RandomIt first, RandomIt last, const Compare& comp)
    {
        // sift down element at 'first'
        const auto length = static_cast<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
    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);
}

Пример

#include <algorithm>
#include <array>
#include <functional>
#include <iostream>
 
void print(auto const& 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
        ^----------

См. также

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

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