From cppreference.com
Defined in header
Call signature
template<std::random_access_iteratorI,std::sentinel_for<I>S,classComp=ranges::less,classProj=std::identity>requiresstd::sortable<I,Comp,Proj>constexprIpartial_sort(Ifirst,Imiddle,Slast,Compcomp={},Projproj={}); (1) (since C++20)template<ranges::random_access_rangeR,classComp=ranges::less,classProj=std::identity>requiresstd::sortable<ranges::iterator_t<R>,Comp,Proj>constexprranges::borrowed_iterator_t<R>partial_sort(R&&r,ranges::iterator_t<R>middle,Compcomp={},Projproj={}); (2) (since C++20)template</*execution-policy*/Ep,std::random_access_iteratorI,std::sized_sentinel_for<I>S,classComp=ranges::less,classProj=std::identity>requiresstd::sortable<I,Comp,Proj>Ipartial_sort(Ep&&policy,Ifirst,Imiddle,Slast,Compcomp={},Projproj={}); (3) (since C++26)template</*execution-policy*/Ep,/*sized-random-access-range*/R,classComp=ranges::less,classProj=std::identity>requiresstd::sortable<ranges::iterator_t<R>,Comp,Proj>ranges::borrowed_iterator_t<R>partial_sort(Ep&&policy,R&&r,ranges::iterator_t<R>middle,Compcomp={},Projproj={}); (4) (since C++26)For the definition of /*execution-policy*/, see
; for the definition of /*sized-random-access-range*/, see
.
1) Places the first middle-first elements from the target range [first, last) as
with respect to the comparator comp and projection proj into the range [first, middle). The rest of the elements are placed in the range [middle, last) in an unspecified order.
2) Same as (1), but uses ranges::begin(r) as first and ranges::end(r) as last.
3) Same as (1), but executed according to policy.
4) Same as (3), but uses ranges::begin(r) as first and ranges::begin(r)+ranges::distance(r) as last.
The function-like entities described on this page are
(informally known as niebloids), that is:
Explicit template argument lists cannot be specified when calling any of them.
None of them are visible to
.
When any of them are found by
as the name to the left of the function-call operator,
is inhibited.
Parameters
first, last - the iterator-sentinel pair defining the target
r - the target range middle - the end of the range of sorted elements comp - the comparator to be applied to the (projected) elements proj - the projection to be applied to the elements policy - the
to use Return value
The past-the-end iterator of the target range.
Complexity
Given
M as ranges::distance(first,middle),
N as ranges::distance(first,last):
1,2) Approximately N·log(M) applications of comp, and twice as many applications of proj.
3,4)𝓞(N·log(M)) applications of comp, and twice as many applications of proj.
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
structpartial_sort_fn{template<std::random_access_iteratorI,std::sentinel_for<I>S,classComp=ranges::less,classProj=std::identity>requiresstd::sortable<I,Comp,Proj>constexprIoperator()(Ifirst,Imiddle,Slast,Compcomp={},Projproj={})const{if(first==middle)returnranges::next(first,last);ranges::make_heap(first,middle,comp,proj);autoit{middle};for(;it!=last;++it){if(std::invoke(comp,std::invoke(proj,*it),std::invoke(proj,*first))){ranges::pop_heap(first,middle,comp,proj);ranges::iter_swap(middle-1,it);ranges::push_heap(first,middle,comp,proj);}}ranges::sort_heap(first,middle,comp,proj);returnit;}template<ranges::random_access_rangeR,classComp=ranges::less,classProj=std::identity>requiresstd::sortable<ranges::iterator_t<R>,Comp,Proj>constexprranges::borrowed_iterator_t<R>operator()(R&&r,ranges::iterator_t<R>middle,Compcomp={},Projproj={})const{return(*this)(ranges::begin(r),std::move(middle),ranges::end(r),std::move(comp),std::move(proj));}};inlineconstexprpartial_sort_fnpartial_sort{};Example
Run this code
#include<algorithm>#include<functional>#include<iostream>#include<string>#include<vector>voidprint(constauto&v){for(constchare:v)std::cout<<e<<' ';std::cout<<'\n';}voidunderscore(intn){while(n-->0)std::cout<<"^ ";std::cout<<'\n';}intmain(){static_assert('A'<'a');std::vector<char>v{'x','P','y','C','z','w','P','o'};print(v);constintm{3};std::ranges::partial_sort(v,v.begin()+m);print(v),underscore(m);static_assert('1'<'a');std::strings{"3a1b41c5"};print(s);std::ranges::partial_sort(s.begin(),s.begin()+m,s.end(),std::greater{});print(s),underscore(m);}Output:
x P y C z w P o C P P y z x w o ^ ^ ^ 3 a 1 b 4 1 c 5 c b a 1 3 1 4 5 ^ ^ ^ See also
sorts the first N elements of a range
(function template)
(C++20)
copies and partially sorts a range of elements
(algorithm function object)
(C++20)
sorts a range of elements
(algorithm function object)
(C++20)
sorts a range of elements while preserving relative order between equivalent elements
(algorithm function object)
(C++20)
finds the Nth element if the range were sorted
(algorithm function object)
(C++20)
creates a max heap out of a range of elements
(algorithm function object)
(C++20)
removes the largest element from a max heap
(algorithm function object)
(C++20)
adds an element to a max heap
(algorithm function object)
(C++20)
turns a max heap into a sorted range of elements
(algorithm function object)