25 Algorithms library [algorithms]

25.4 Mutating sequence operations [alg.modifying.operations]

25.4.14 Partitions [alg.partitions]

template <class InputIterator, class Predicate> bool is_partitioned(InputIterator first, InputIterator last, Predicate pred); template <class ExecutionPolicy, class InputIterator, class Predicate> bool is_partitioned(ExecutionPolicy&& exec, 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); template<class ExecutionPolicy, class ForwardIterator, class Predicate> ForwardIterator partition(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Predicate pred);

Requires: ForwardIterator shall satisfy the requirements of ValueSwappable ([swappable.requirements]).

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.

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); template<class ExecutionPolicy, class BidirectionalIterator, class Predicate> BidirectionalIterator stable_partition(ExecutionPolicy&& exec, BidirectionalIterator first, BidirectionalIterator last, Predicate pred);

Requires: BidirectionalIterator shall satisfy the requirements of ValueSwappable ([swappable.requirements]). The type of *first shall satisfy the requirements of MoveConstructible (Table [tab:moveconstructible]) and of MoveAssignable (Table [tab:moveassignable]).

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.

Complexity: At most N log(N) swaps, where N = last - first, but only Ο(N) 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); template <class ExecutionPolicy, class InputIterator, class OutputIterator1, class OutputIterator2, class Predicate> pair<OutputIterator1, OutputIterator2> partition_copy(ExecutionPolicy&& exec, InputIterator first, InputIterator last, OutputIterator1 out_true, OutputIterator2 out_false, Predicate pred);

Requires: InputIterator's value type shall be CopyAssignable, and shall be writable ([iterator.requirements.general]) 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.