Function definition
template< class BidirIterator, class UnaryPredicate >
BidirIterator stable_partition( BidirIterator first, BidirIterator last, UnaryPredicate p );
Effect
std::stable_partition 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 preserved.
Return
Iterator to the first element of the second group
Complexity
Given N = std::distance(first, last),
- Exactly N applications of the predicate and O(N) swaps if there is enough extra memory. If memory is insufficient, at most N log N swaps.
- O(N log N) swaps and O(N) applications of the predicate