template <class InputIterator, class Predicate>
bool is_partitioned(InputIterator first, InputIterator last, Predicate pred);
Requires: InputIterator's value type shall be convertible to Predicate's argument type.
Returns: true if [first,last) is empty or if [first,last) is partitioned by pred, i.e. if all elements that satisfy pred appear before those that do not.
Complexity: Linear. At most last - first applications of pred.
template<class ForwardIterator, class Predicate>
ForwardIterator
partition(ForwardIterator first,
ForwardIterator last, Predicate pred);
Effects: Places all the elements in the range [first,last) that satisfy pred before all the elements that do not satisfy it.
Returns: An iterator i such that for every iterator j in the range [first,i) pred(*j) != false, and for every iterator k in the range [i,last), pred(*k) == false.
Requires: ForwardIterator shall satisfy the requirements of ValueSwappable ([swappable.requirements]).
Complexity: If ForwardIterator meets the requirements for a BidirectionalIterator, at most (last - first) / 2 swaps are done; otherwise at most last - first swaps are done. Exactly last - first applications of the predicate are done.
template<class BidirectionalIterator, class Predicate>
BidirectionalIterator
stable_partition(BidirectionalIterator first,
BidirectionalIterator last, Predicate pred);
Effects: Places all the elements in the range [first,last) that satisfy pred before all the elements that do not satisfy it.
Returns: An iterator i such that for every iterator j in the range [first,i), pred(*j) != false, and for every iterator k in the range [i,last), pred(*k) == false. The relative order of the elements in both groups is preserved.
Requires: BidirectionalIterator shall satisfy the requirements of ValueSwappable ([swappable.requirements]). The type of *first shall satisfy the requirements of MoveConstructible (Table [moveconstructible]) and of MoveAssignable (Table [moveassignable]).
Complexity: At most (last - first) * log(last - first) swaps, but only linear number of swaps if there is enough extra memory. Exactly last - first applications of the predicate.
template <class InputIterator, class OutputIterator1,
class OutputIterator2, class Predicate>
pair<OutputIterator1, OutputIterator2>
partition_copy(InputIterator first, InputIterator last,
OutputIterator1 out_true, OutputIterator2 out_false,
Predicate pred);
Requires: InputIterator's value type shall be CopyAssignable, and shall be writable to the out_true and out_false OutputIterators, and shall be convertible to Predicate's argument type. The input range shall not overlap with either of the output ranges.
Effects: For each iterator i in [first,last), copies *i to the output range beginning with out_true if pred(*i) is true, or to the output range beginning with out_false otherwise.
Returns: A pair p such that p.first is the end of the output range beginning at out_true and p.second is the end of the output range beginning at out_false.
Complexity: Exactly last - first applications of pred.
template<class ForwardIterator, class Predicate>
ForwardIterator partition_point(ForwardIterator first,
ForwardIterator last,
Predicate pred);
Requires: ForwardIterator's value type shall be convertible to Predicate's argument type. [first,last) shall be partitioned by pred, i.e. all elements that satisfy pred shall appear before those that do not.
Returns: An iterator mid such that all_of(first, mid, pred) and none_of(mid, last, pred) are both true.
Complexity: Ο(log(last - first)) applications of pred.