27 Algorithms library [algorithms]

27.8 Sorting and related operations [alg.sorting]

27.8.2 Sorting [alg.sort]

27.8.2.4 partial_sort_copy [partial.sort.copy]

template<class InputIterator, class RandomAccessIterator>
  constexpr RandomAccessIterator
    partial_sort_copy(InputIterator first, InputIterator last,
                      RandomAccessIterator result_first,
                      RandomAccessIterator result_last);
template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator>
  RandomAccessIterator
    partial_sort_copy(ExecutionPolicy&& exec,
                      ForwardIterator first, ForwardIterator last,
                      RandomAccessIterator result_first,
                      RandomAccessIterator result_last);

template<class InputIterator, class RandomAccessIterator,
         class Compare>
  constexpr RandomAccessIterator
    partial_sort_copy(InputIterator first, InputIterator last,
                      RandomAccessIterator result_first,
                      RandomAccessIterator result_last,
                      Compare comp);
template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator,
         class Compare>
  RandomAccessIterator
    partial_sort_copy(ExecutionPolicy&& exec,
                      ForwardIterator first, ForwardIterator last,
                      RandomAccessIterator result_first,
                      RandomAccessIterator result_last,
                      Compare comp);

template<input_iterator I1, sentinel_for<I1> S1, random_access_iterator I2, sentinel_for<I2> S2,
         class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
  requires indirectly_copyable<I1, I2> && sortable<I2, Comp, Proj2> &&
           indirect_strict_weak_order<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
  constexpr ranges::partial_sort_copy_result<I1, I2>
    ranges::partial_sort_copy(I1 first, S1 last, I2 result_first, S2 result_last,
                              Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, random_access_range R2, class Comp = ranges::less,
         class Proj1 = identity, class Proj2 = identity>
  requires indirectly_copyable<iterator_t<R1>, iterator_t<R2>> &&
           sortable<iterator_t<R2>, Comp, Proj2> &&
           indirect_strict_weak_order<Comp, projected<iterator_t<R1>, Proj1>,
                                      projected<iterator_t<R2>, Proj2>>
  constexpr ranges::partial_sort_copy_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
    ranges::partial_sort_copy(R1&& r, R2&& result_r, Comp comp = {},
                              Proj1 proj1 = {}, Proj2 proj2 = {});

Let N be min(last - first, result_last - result_first).

Let comp be less{}, and proj1 and proj2 be identity{} for the overloads with no parameters by those names.

Mandates: For the overloads in namespace std, the expression *first is writable ([iterator.requirements.general]) to result_first.

Preconditions: For the overloads in namespace std, RandomAccessIterator meets the Cpp17ValueSwappable requirements ([swappable.requirements]), the type of *result_first meets the Cpp17MoveConstructible (Table 31) and Cpp17MoveAssignable (Table 33) requirements.

For iterators a1 and b1 in [first, last), and iterators x2 and y2 in [result_first, result_last), after evaluating the assignment *y2 = *b1, let E be the value of bool(invoke(comp, invoke(proj1, *a1), invoke(proj2, *y2))).

Then, after evaluating the assignment *x2 = *a1, E is equal to bool(invoke(comp, invoke(proj2, *x2), invoke(proj2, *y2))).

[Note 1:

Writing a value from the input range into the output range does not affect how it is ordered by comp and proj1 or proj2.

— end note]

Effects: Places the first N elements as sorted with respect to comp and proj2 into the range [result_first, result_first + N).

Returns:

(6.1)
result_first + N for the overloads in namespace std.
(6.2)
{last, result_first + N} for the overloads in namespace ranges.

Complexity: Approximately (last - first) * log N comparisons, and twice as many projections.