Defined in header
template<classRandomIt>voidpartial_sort(RandomItfirst,RandomItmiddle,RandomItlast); (1)(constexpr since C++20)template<classRandomIt,classCompare>voidpartial_sort(RandomItfirst,RandomItmiddle,RandomItlast,Comparecomp); (2)(constexpr since C++20)template<classExecutionPolicy,classRandomIt>voidpartial_sort(ExecutionPolicy&&policy,RandomItfirst,RandomItmiddle,RandomItlast); (3) (since C++17)template<classExecutionPolicy,classRandomIt,classCompare>voidpartial_sort(ExecutionPolicy&&policy,RandomItfirst,RandomItmiddle,RandomItlast,Comparecomp); (4) (since C++17)Places the first middle-first elements from the target range [first, last) as sorted into the range [first, middle). The rest of the elements are placed in the range [middle, last) in an unspecified order.
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 any of the following conditions is satisfied, the behavior is undefined:
[first, middle) or [middle, last) is not a
.
Parameters
first, last - the pair of iterators defining the target
middle - the end of the range of sorted elements 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 -RandomIt must meet the requirements of
. -Compare must meet the requirements of
. Complexity
Given
M as middle-first,
N as last-first:
1) Approximately N·log(M) comparisons using operator<(until C++20)std::less{}(since C++20).
2) Approximately N·log(M) applications of the comparator comp.
3)𝓞(N·log(M)) comparisons using operator<(until C++20)std::less{}(since C++20).
4)𝓞(N·log(M)) 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
.
template<typenameRandomIt>constexpr//< since C++20voidpartial_sort(RandomItfirst,RandomItmiddle,RandomItlast){typedeftypenamestd::iterator_traits<RandomIt>::value_typeVT;std::partial_sort(first,middle,last,std::less<VT>());}
namespaceimpl{template<typenameRandomIt,typenameCompare>constexpr//< since C++20voidsift_down(RandomItfirst,RandomItlast,constCompare&comp){// sift down element at “first”constautolength=static_cast<std::size_t>(last-first);std::size_tcurrent=0;std::size_tnext=2;while(next<length){if(comp(*(first+next),*(first+(next-1))))--next;if(!comp(*(first+current),*(first+next)))return;std::iter_swap(first+current,first+next);current=next;next=2*current+2;}--next;if(next<length&&comp(*(first+current),*(first+next)))std::iter_swap(first+current,first+next);}template<typenameRandomIt,typenameCompare>constexpr//< since C++20voidheap_select(RandomItfirst,RandomItmiddle,RandomItlast,constCompare&comp){std::make_heap(first,middle,comp);for(autoi=middle;i!=last;++i){if(comp(*i,*first)){std::iter_swap(first,i);sift_down(first,middle,comp);}}}}// namespace impltemplate<typenameRandomIt,typenameCompare>constexpr//< since C++20voidpartial_sort(RandomItfirst,RandomItmiddle,RandomItlast,Comparecomp){impl::heap_select(first,middle,last,comp);std::sort_heap(first,middle,comp);}Notes
std::partial_sort algorithms are intended to be used for small constant numbers of [first, middle) selected elements.
The algorithm used is typically heap select to select the smallest elements, and heap sort to sort the selected elements in the heap in ascending order.
To select elements, a heap is used (see
). For example, for operator< as comparison function, max-heap is used to select middle−first smallest elements.
is used after selection to sort [first, middle) selected elements (see
).
Example
Run this code
#include<algorithm>#include<array>#include<functional>#include<iostream>voidprint(constauto&s,intmiddle){for(inta:s)std::cout<<a<<' ';std::cout<<'\n';if(middle>0){while(middle-->0)std::cout<<"--";std::cout<<'^';}elseif(middle<0){for(autoi=s.size()+middle;--i;std::cout<<" "){}for(std::cout<<'^';middle++<0;std::cout<<"--"){}}std::cout<<'\n';};intmain(){std::array<int,10>s{5,7,4,2,8,6,1,9,0,3};print(s,0);std::partial_sort(s.begin(),s.begin()+3,s.end());print(s,3);std::partial_sort(s.rbegin(),s.rbegin()+4,s.rend());print(s,-4);std::partial_sort(s.rbegin(),s.rbegin()+5,s.rend(),std::greater{});print(s,-5);}Possible output:
5 7 4 2 8 6 1 9 0 3 0 1 2 7 8 6 5 9 4 3 ------^ 4 5 6 7 8 9 3 2 1 0 ^-------- 4 3 2 1 0 5 6 7 8 9 ^---------- 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, middle) and [middle, last)
were not required to be valid ranges the behavior is undefined
if any of them is invalid See also
(C++20)
sorts the first N elements of a range
(algorithm function object)
finds the Nth element if the range were sorted
(function template & algorithm function object)
(C++20)
copies and partially 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)
sorts a range of elements
(function template & algorithm function object)
(C++20)