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.