From cppreference.com
Defined in header
template<classInputIt,classRandomIt>RandomItpartial_sort_copy(InputItfirst,InputItlast,RandomItd_first,RandomItd_last); (1)(constexpr since C++20)template<classInputIt,classRandomIt,classCompare>RandomItpartial_sort_copy(InputItfirst,InputItlast,RandomItd_first,RandomItd_last,Comparecomp); (2)(constexpr since C++20)template<classExecutionPolicy,classForwardIt,classRandomIt>RandomItpartial_sort_copy(ExecutionPolicy&&policy,ForwardItfirst,ForwardItlast,RandomItd_first,RandomItd_last); (3) (since C++17)template<classExecutionPolicy,classForwardIt,classRandomIt,classCompare>RandomItpartial_sort_copy(ExecutionPolicy&&policy,ForwardItfirst,ForwardItlast,RandomItd_first,RandomItd_last,Comparecomp); (4) (since C++17)Copies elements from the source range [first, last) as sorted into the destination range [d_first, d_last):
If std::distance(first,last) is greater than d_last-d_first, the first d_last-d_first elements of the source range is copied as sorted into [d_first, d_last).
Otherwise, all elements of the source range is copied as sorted into [d_first, d_first+std::distance(first,last)).
1) Elements are
with respect to operator<(until C++20)std::less{}(since C++20).
2) Elements are sorted with respect to comp.
3,4) Same as (1,2), but executed according to policy.
These overloads participate in overload resolution only if the value of the following expression is true:
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>
(until C++20)std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>
(since C++20)If *first is not
to d_first, the program is ill-formed.
If any of the following conditions is satisfied, the behavior is undefined:
Parameters
first, last - the pair of iterators defining the source
d_first, d_last - the pair of iterators defining the destination
comp - comparison function object (i.e. an object that satisfies the requirements of
) which returns true if the first argument is less than (i.e. is ordered before) the second. The signature of the comparison function should be equivalent to the following:
boolcmp(constType1&a,constType2&b);
While the signature does not need to have const&, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) Type1 and Type2 regardless of
(thus, Type1& is not allowed, nor is Type1 unless for Type1 a move is equivalent to a copy(since C++11)).
The types Type1 and Type2 must be such that an object of type RandomIt can be dereferenced and then implicitly converted to both of them.
policy - the
to use Type requirements -InputIt must meet the requirements of
. -ForwardIt must meet the requirements of
. -RandomIt must meet the requirements of
. -Compare must meet the requirements of
. Return value
An iterator past the last assigned element in the destination range, or d_first if no element is assigned.
Complexity
Given
N1 as std::distance(first,last),
N2 as d_last-d_first:
1) Approximately N1·log(min(N1,N2)) comparisons using operator<(until C++20)std::less{}(since C++20).
2) Approximately N1·log(min(N1,N2)) applications of the comparator comp.
3)𝓞(N1·log(min(N1,N2))) comparisons using operator<(until C++20)std::less{}(since C++20).
4)𝓞(N1·log(min(N1,N2))) applications of the comparator comp.
Exceptions
3,4) During the execution process:
If the temporary memory resources required for parallelization are not available,
is thrown.
If an uncaught exception is thrown while accessing objects via an algorithm argument, the behavior is determined by the execution policy (for
,
is invoked).
Possible implementation
See also the implementations in
and
.
Example
Run this code
#include<algorithm>#include<cstdio>#include<functional>#include<print>#include<string_view>structResult{std::string_viewname;doublescore;friendstd::partial_orderingoperator<=>(Resultlhs,Resultrhs){returnlhs.score<=>rhs.score;}};intmain(){constResultresults[]{{"Curt von Bardeleben",11.5},{"Emanuel Lasker",15.5},{"Emanuel Schiffers",12},{"Harry Pillsbury",16.5},{"Mikhail Chigorin",16},{"Richard Teichmann",11.5},{"Siegbert Tarrasch",14},{"William Steinitz",13}};Resultpodium[3];std::partial_sort_copy(std::begin(results),std::end(results),std::begin(podium),std::end(podium),std::greater());std::puts("Top 3:");for(Resultresult:podium)std::print(" {}: {}\n",result.name,result.score);}Output:
Top 3: Harry Pillsbury: 16.5 Mikhail Chigorin: 16 Emanuel Lasker: 15.5 Defect reports
The following behavior-changing defect reports were applied retroactively to previously published C++ standards.
DR Applied to Behavior as published Correct behavior
C++98 *first was not required to be writable to d_firstthe program is ill-formed if not writable See also
(C++20)
copies and partially sorts a range of elements
(algorithm function object)
sorts the first N elements of a range
(function template & algorithm function object)
(C++20)
sorts a range of elements
(function template & algorithm function object)
(C++20)
sorts a range of elements while preserving relative order between equivalent elements
(function template & algorithm function object)
(C++20)