std::ranges::partial_sort_copy, std::ranges::partial_sort_copy_result

Defined in header `<algorithm>`
Call signature
template< std::input_iterator I1, std::sentinel_for<I1> S1, std::random_access_iterator I2, std::sentinel_for<I2> S2, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity > requires std::indirectly_copyable<I1, I2> && std::sortable<I2, Comp, Proj2> && std::indirect_strict_weak_order<Comp, std::projected<I1, Proj1>, std::projected<I2, Proj2>> constexpr ranges::partial_sort_copy_result<I1, I2> partial_sort_copy( I1 first, S1 last, I2 d_first, S2 d_last, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(1)	(since C++20)
template< ranges::input_range R1, ranges::random_access_range R2, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity > requires std::indirectly_copyable<ranges::iterator_t<R1>, ranges::iterator_t<R2>> && std::sortable<ranges::iterator_t<R2>, Comp, Proj2> && std::indirect_strict_weak_order <Comp, std::projected<ranges::iterator_t<R1>, Proj1>, std::projected<ranges::iterator_t<R2>, Proj2>> constexpr ranges::partial_sort_copy_result<ranges::borrowed_iterator_t<R1>, ranges::borrowed_iterator_t<R2>> partial_sort_copy( R1&& r, R2&& d_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(2)	(since C++20)
template< /execution-policy/ Ep, std::random_access_iterator I1, std::sized_sentinel_for<I1> S1, std::random_access_iterator I2, std::sized_sentinel_for<I2> S2, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity > requires std::indirectly_copyable<I1, I2> && std::sortable<I2, Comp, Proj2> && std::indirect_strict_weak_order<Comp, std::projected<I1, Proj1>, std::projected<I2, Proj2>> ranges::partial_sort_copy_result<I1, I2> partial_sort_copy( Ep&& policy, I1 first, S1 last, I2 d_first, S2 d_last, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(3)	(since C++26)
template< /execution-policy/ Ep, /sized-random-access-range/ R1, /sized-random-access-range/ R2, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity > requires std::indirectly_copyable<ranges::iterator_t<R1>, ranges::iterator_t<R2>> && std::sortable<ranges::iterator_t<R2>, Comp, Proj2> && std::indirect_strict_weak_order <Comp, std::projected<ranges::iterator_t<R1>, Proj1>, std::projected<ranges::iterator_t<R2>, Proj2>> ranges::partial_sort_copy_result<ranges::borrowed_iterator_t<R1>, ranges::borrowed_iterator_t<R2>> partial_sort_copy( Ep&& policy, R1&& r, R2&& d_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(4)	(since C++26)
Helper types
template< class I, class O > using partial_sort_copy_result = ranges::in_out_result<I, O>;	(5)	(since C++20)

For the definition of /*execution-policy*/, see this page; for the definition of /*sized-random-access-range*/, see this page.

Copies elements from the source range as sorted with respect to the comparator comp and projection proj1 into the destination range.

1) The source range is [first, last), and the destination range is [d_first, d_last).

If ranges::distance(first, last) is greater than ranges::distance(d_first, d_last), the first ranges::distance(d_first, d_last) elements of the source range are copied as sorted into [d_first, d_last).
Otherwise, all elements of the source range are copied as sorted into [d_first, d_first + ranges::distance(first, last)).

2) The source range is r, and the destination range is d_r.

If ranges::distance(r) is greater than ranges::distance(d_r), the first ranges::distance(d_r) elements of the source range are copied as sorted into d_r.
Otherwise, all elements of the source range are copied as sorted into [d_r.begin(), d_r.begin() + ranges::distance(r)).

3,4) Same as (1,2), but executed according to policy.

Let

sorted_r be a hypothetical sequence containing all elements of the source range, and sorted with respect to the comparator comp and projection proj1,
full_r be a hypothetical sequence of the same value type as I2 or R2, containing all elements assigned from the source range, and sorted with respect to the comparator comp and projection proj2:

If there exists an integer i where assigning the ith element of sorted_r into the destination range does not yield the ith element of full_r, the behavior is undefined.

The function-like entities described on this page are algorithm function objects (informally known as niebloids), that is:

Explicit template argument lists cannot be specified when calling any of them.
None of them are visible to argument-dependent lookup.
When any of them are found by normal unqualified lookup as the name to the left of the function-call operator, argument-dependent lookup is inhibited.

Parameters

first, last	-	the iterator-sentinel pair defining the source range
r	-	the source range
d_first, d_last	-	the iterator-sentinel pair defining the destination range
d_r	-	the destination range
comp	-	the comparator to be applied to the (projected) elements
proj1	-	the projection to be applied to the elements of source range
proj2	-	the projection to be applied to the elements of destination range
policy	-	the execution policy to use

Return value

A ranges::partial_sort_copy_result object where:

The data member in holds the past-the-end iterator of the source range.
The data member out holds an iterator past the last assigned element in the destination range, or an iterator to the beginning of the destination range if no element is assigned.

Complexity

Given

$\scriptsize N_1$ $N 1$ as ranges::distance(first, last) or ranges::distance(r),
$\scriptsize N_2$ $N 2$ as ranges::distance(d_first, d_last) or ranges::distance(d_r):

1,2) Approximately

N 1 \cdotlog(min(N 1,N 2))

applications of comp, and twice as many applications of proj1 and proj2 in total.

3,4)

𝓞(N 1 \cdotlog(min(N 1,N 2)))

applications of comp, and twice as many applications of proj1 and proj2 in total.

Exceptions

3,4) During the execution process:

