Defined in header
Call signature
template<std::permutableI,std::sentinel_for<I>S,classProj=std::identity,std::indirect_unary_predicate<std::projected<I,Proj>>Pred>constexprranges::subrange<I>partition(Ifirst,Slast,Predpred,Projproj={}); (1) (since C++20)template<ranges::forward_rangeR,classProj=std::identity,std::indirect_unary_predicate<std::projected<ranges::iterator_t<R>,Proj>>Pred>requiresstd::permutable<ranges::iterator_t<R>>constexprranges::borrowed_subrange_t<R>partition(R&&r,Predpred,Projproj={}); (2) (since C++20)template</*execution-policy*/Ep,std::random_access_iteratorI,std::sized_sentinel_for<I>S,classProj=std::identity,std::indirect_unary_predicate<std::projected<I,Proj>>Pred>requiresstd::permutable<I>ranges::subrange<I>partition(Ep&&policy,Ifirst,Slast,Predpred,Projproj={}); (3) (since C++26)template</*execution-policy*/Ep,/*sized-random-access-range*/R,classProj=std::identity,std::indirect_unary_predicate<std::projected<ranges::iterator_t<R>,Proj>>Pred>requiresstd::permutable<ranges::iterator_t<R>>ranges::borrowed_subrange_t<R>partition(Ep&&policy,R&&r,Predpred,Projproj={}); (4) (since C++26)For the definition of /*execution-policy*/, see
; for the definition of /*sized-random-access-range*/, see
.
1,2)
the elements e in the target range [first, last) or r with respect to the expression bool(std::invoke(pred,std::invoke(proj,e))): all elements (projected by proj) satisfy pred appear before all elements that do not.
3,4) Same as (1,2), but executed according to policy.
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 pred - the predicate to be applied to the (projected) elements proj - the projection to be applied to the elements policy - the
to use Return value
A subrange from the partition point to the end of the target range. All elements outside the subrange satisfy p, while all elements in the subrange do not.
Complexity
Given N as ranges::distance(first,last) or ranges::distance(r):
1,2) At most N swaps (or only at most N2 swaps if I or ranges::iterator_t<R> models
), and exactly N applications of pred and proj.
3,4)𝓞(N·log(N)) swaps, and 𝓞(N) applications of pred and 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
structpartition_fn{template<std::permutableI,std::sentinel_for<I>S,classProj=std::identity,std::indirect_unary_predicate<std::projected<I,Proj>>Pred>constexprranges::subrange<I>operator()(Ifirst,Slast,Predpred,Projproj={})const{first=ranges::find_if_not(first,last,std::ref(pred),std::ref(proj));if(first==last)return{first,first};for(autoi=ranges::next(first);i!=last;++i){if(std::invoke(pred,std::invoke(proj,*i))){ranges::iter_swap(i,first);++first;}}return{std::move(first),std::move(last)};}template<ranges::forward_rangeR,classProj=std::identity,std::indirect_unary_predicate<std::projected<ranges::iterator_t<R>,Proj>>Pred>requiresstd::permutable<ranges::iterator_t<R>>constexprranges::borrowed_subrange_t<R>operator()(R&&r,Predpred,Projproj={})const{return(*this)(ranges::begin(r),ranges::next(ranges::begin(r),ranges::end(r)),std::ref(pred),std::ref(proj));}};inlineconstexprpartition_fnpartition;Example
Run this code
#include<algorithm>#include<forward_list>#include<functional>#include<iostream>#include<iterator>#include<ranges>#include<vector>namespaceranges=std::ranges;template<classI,std::sentinel_for<I>S,classCmp=ranges::less>requiresstd::sortable<I,Cmp>voidquicksort(Ifirst,Slast,Cmpcmp=Cmp{}){usingreference=std::iter_reference_t<I>;if(first==last)return;autosize=ranges::distance(first,last);autopivot=ranges::next(first,size-1);ranges::iter_swap(pivot,ranges::next(first,size/2));autotail=ranges::partition(first,pivot,[=](referenceem){returnstd::invoke(cmp,em,*pivot);// em < pivot});ranges::iter_swap(pivot,tail.begin());quicksort(first,tail.begin(),std::ref(cmp));quicksort(ranges::next(tail.begin()),last,std::ref(cmp));}intmain(){std::ostream_iterator<int>cout{std::cout," "};std::vector<int>v{0,1,2,3,4,5,6,7,8,9};std::cout<<"Original vector: ";ranges::copy(v,cout);autotail=ranges::partition(v,[](inti){returni%2==0;});std::cout<<"\nPartitioned vector: ";ranges::copy(ranges::begin(v),ranges::begin(tail),cout);std::cout<<"│ ";ranges::copy(tail,cout);std::forward_list<int>fl{1,30,-4,3,5,-4,1,6,-8,2,-5,64,1,92};std::cout<<"\nUnsorted list: ";ranges::copy(fl,cout);quicksort(ranges::begin(fl),ranges::end(fl),ranges::greater{});std::cout<<"\nSorted using quicksort: ";ranges::copy(fl,cout);std::cout<<'\n';}Possible output:
Original vector: 0 1 2 3 4 5 6 7 8 9 Partitioned vector: 0 8 2 6 4 │ 5 3 7 1 9 Unsorted list: 1 30 -4 3 5 -4 1 6 -8 2 -5 64 1 92 Sorted using quicksort: 92 64 30 6 5 3 2 1 1 1 -4 -4 -5 -8 See also