From cppreference.com
Defined in header
Call signature
template<std::forward_iteratorI,std::sentinel_for<I>S,classProj=std::identity,std::indirect_unary_predicate<std::projected<I,Proj>>Pred>constexprIpartition_point(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>constexprranges::borrowed_iterator_t<R>partition_point(R&&r,Predpred,Projproj={}); (2) (since C++20)Returns the iterator iter indicating the partition point of the source range [first, last) or r: all elements (projected by proj) before iter satisfy pred, while all elements starting from iter do not.
If the elements e of the source range are not
with respect to the expression bool(std::invoke(pred,std::invoke(proj,e))), the behavior is undefined.
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 source
r - the source range pred - the predicate to be applied to the (projected) elements proj - the projection to be applied to the elements Return value
As described above.
Complexity
Given N as ranges::distance(first,last) or ranges::distance(r):
1,2)𝓞(log(N)) applications of pred and proj.
Notes
This algorithm is a more general form of ranges::lower_bound, which can be expressed in terms of ranges::partition_point with the predicate [&](autoconst&e){returnstd::invoke(pred,e,value);});.
Example
Run this code
#include<algorithm>#include<array>#include<iostream>#include<iterator>autoprint_seq=[](autorem,autofirst,autolast){for(std::cout<<rem;first!=last;std::cout<<*first++<<' '){}std::cout<<'\n';};intmain(){std::arrayv{1,2,3,4,5,6,7,8,9};autois_even=[](inti){returni%2==0;};std::ranges::partition(v,is_even);print_seq("After partitioning, v: ",v.cbegin(),v.cend());constautopp=std::ranges::partition_point(v,is_even);constautoi=std::ranges::distance(v.cbegin(),pp);std::cout<<"Partition point is at "<<i<<"; v["<<i<<"] = "<<*pp<<'\n';print_seq("First partition (all even elements): ",v.cbegin(),pp);print_seq("Second partition (all odd elements): ",pp,v.cend());}Possible output:
After partitioning, v: 2 4 6 8 5 3 7 1 9 Partition point is at 4; v[4] = 5 First partition (all even elements): 2 4 6 8 Second partition (all odd elements): 5 3 7 1 9 See also