From cppreference.com
template<classForwardIt,classUnaryPred>ForwardItpartition_point(ForwardItfirst,ForwardItlast,UnaryPredp);(since C++11)
(constexpr since C++20)Returns the iterator iter indicating the partition point of the source range [first, last): all elements before iter satisfy p, while all elements starting from iter do not.
If the elements e of the source range are not
with respect to the expression bool(p(elem)), the behavior is undefined.
Parameters
first, last - the pair of iterators defining the source
p - unary predicate which returns true for the elements before the partition point. The expression p(v) must be convertible to bool for every argument v of type (possibly const) VT, where VT is the value type of ForwardIt, regardless of
, and must not modify v. Thus, a parameter type of VT&is not allowed, nor is VT unless for VT a move is equivalent to a copy(since C++11).
Type requirements -ForwardIt must meet the requirements of
. -UnaryPred must meet the requirements of
. Return value
As described above.
Complexity
Given N as std::distance(first,last), performs 𝓞(log(N)) applications of the predicate p.
Notes
This algorithm is a more general form of
, which can be expressed in terms of std::partition_point with the predicate [&](constauto&e){returne<value;});.
Possible implementation
template<classForwardIt,classUnaryPred>constexpr//< since C++20ForwardItpartition_point(ForwardItfirst,ForwardItlast,UnaryPredp){for(autolength=std::distance(first,last);0<length;){autohalf=length/2;automiddle=std::next(first,half);if(p(*middle)){first=std::next(middle);length-=(half+1);}elselength=half;}returnfirst;}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::partition(v.begin(),v.end(),is_even);print_seq("After partitioning, v: ",v.cbegin(),v.cend());constautopp=std::partition_point(v.cbegin(),v.cend(),is_even);constautoi=std::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: 8 2 6 4 5 3 7 1 9 Partition point is at 4; v[4] = 5 First partition (all even elements): 8 2 6 4 Second partition (all odd elements): 5 3 7 1 9 See also
(C++20)
locates the partition point of a partitioned range
(algorithm function object)
(C++11)
finds the first element satisfying specific criteria
(function template & algorithm function object)
ranges::findranges::find_ifranges::find_if_not
(C++20)(C++20)(C++20)
(C++11)
checks whether a range is sorted
(function template & algorithm function object)
(C++20)
finds the first element not less than the given value using binary search
(function template & algorithm function object)
(C++20)