std::ranges::partial_sort() algorithm

od C++20

Simplified

// (1)
constexpr I
    partial_sort( I first, I middle, S last, Comp comp = {}, Proj proj = {} );

// (2)
constexpr ranges::borrowed_iterator_t<R>
    partial_sort( R&& r, ranges::iterator_t<R> middle, Comp comp = {}, Proj proj = {} );

The type of arguments are generic and have following constraints:

• I - std::random_access_iterator
• S - std::sentinel_for<I>
• R - std::ranges::random_access_range
• Comp - (none)
• Proj - (none)

The Proj and Comp template arguments have, the following default types for all overloads: std::identity, ranges::less.

Additionally, each overload has the following constraints:

• (1) - std::sortable<I, Comp, Proj>
• (2) - std::sortable<ranges::iterator_t<R>, Comp, Proj>

Detailed

// (1)
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 = {} );

// (2)
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 = {} );

Rearranges elements such that the range [first; middle) contains the sorted middle - first smallest elements in the range [first; last).

The elements are compared using the given binary comparison function comp and projected using proj function object.

uwaga

The order of equal elements is not guaranteed to be preserved.

The order of the remaining elements in the range [middle; last) is unspecified.

• (1) Elements are compared using the given binary comparison function comp.

• (2) Same as (1), but uses r as the source range, as if using ranges::begin(r) as first and ranges::end(r) as last.

The function-like entities described on this page are niebloids.

Parameters

first last	The entire range which part should be sorted.
r	The entire range which part should be sorted.
middle	The iterator defining the last element to be sorted.
comp	Comparison object to apply to the projected elements.
proj	Projection to apply to the elements.

Return value

An iterator equal to last.

Complexity

Given N as ranges::distance(first, last) and M as ranges::distance(first, middle):

O(N * log(M)) comparisons and twice as many projections.

Exceptions

(none)

Possible implementation

partial_sort(1) and partial_sort(2)

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

Examples

Main.cpp

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

Output

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
^ ^ ^