# 25 Algorithms library [algorithms]

## 25.3 Mutating sequence operations [alg.modifying.operations]

### 25.3.13 Partitions [alg.partitions]

``` 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.