| Constrained algorithms and algorithms on ranges(C++20) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Constrained algorithms, e.g.ranges::copy,ranges::sort, ... | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Execution policies(C++17) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Numeric operations | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Operations on uninitialized memory | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Defined in header <algorithm> | ||
template<class ForwardIt,class UnaryPred> ForwardIt partition_point( ForwardIt first, ForwardIt last, UnaryPred p); | (since C++11) (constexpr since C++20) | |
Examines the partitioned range[first, last) and locates the end of the first partition, that is, the first element that does not satisfyp orlast if all elements satisfyp.
If the elementselem of[first, last) are notpartitioned with respect to the expressionbool(p(elem)), the behavior is undefined.
Contents |
| first, last | - | the pair of iterators defining the partitionedrange of elements to examine |
| p | - | unary predicate which returns true for the elements found in the beginning of the range. The expressionp(v) must be convertible tobool for every argument |
| Type requirements | ||
-ForwardIt must meet the requirements ofLegacyForwardIterator. | ||
-UnaryPred must meet the requirements ofPredicate. | ||
The iterator past the end of the first partition within[first, last) orlast if all elements satisfyp.
Given\(\scriptsize N\)N asstd::distance(first, last), performs\(\scriptsize O(log(N))\)O(log(N)) applications of the predicatep.
This algorithm is a more general form ofstd::lower_bound, which can be expressed in terms ofstd::partition_point with the predicate[&](constauto& e){return e< value;});.
template<class ForwardIt,class UnaryPred>constexpr//< since C++20ForwardIt partition_point(ForwardIt first, ForwardIt last, UnaryPred p){for(auto length=std::distance(first, last);0< length;){auto half= length/2;auto middle=std::next(first, half);if(p(*middle)){ first=std::next(middle); length-=(half+1);}else length= half;} return first;} |
#include <algorithm>#include <array>#include <iostream>#include <iterator> auto print_seq=[](auto rem,auto first,auto last){for(std::cout<< rem; first!= last;std::cout<<*first++<<' '){}std::cout<<'\n';}; int main(){std::array v{1,2,3,4,5,6,7,8,9}; auto is_even=[](int i){return i%2==0;}; std::partition(v.begin(), v.end(), is_even); print_seq("After partitioning, v: ", v.cbegin(), v.cend()); constauto pp= std::partition_point(v.cbegin(), v.cend(), is_even);constauto i=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 9Partition point is at 4; v[4] = 5First partition (all even elements): 8 2 6 4Second partition (all odd elements): 5 3 7 1 9
(C++11) | finds the first element satisfying specific criteria (function template)[edit] |
(C++11) | checks whether a range is sorted into ascending order (function template)[edit] |
| returns an iterator to the first elementnot less than the given value (function template)[edit] | |
(C++20) | locates the partition point of a partitioned range (algorithm function object)[edit] |
