std::ranges::partial_sort

Определено в заголовке <algorithm>

Подпись вызова

Определено в заголовке `<algorithm>`
Подпись вызова
template< std::random_access_iterator I, std::sentinel_for<I> S, class Comp = ranges::less, class Proj = std::identity > requires std::sortable<I, Comp, Proj> constexpr I partial_sort( I first, I middle, S last, Comp comp = {}, Proj proj = {} );	(1)	(с C++20)
template< ranges::random_access_range R, class Comp = ranges::less, class Proj = std::identity > requires std::sortable<ranges::iterator_t<R>, Comp, Proj> constexpr ranges::borrowed_iterator_t<R> partial_sort( R&& r, ranges::iterator_t<R> middle, Comp comp = {}, Proj proj = {} );	(2)	(с C++20)

template< std::random_access_iterator I, std::sentinel_for<I> S,
          class Comp = ranges::less, class Proj = std::identity >
requires std::sortable<I, Comp, Proj>
constexpr I
    partial_sort( I first, I middle, S last, Comp comp = {}, Proj proj = {} );

(1)

(с C++20)

template< ranges::random_access_range R,
          class Comp = ranges::less, class Proj = std::identity >
requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
constexpr ranges::borrowed_iterator_t<R>
    partial_sort( R&& r, ranges::iterator_t<R> middle, Comp comp = {},
                  Proj proj = {} );

(2)

(с C++20)

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

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

Элементы сравниваются с помощью заданной бинарной функции сравнения comp и проектируются с помощью proj объекта-функции.

2) То же, что и (1), но использует r в качестве диапазона, как если бы ranges::begin(r) использовалось как first и ranges::end(r) как last.

Функции, описанные на этой странице, являются неблоидами, то есть:

Явные списки аргументов шаблона не могут быть указаны при их вызове.
Ни один из них не виден для поиска аргументов по зависимости от контекста.
Когда любой из них найден обычным поиском без квалификатора в качестве имени слева от оператора вызова функции, поиск аргументов по зависимости от контекста запрещён.

На практике они могут быть реализованы как объекты-функции или с помощью специальных расширений компилятора.

Параметры

first, last	-	итератор-предел, определяющий диапазон для сортировки
r	-	диапазон для сортировки
middle	-	итератор, определяющий последний элемент, подлежащий сортировке
comp	-	компаратор, применяемый к проецированным элементам
proj	-	проекция, применяемая к элементам

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

Итератор, равный last.

Сложность

\(\scriptsize \mathcal{O}(N\cdot\log{(M)})\) сравнений и в два раза больше проекций, где \(\scriptsize N\) — ranges::distance(first, last), \(\scriptsize M\) — ranges::distance(first, middle).

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

struct partial_sort_fn
{
    template<std::random_access_iterator I, std::sentinel_for<I> S,
             class Comp = ranges::less, class Proj = std::identity>
    requires std::sortable<I, Comp, Proj>
    constexpr I
        operator()(I first, I middle, S last, Comp comp = {}, Proj proj = {}) const
    {
        if (first == middle)
            return ranges::next(first, last);
        ranges::make_heap(first, middle, comp, proj);
        auto it {middle};
        for (; it != last; ++it)
        {
            if (std::invoke(comp, std::invoke(proj, *it), std::invoke(proj, *first)))
            {
                ranges::pop_heap(first, middle, comp, proj);
                ranges::iter_swap(middle - 1, it);
                ranges::push_heap(first, middle, comp, proj);
            }
        }
        ranges::sort_heap(first, middle, comp, proj);
        return it;
    }
 
    template<ranges::random_access_range R, class Comp = ranges::less,
             class Proj = std::identity>
    requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
    constexpr ranges::borrowed_iterator_t<R>
        operator()(R&& r, ranges::iterator_t<R> middle, Comp comp = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), std::move(middle), ranges::end(r),
                       std::move(comp), std::move(proj));
    }
};
 
inline constexpr partial_sort_fn partial_sort {};

Пример

#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <vector>
 
void print(const auto& v)
{
    for (const char e : v)
        std::cout << e << ' ';
    std::cout << '\n';
}
 
void underscore(int n)
{
    while (n-- > 0)
        std::cout << "^ ";
    std::cout << '\n';
}
 
int main()
{
    static_assert('A' < 'a');
    std::vector<char> v {'x', 'P', 'y', 'C', 'z', 'w', 'P', 'o'};
    print(v);
    const int m {3};
    std::ranges::partial_sort(v, v.begin() + m);
    print(v), underscore(m);
 
    static_assert('1' < 'a');
    std::string s {"3a1b41c5"};
    print(s);
    std::ranges::partial_sort(s.begin(), s.begin() + m, s.end(), std::greater {});
    print(s), underscore(m);
}

Вывод:

x P y C z w P o
C P P y z x w o
^ ^ ^
3 a 1 b 4 1 c 5
c b a 1 3 1 4 5
^ ^ ^

См. также

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

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