std::partition
From Cppreference
Defined in header <algorithm>
|
||
template< class BidirectionalIterator, class UnaryPredicate >
BidirectionalIterator partition( BidirectionalIterator first, BidirectionalIterator last, |
(pre-C++11 version) (C++11 version) |
|
Reorders the elements in the range [first, last) in such a way that all elements for which the predicate p returns true precede the elements for which predicate p returns false. Relative order of the elements is not preserved.
Contents |
[edit] Parameters
first, last | - | the range of elements to reorder | |||||||||
p | - | unary predicate which returns true if the element should be ordered before other elements. The signature of the predicate function should be equivalent to the following:
The signature does not need to have const &, but the function must not modify the objects passed to it. |
[edit] Return value
iterator to the first element of the second group
[edit] Complexity
Exactly last-first applications of the predicate and at most (last-first)/2 swaps if ForwardIterator meets the requirements of BidirectionalIterator, otherwise at most last-first swaps.
[edit] Equivalent function
template<class BidirectionalIterator, class UnaryPredicate> BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate p) { while (1) { while ((first != last) && p(*first)) { ++first; } if (first == last--) break; while ((first != last) && !p(*last)) { --last; } if (first == last) break; std::swap (*first++,*last); } return first; } |
[edit] Example
This section is incomplete |
[edit] See also
|
determines if the range is partitioned by the given predicate (function template) |
||
|
divides elements into two groups while preserving their relative order (function template) |