If the temporary memory resources required for parallelization are not available, std::bad_alloc is thrown.
If an uncaught exception is thrown while accessing objects via an algorithm argument, the behavior is determined by the execution policy (for standard policies, std::terminate is invoked).

Possible implementation

struct partial_sort_copy_fn
{
    template<std::input_iterator I1, std::sentinel_for<I1> S1,
             std::random_access_iterator I2, std::sentinel_for<I2> S2,
             class Comp = ranges::less,
             class Proj1 = std::identity, class Proj2 = std::identity>
        requires std::indirectly_copyable<I1, I2> &&
                 std::sortable<I2, Comp, Proj2> &&
                 std::indirect_strict_weak_order<Comp, std::projected<I1, Proj1>,
                                                       std::projected<I2, Proj2>>
    constexpr ranges::partial_sort_copy_result<I1, I2>
        operator()(I1 first, S1 last, I2 d_first, S2 d_last,
                   Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        if (d_first == d_last)
            return {std::move(ranges::next(std::move(first), std::move(last))),
                    std::move(d_first)};
        
        auto out_last{d_first};
        // copy first N elements
        for (; !(first == last or out_last == d_last); ++out_last, ++first)
            *out_last = *first;
        
        // convert N copied elements into a max-heap
        ranges::make_heap(d_first, out_last, comp, proj2);
        
        // process the rest of the input range (if any), preserving the heap property
        for (; first != last; ++first)
        {
            if (std::invoke(comp, std::invoke(proj1, *first),
                                  std::invoke(proj2, *d_first)))
            {
                // pop out the biggest item and push in a newly found smaller one
                ranges::pop_heap(d_first, out_last, comp, proj2);
                *(out_last - 1) = *first;
                ranges::push_heap(d_first, out_last, comp, proj2);
            }
        }
        
        // first N elements in the output range is still
        // a heap - convert it into a sorted range
        ranges::sort_heap(d_first, out_last, comp, proj2);
        
        return {std::move(first), std::move(out_last)};
    }
    
    template<ranges::input_range R>
    constexpr auto get_end(R&& r)
    {
        return ranges::end(r);
    }
    
    template<ranges::forward_range R>
    constexpr auto get_end(R&& r)
    {
        return ranges::next(ranges::begin(r), ranges::end(r));
    }
    
    template<ranges::input_range R1, ranges::random_access_range R2,
             class Comp = ranges::less,
             class Proj1 = std::identity, class Proj2 = std::identity>
        requires std::indirectly_copyable<ranges::iterator_t<R1>,
                                          ranges::iterator_t<R2>> &&
                 std::sortable<ranges::iterator_t<R2>, Comp, Proj2> &&
                 std::indirect_strict_weak_order
                     <Comp, std::projected<ranges::iterator_t<R1>, Proj1>,
                            std::projected<ranges::iterator_t<R2>, Proj2>>
    constexpr ranges::partial_sort_copy_result<ranges::borrowed_iterator_t<R1>,
                                               ranges::borrowed_iterator_t<R2>>
        operator()(R1&& r, R2&& d_r, Comp comp = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        return (*this)(ranges::begin(r), get_end(r),
                       ranges::begin(d_r), get_end(d_r),
                       std::move(comp), std::move(proj1), std::move(proj2));
    }
};

inline constexpr partial_sort_copy_fn partial_sort_copy{};

Example

Run this code

#include <algorithm>
#include <functional>
#include <print>
#include <string_view>

struct PlayerResult
{
    std::string_view name, country;
    double score;
};

struct PodiumResult
{
    std::string_view name;
    double score;
    
    PodiumResult() = default;
    PodiumResult(PlayerResult r)
        : name(r.name), score(r.score)
    {}
};

int main()
{
    const PlayerResult results[]
    {
        {"Curt von Bardeleben", "Germany",       11.5},
        {"Emanuel Lasker",      "Germany",       15.5},
        {"Emanuel Schiffers",   "Russia",        12},
        {"Harry Pillsbury",     "United States", 16.5},
        {"Mikhail Chigorin",    "Russia",        16},
        {"Richard Teichmann",   "Germany",       11.5},
        {"Siegbert Tarrasch",   "Germany",       14},
        {"William Steinitz",    "United States", 13}
    };
    
    PodiumResult podium[3];
    std::ranges::partial_sort_copy(results, podium, std::greater(),
                                   &PlayerResult::score, &PodiumResult::score);
    
    std::print("Top 3:\n");
    for (PodiumResult result : podium)
        std::print("    {:19}: {}\n", result.name, result.score);
}

Output:

Top 3:
    Harry Pillsbury    : 16.5
    Mikhail Chigorin   : 16
    Emanuel Lasker     : 15.5

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

partial_sort_copy	copies and partially sorts a range of elements (function template) [edit]
ranges::partial_sort (C++20)	sorts the first N elements of a range (algorithm function object)[edit]
ranges::sort (C++20)	sorts a range of elements (algorithm function object)[edit]
ranges::stable_sort (C++20)	sorts a range of elements while preserving relative order between equivalent elements (algorithm function object)[edit]
ranges::sort_heap (C++20)	turns a max heap into a sorted range of elements (algorithm function object)[edit]
ranges::make_heap (C++20)	creates a max heap out of a range of elements (algorithm function object)[edit]
ranges::push_heap (C++20)	adds an element to a max heap (algorithm function object)[edit]
ranges::pop_heap (C++20)	removes the largest element from a max heap (algorithm function object)[edit]

cppreference.com

Search

Namespaces

Variants

Views

Actions

std::ranges::partial_sort_copy, std::ranges::partial_sort_copy_result

Contents

Parameters

Return value

Complexity

Exceptions

Possible implementation

Example

See also

Navigation

Tools