| 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( ForwardIt first, ForwardIt last, UnaryPred p); | (1) | (constexpr since C++20) |
template<class ExecutionPolicy,class ForwardIt,class UnaryPred> ForwardIt partition( ExecutionPolicy&& policy, | (2) | (since C++17) |
[first, last) in such a way that all elements for which the predicatep returnstrue precede all elements for which predicatep returnsfalse. Relative order of the elements is not preserved.std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> istrue. | (until C++20) |
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> istrue. | (since C++20) |
Ifthe type of*first is notSwappable(until C++11)ForwardIt is notValueSwappable(since C++11), the behavior is undefined.
Contents |
| first, last | - | the pair of iterators defining therange of elements to reorder |
| policy | - | theexecution policy to use |
| p | - | unary predicate which returns true if the element should be ordered before other elements. The expressionp(v) must be convertible tobool for every argument |
| Type requirements | ||
-ForwardIt must meet the requirements ofLegacyForwardIterator. | ||
-UnaryPred must meet the requirements ofPredicate. | ||
Iterator to the first element of the second group.
Given\(\scriptsize N\)N asstd::distance(first, last):
ForwardIt meets the requirements ofLegacyBidirectionalIterator, and at most\(\scriptsize N\)N swaps otherwise.The overload with a template parameter namedExecutionPolicy reports errors as follows:
ExecutionPolicy is one of thestandard policies,std::terminate is called. For any otherExecutionPolicy, the behavior is implementation-defined.Implements overload(1) preserving C++11 compatibility.
template<class ForwardIt,class UnaryPred>ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPred p){ first=std::find_if_not(first, last, p);if(first== last)return first; for(auto i=std::next(first); i!= last;++i)if(p(*i)){std::iter_swap(i, first);++first;} return first;} |
#include <algorithm>#include <forward_list>#include <iostream>#include <iterator>#include <vector> template<class ForwardIt>void quicksort(ForwardIt first, ForwardIt last){if(first== last)return; auto pivot=*std::next(first,std::distance(first, last)/2);auto middle1= std::partition(first, last,[pivot](constauto& em){return em< pivot;});auto middle2= std::partition(middle1, last,[pivot](constauto& em){return!(pivot< em);}); quicksort(first, middle1); quicksort(middle2, last);} int main(){std::vector<int> v{0,1,2,3,4,5,6,7,8,9};std::cout<<"Original vector: ";for(int elem: v)std::cout<< elem<<' '; auto it= std::partition(v.begin(), v.end(),[](int i){return i%2==0;}); std::cout<<"\nPartitioned vector: ";std::copy(std::begin(v), it,std::ostream_iterator<int>(std::cout," "));std::cout<<"* ";std::copy(it,std::end(v),std::ostream_iterator<int>(std::cout," ")); std::forward_list<int> fl{1,30,-4,3,5,-4,1,6,-8,2,-5,64,1,92};std::cout<<"\nUnsorted list: ";for(int n: fl)std::cout<< n<<' '; quicksort(std::begin(fl),std::end(fl));std::cout<<"\nSorted using quicksort: ";for(int fi: fl)std::cout<< fi<<' ';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: -8 -5 -4 -4 1 1 1 2 3 5 6 30 64 92
The following behavior-changing defect reports were applied retroactively to previously published C++ standards.
| DR | Applied to | Behavior as published | Correct behavior |
|---|---|---|---|
| LWG 498 | C++98 | std::partition requiredfirst andlast to beLegacyBidirectionalIterator | only required to be LegacyForwardIterator |
| LWG 2150 | C++98 | std::partition was only required to place one elementsatisfyingp before one element not satisfyingp | corrected the requirement |
(C++11) | determines if the range is partitioned by the given predicate (function template)[edit] |
| divides elements into two groups while preserving their relative order (function template)[edit] | |
(C++20) | divides a range of elements into two groups (algorithm function object)[edit] |
