# 11 Algorithms library [algorithms]

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

### 11.4.13 Partitions [alg.partitions]

``` template <InputIterator I, Sentinel<I> S, class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred> bool is_partitioned(I first, S last, Pred pred, Proj proj = Proj{}); template <InputRange Rng, class Proj = identity, IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred> bool is_partitioned(Rng&& rng, Pred pred, Proj proj = Proj{}); ```

Returns: true if [first,last) is empty or if [first,last) is partitioned by pred and proj, i.e. if all iterators i for which invoke(pred, invoke(proj, *i)) != false come before those that do not, for every i in [first,last).

Complexity: Linear. At most last - first applications of pred and proj.

``` template <ForwardIterator I, Sentinel<I> S, class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred> requires Permutable<I> I partition(I first, S last, Pred pred, Proj proj = Proj{}); template <ForwardRange Rng, class Proj = identity, IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred> requires Permutable<iterator_t<Rng>> safe_iterator_t<Rng> partition(Rng&& rng, Pred pred, Proj proj = Proj{}); ```

Effects: Permutes the elements in the range [first,last) such that there exists an iterator i such that for every iterator j in the range [first,i) invoke(pred, invoke(proj, *j)) != false, and for every iterator k in the range [i,last), invoke(pred, invoke(proj, *k)) == false.

Returns: An iterator i such that for every iterator j in the range [first,i) invoke(pred, invoke(proj, *j)) != false, and for every iterator k in the range [i,last), invoke(pred, invoke(proj, *k)) == false.

Complexity: If I meets the requirements for a BidirectionalIterator, at most (last - first) / 2 swaps; otherwise at most last - first swaps. Exactly last - first applications of the predicate and projection.

``` template <BidirectionalIterator I, Sentinel<I> S, class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred> requires Permutable<I> I stable_partition(I first, S last, Pred pred, Proj proj = Proj{}); template <BidirectionalRange Rng, class Proj = identity, IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred> requires Permutable<iterator_t<Rng>> safe_iterator_t<Rng> stable_partition(Rng&& rng, Pred pred, Proj proj = Proj{}); ```

Effects: Permutes the elements in the range [first,last) such that there exists an iterator i such that for every iterator j in the range [first,i) invoke(pred, invoke(proj, *j)) != false, and for every iterator k in the range [i,last), invoke(pred, invoke(proj, *k)) == false.

Returns: An iterator i such that for every iterator j in the range [first,i), invoke(pred, invoke(proj, *j)) != false, and for every iterator k in the range [i,last), invoke(pred, invoke(proj, *k)) == false. The relative order of the elements in both groups is preserved.

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 and projection.

``` template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O1, WeaklyIncrementable O2, class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred> requires IndirectlyCopyable<I, O1> && IndirectlyCopyable<I, O2> tagged_tuple<tag::in(I), tag::out1(O1), tag::out2(O2)> partition_copy(I first, S last, O1 out_true, O2 out_false, Pred pred, Proj proj = Proj{}); template <InputRange Rng, WeaklyIncrementable O1, WeaklyIncrementable O2, class Proj = identity, IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred> requires IndirectlyCopyable<iterator_t<Rng>, O1> && IndirectlyCopyable<iterator_t<Rng>, O2> tagged_tuple<tag::in(safe_iterator_t<Rng>), tag::out1(O1), tag::out2(O2)> partition_copy(Rng&& rng, O1 out_true, O2 out_false, Pred pred, Proj proj = Proj{}); ```

Requires: 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 invoke(pred, invoke(proj, *i)) is true, or to the output range beginning with out_false otherwise.

Returns: A tuple p such that get<0>(p) is last, get<1>(p) is the end of the output range beginning at out_true, and get<2>(p) is the end of the output range beginning at out_false.

Complexity: Exactly last - first applications of pred and proj.

``` template <ForwardIterator I, Sentinel<I> S, class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred> I partition_point(I first, S last, Pred pred, Proj proj = Proj{}); template <ForwardRange Rng, class Proj = identity, IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred> safe_iterator_t<Rng> partition_point(Rng&& rng, Pred pred, Proj proj = Proj{}); ```

Requires: [first,last) shall be partitioned by pred and proj, i.e. there shall be an iterator mid such that all_of(first, mid, pred, proj) and none_of(mid, last, pred, proj) are both true.

Returns: An iterator mid such that all_of(first, mid, pred, proj) and none_of(mid, last, pred, proj) are both true.

Complexity: Ο(log(last - first)) applications of pred and proj.