24 Algorithms library [algorithms]

24.7 Sorting and related operations [alg.sorting]

24.7.1 Sorting [alg.sort]

24.7.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); namespace ranges { template<InputIterator I1, Sentinel<I1> S1, RandomAccessIterator I2, Sentinel<I2> S2, class Comp = ranges::less<>, class Proj1 = identity, class Proj2 = identity> requires IndirectlyCopyable<I1, I2> && Sortable<I2, Comp, Proj2> && IndirectStrictWeakOrder<Comp, projected<I1, Proj1>, projected<I2, Proj2>> constexpr I2 partial_sort_copy(I1 first, S1 last, I2 result_first, S2 result_last, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<InputRange R1, RandomAccessRange R2, class Comp = ranges::less<>, class Proj1 = identity, class Proj2 = identity> requires IndirectlyCopyable<iterator_t<R1>, iterator_t<R2>> && Sortable<iterator_t<R2>, Comp, Proj2> && IndirectStrictWeakOrder<Comp, projected<iterator_t<R1>, Proj1>, projected<iterator_t<R2>, Proj2>> constexpr safe_iterator_t<R2> 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.
Requires: For the overloads in namespace std, RandomAccessIterator shall meet the Cpp17ValueSwappable requirements ([swappable.requirements]), the type of *result_­first shall meet the Cpp17MoveConstructible (Table 26) and Cpp17MoveAssignable (Table 28) requirements, and the expression *first shall be writable ([iterator.requirements.general]) to result_­first.
Expects: 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.
Complexity: Approximately (last - first) * log N comparisons, and twice as many projections.