25 Algorithms library [algorithms]

25.8 Sorting and related operations [alg.sorting]

25.8.1 Sorting [alg.sort]

25.8.1.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 .
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 28) and Cpp17MoveAssignable (Table 30) requirements.
Preconditions: 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
: 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:
  • result_­first + N for the overloads in namespace std.
  • {last, result_­first + N} for the overloads in namespace ranges.
Complexity: Approximately (last - first) * log N comparisons, and twice as many projections.