# 11 Algorithms library [algorithms]

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

### 11.4.1 Copy [alg.copy]

template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O> requires IndirectlyCopyable<I, O> tagged_pair<tag::in(I), tag::out(O)> copy(I first, S last, O result); template <InputRange Rng, WeaklyIncrementable O> requires IndirectlyCopyable<iterator_t<Rng>, O> tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)> copy(Rng&& rng, O result);

Effects: Copies elements in the range [first,last) into the range [result,result + (last - first)) starting from first and proceeding to last. For each non-negative integer n < (last - first), performs *(result + n) = *(first + n).

Returns: {last, result + (last - first)}.

Requires: result shall not be in the range [first,last).

Complexity: Exactly last - first assignments.

template <InputIterator I, WeaklyIncrementable O> requires IndirectlyCopyable<I, O> tagged_pair<tag::in(I), tag::out(O)> copy_n(I first, difference_type_t<I> n, O result);

Effects: For each non-negative integer i < n, performs *(result + i) = *(first + i).

Returns: {first + n, result + n}.

Complexity: Exactly n assignments.

template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O, class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred> requires IndirectlyCopyable<I, O> tagged_pair<tag::in(I), tag::out(O)> copy_if(I first, S last, O result, Pred pred, Proj proj = Proj{}); template <InputRange Rng, WeaklyIncrementable O, class Proj = identity, IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred> requires IndirectlyCopyable<iterator_t<Rng>, O> tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)> copy_if(Rng&& rng, O result, Pred pred, Proj proj = Proj{});

Let N be the number of iterators i in the range [first,last) for which the condition invoke(pred, invoke(proj, *i)) holds.

Requires: The ranges [first,last) and [result,result + N) shall not overlap.

Effects: Copies all of the elements referred to by the iterator i in the range [first,last) for which invoke(pred, invoke(proj, *i)) is true.

Returns: {last, result + N}.

Complexity: Exactly last - first applications of the corresponding predicate and projection.

Remarks: Stable ( ISO/IEC 14882:2014 §[algorithm.stable]).

template <BidirectionalIterator I1, Sentinel<I1> S1, BidirectionalIterator I2> requires IndirectlyCopyable<I1, I2> tagged_pair<tag::in(I1), tag::out(I2)> copy_backward(I1 first, S1 last, I2 result); template <BidirectionalRange Rng, BidirectionalIterator I> requires IndirectlyCopyable<iterator_t<Rng>, I> tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(I)> copy_backward(Rng&& rng, I result);

Effects: Copies elements in the range [first,last) into the range [result - (last-first),result) starting from last - 1 and proceeding to first.5 For each positive integer n <= (last - first), performs *(result - n) = *(last - n).

Requires: result shall not be in the range (first,last].

Returns: {last, result - (last - first)}.

Complexity: Exactly last - first assignments.

copy_backward should be used instead of copy when last is in the range [result - (last - first),result).

### 11.4.2 Move [alg.move]

template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O> requires IndirectlyMovable<I, O> tagged_pair<tag::in(I), tag::out(O)> move(I first, S last, O result); template <InputRange Rng, WeaklyIncrementable O> requires IndirectlyMovable<iterator_t<Rng>, O> tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)> move(Rng&& rng, O result);

Effects: Moves elements in the range [first,last) into the range [result,result + (last - first)) starting from first and proceeding to last. For each non-negative integer n < (last-first), performs *(result + n) = ranges::iter_move(first + n).

Returns: {last, result + (last - first)}.

Requires: result shall not be in the range [first,last).

Complexity: Exactly last - first move assignments.

template <BidirectionalIterator I1, Sentinel<I1> S1, BidirectionalIterator I2> requires IndirectlyMovable<I1, I2> tagged_pair<tag::in(I1), tag::out(I2)> move_backward(I1 first, S1 last, I2 result); template <BidirectionalRange Rng, BidirectionalIterator I> requires IndirectlyMovable<iterator_t<Rng>, I> tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(I)> move_backward(Rng&& rng, I result);

Effects: Moves elements in the range [first,last) into the range [result - (last-first),result) starting from last - 1 and proceeding to first.6 For each positive integer n <= (last - first), performs *(result - n) = ranges::iter_move(last - n).

Requires: result shall not be in the range (first,last].

Returns: {last, result - (last - first)}.

Complexity: Exactly last - first assignments.

move_backward should be used instead of move when last is in the range [result - (last - first),result).

### 11.4.3 swap [alg.swap]

template <ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2, Sentinel<I2> S2> requires IndirectlySwappable<I1, I2> tagged_pair<tag::in1(I1), tag::in2(I2)> swap_ranges(I1 first1, S1 last1, I2 first2, S2 last2); template <ForwardRange Rng1, ForwardRange Rng2> requires IndirectlySwappable<iterator_t<Rng1>, iterator_t<Rng2>> tagged_pair<tag::in1(safe_iterator_t<Rng1>), tag::in2(safe_iterator_t<Rng2>)> swap_ranges(Rng1&& rng1, Rng2&& rng2);

Effects: For each non-negative integer n < min(last1 - first1, last2 - first2) performs:
ranges::iter_swap(first1 + n, first2 + n).

Requires: The two ranges [first1,last1) and [first2,last2) shall not overlap. *(first1 + n) shall be swappable with ([concepts.lib.corelang.swappable]) *(first2 + n).

Returns: {first1 + n, first2 + n}, where n is min(last1 - first1, last2 - first2).

Complexity: Exactly min(last1 - first1, last2 - first2) swaps.

### 11.4.4 Transform [alg.transform]

template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O, CopyConstructible F, class Proj = identity> requires Writable<O, indirect_result_of_t<F&(projected<I, Proj>)>> tagged_pair<tag::in(I), tag::out(O)> transform(I first, S last, O result, F op, Proj proj = Proj{}); template <InputRange Rng, WeaklyIncrementable O, CopyConstructible F, class Proj = identity> requires Writable<O, indirect_result_of_t<F&( projected<iterator_t<R>, Proj>)>> tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)> transform(Rng&& rng, O result, F op, Proj proj = Proj{}); template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2, WeaklyIncrementable O, CopyConstructible F, class Proj1 = identity, class Proj2 = identity> requires Writable<O, indirect_result_of_t<F&(projected<I1, Proj1>, projected<I2, Proj2>)>> tagged_tuple<tag::in1(I1), tag::in2(I2), tag::out(O)> transform(I1 first1, S1 last1, I2 first2, S2 last2, O result, F binary_op, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{}); template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O, CopyConstructible F, class Proj1 = identity, class Proj2 = identity> requires Writable<O, indirect_result_of_t<F&( projected<iterator_t<Rng1>, Proj1>, projected<iterator_t<Rng2>, Proj2>)>> tagged_tuple<tag::in1(safe_iterator_t<Rng1>), tag::in2(safe_iterator_t<Rng2>), tag::out(O)> transform(Rng1&& rng1, Rng2&& rng2, O result, F binary_op, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

Let N be (last1 - first1) for unary transforms, or min(last1 - first1, last2 - first2) for binary transforms.

Effects: Assigns through every iterator i in the range [result,result + N) a new corresponding value equal to invoke(op, invoke(proj, *(first1 + (i - result)))) or invoke(binary_op, invoke(proj1, *(first1 + (i - result))), invoke(proj2, *(first2 + (i - result)))).

Requires: op and binary_op shall not invalidate iterators or subranges, or modify elements in the ranges [first1,first1 + N], [first2,first2 + N], and [result,result + N].7

Returns: {first1 + N, result + N} or make_tagged_tuple<tag::in1, tag::in2, tag::out>(first1 + N, first2 + N, result + N).

Complexity: Exactly N applications of op or binary_op and the corresponding projection(s).

Remarks: result may be equal to first1 in case of unary transform, or to first1 or first2 in case of binary transform.

The use of fully closed ranges is intentional.

### 11.4.5 Replace [alg.replace]

template <InputIterator I, Sentinel<I> S, class T1, class T2, class Proj = identity> requires Writable<I, const T2&> && IndirectRelation<equal_to<>, projected<I, Proj>, const T1*> I replace(I first, S last, const T1& old_value, const T2& new_value, Proj proj = Proj{}); template <InputRange Rng, class T1, class T2, class Proj = identity> requires Writable<iterator_t<Rng>, const T2&> && IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T1*> safe_iterator_t<Rng> replace(Rng&& rng, const T1& old_value, const T2& new_value, Proj proj = Proj{}); template <InputIterator I, Sentinel<I> S, class T, class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred> requires Writable<I, const T&> I replace_if(I first, S last, Pred pred, const T& new_value, Proj proj = Proj{}); template <InputRange Rng, class T, class Proj = identity, IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred> requires Writable<iterator_t<Rng>, const T&> safe_iterator_t<Rng> replace_if(Rng&& rng, Pred pred, const T& new_value, Proj proj = Proj{});

Effects: Assigns new_value through each iterator i in the range [first,last) when the following corresponding conditions hold: invoke(proj, *i) == old_value, invoke(pred, invoke(proj, *i)) != false.

Returns: last.

Complexity: Exactly last - first applications of the corresponding predicate and projection.

template <InputIterator I, Sentinel<I> S, class T1, class T2, OutputIterator<const T2&> O, class Proj = identity> requires IndirectlyCopyable<I, O> && IndirectRelation<equal_to<>, projected<I, Proj>, const T1*> tagged_pair<tag::in(I), tag::out(O)> replace_copy(I first, S last, O result, const T1& old_value, const T2& new_value, Proj proj = Proj{}); template <InputRange Rng, class T1, class T2, OutputIterator<const T2&> O, class Proj = identity> requires IndirectlyCopyable<iterator_t<Rng>, O> && IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T1*> tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)> replace_copy(Rng&& rng, O result, const T1& old_value, const T2& new_value, Proj proj = Proj{}); template <InputIterator I, Sentinel<I> S, class T, OutputIterator<const T&> O, class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred> requires IndirectlyCopyable<I, O> tagged_pair<tag::in(I), tag::out(O)> replace_copy_if(I first, S last, O result, Pred pred, const T& new_value, Proj proj = Proj{}); template <InputRange Rng, class T, OutputIterator<const T&> O, class Proj = identity, IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred> requires IndirectlyCopyable<iterator_t<Rng>, O> tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)> replace_copy_if(Rng&& rng, O result, Pred pred, const T& new_value, Proj proj = Proj{});

Requires: The ranges [first,last) and [result,result + (last - first)) shall not overlap.

Effects: Assigns to every iterator i in the range [result,result + (last - first)) either new_value or *(first + (i - result)) depending on whether the following corresponding conditions hold:

invoke(proj, *(first + (i - result))) == old_value
invoke(pred, invoke(proj, *(first + (i - result)))) != false

Returns: {last, result + (last - first)}.

Complexity: Exactly last - first applications of the corresponding predicate and projection.

### 11.4.6 Fill [alg.fill]

template <class T, OutputIterator<const T&> O, Sentinel<O> S> O fill(O first, S last, const T& value); template <class T, OutputRange<const T&> Rng> safe_iterator_t<Rng> fill(Rng&& rng, const T& value); template <class T, OutputIterator<const T&> O> O fill_n(O first, difference_type_t<O> n, const T& value);

Effects: fill assigns value through all the iterators in the range [first,last). fill_n assigns value through all the iterators in the counted range [first,n) if n is positive, otherwise it does nothing.

Returns: last, where last is first + max(n, 0) for fill_n.

Complexity: Exactly last - first assignments.

### 11.4.7 Generate [alg.generate]

template <Iterator O, Sentinel<O> S, CopyConstructible F> requires Invocable<F&> && Writable<O, result_of_t<F&()>> O generate(O first, S last, F gen); template <class Rng, CopyConstructible F> requires Invocable<F&> && OutputRange<Rng, result_of_t<F&()>> safe_iterator_t<Rng> generate(Rng&& rng, F gen); template <Iterator O, CopyConstructible F> requires Invocable<F&> && Writable<O, result_of_t<F&()>> O generate_n(O first, difference_type_t<O> n, F gen);

Effects: The generate algorithms invoke the function object gen and assign the return value of gen through all the iterators in the range [first,last). The generate_n algorithm invokes the function object gen and assigns the return value of gen through all the iterators in the counted range [first,n) if n is positive, otherwise it does nothing.

Returns: last, where last is first + max(n, 0) for generate_n.

Complexity: Exactly last - first evaluations of invoke(gen) and assignments.

### 11.4.8 Remove [alg.remove]

template <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity> requires Permutable<I> && IndirectRelation<equal_to<>, projected<I, Proj>, const T*> I remove(I first, S last, const T& value, Proj proj = Proj{}); template <ForwardRange Rng, class T, class Proj = identity> requires Permutable<iterator_t<Rng>> && IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T*> safe_iterator_t<Rng> remove(Rng&& rng, const T& value, Proj proj = Proj{}); template <ForwardIterator I, Sentinel<I> S, class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred> requires Permutable<I> I remove_if(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> remove_if(Rng&& rng, Pred pred, Proj proj = Proj{});

Effects: Eliminates all the elements referred to by iterator i in the range [first,last) for which the following corresponding conditions hold: invoke(proj, *i) == value, invoke(pred, invoke(proj, *i)) != false.

Returns: The end of the resulting range.

Remarks: Stable ( ISO/IEC 14882:2014 §[algorithm.stable]).

Complexity: Exactly last - first applications of the corresponding predicate and projection.

Note: each element in the range [ret,last), where ret is the returned value, has a valid but unspecified state, because the algorithms can eliminate elements by moving from elements that were originally in that range.

template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O, class T, class Proj = identity> requires IndirectlyCopyable<I, O> && IndirectRelation<equal_to<>, projected<I, Proj>, const T*> tagged_pair<tag::in(I), tag::out(O)> remove_copy(I first, S last, O result, const T& value, Proj proj = Proj{}); template <InputRange Rng, WeaklyIncrementable O, class T, class Proj = identity> requires IndirectlyCopyable<iterator_t<Rng>, O> && IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T*> tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)> remove_copy(Rng&& rng, O result, const T& value, Proj proj = Proj{}); template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O, class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred> requires IndirectlyCopyable<I, O> tagged_pair<tag::in(I), tag::out(O)> remove_copy_if(I first, S last, O result, Pred pred, Proj proj = Proj{}); template <InputRange Rng, WeaklyIncrementable O, class Proj = identity, IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred> requires IndirectlyCopyable<iterator_t<Rng>, O> tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)> remove_copy_if(Rng&& rng, O result, Pred pred, Proj proj = Proj{});

Requires: The ranges [first,last) and [result,result + (last - first)) shall not overlap.

Effects: Copies all the elements referred to by the iterator i in the range [first,last) for which the following corresponding conditions do not hold: invoke(proj, *i) == value, invoke(pred, invoke(proj, *i)) != false.

Returns: A pair consisting of last and the end of the resulting range.

Complexity: Exactly last - first applications of the corresponding predicate and projection.

Remarks: Stable ( ISO/IEC 14882:2014 §[algorithm.stable]).

### 11.4.9 Unique [alg.unique]

template <ForwardIterator I, Sentinel<I> S, class Proj = identity, IndirectRelation<projected<I, Proj>> R = equal_to<>> requires Permutable<I> I unique(I first, S last, R comp = R{}, Proj proj = Proj{}); template <ForwardRange Rng, class Proj = identity, IndirectRelation<projected<iterator_t<Rng>, Proj>> R = equal_to<>> requires Permutable<iterator_t<Rng>> safe_iterator_t<Rng> unique(Rng&& rng, R comp = R{}, Proj proj = Proj{});

Effects: For a nonempty range, eliminates all but the first element from every consecutive group of equivalent elements referred to by the iterator i in the range [first + 1,last) for which the following conditions hold: invoke(proj, *(i - 1)) == invoke(proj, *i) or invoke(pred, invoke(proj, *(i - 1)), invoke(proj, *i)) != false.

Returns: The end of the resulting range.

Complexity: For nonempty ranges, exactly (last - first) - 1 applications of the corresponding predicate and no more than twice as many applications of the projection.

template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O, class Proj = identity, IndirectRelation<projected<I, Proj>> R = equal_to<>> requires IndirectlyCopyable<I, O> && (ForwardIterator<I> || (InputIterator<O> && Same<value_type_t<I>, value_type_t<O>>) || IndirectlyCopyableStorable<I, O>) tagged_pair<tag::in(I), tag::out(O)> unique_copy(I first, S last, O result, R comp = R{}, Proj proj = Proj{}); template <InputRange Rng, WeaklyIncrementable O, class Proj = identity, IndirectRelation<projected<iterator_t<Rng>, Proj>> R = equal_to<>> requires IndirectlyCopyable<iterator_t<Rng>, O> && (ForwardIterator<iterator_t<Rng>> || (InputIterator<O> && Same<value_type_t<iterator_t<Rng>>, value_type_t<O>>) || IndirectlyCopyableStorable<iterator_t<Rng>, O>) tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)> unique_copy(Rng&& rng, O result, R comp = R{}, Proj proj = Proj{});

Requires: The ranges [first,last) and [result,result+(last-first)) shall not overlap.

Effects: Copies only the first element from every consecutive group of equal elements referred to by the iterator i in the range [first,last) for which the following corresponding conditions hold:

invoke(proj, *i) == invoke(proj, *(i - 1))

or

invoke(pred, invoke(proj, *i), invoke(proj, *(i - 1))) != false.

Returns: A pair consisting of last and the end of the resulting range.

Complexity: For nonempty ranges, exactly last - first - 1 applications of the corresponding predicate and no more than twice as many applications of the projection.

### 11.4.10 Reverse [alg.reverse]

template <BidirectionalIterator I, Sentinel<I> S> requires Permutable<I> I reverse(I first, S last); template <BidirectionalRange Rng> requires Permutable<iterator_t<Rng>> safe_iterator_t<Rng> reverse(Rng&& rng);

Effects: For each non-negative integer i < (last - first)/2, applies iter_swap to all pairs of iterators first + i, (last - i) - 1.

Returns: last.

Complexity: Exactly (last - first)/2 swaps.

template <BidirectionalIterator I, Sentinel<I> S, WeaklyIncrementable O> requires IndirectlyCopyable<I, O> tagged_pair<tag::in(I), tag::out(O)> reverse_copy(I first, S last, O result); template <BidirectionalRange Rng, WeaklyIncrementable O> requires IndirectlyCopyable<iterator_t<Rng>, O> tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)> reverse_copy(Rng&& rng, O result);

Effects: Copies the range [first,last) to the range [result,result+(last-first)) such that for every non-negative integer i < (last - first) the following assignment takes place: *(result + (last - first) - 1 - i) = *(first + i).

Requires: The ranges [first,last) and [result,result+(last-first)) shall not overlap.

Returns: {last, result + (last - first)}.

Complexity: Exactly last - first assignments.

### 11.4.11 Rotate [alg.rotate]

template <ForwardIterator I, Sentinel<I> S> requires Permutable<I> tagged_pair<tag::begin(I), tag::end(I)> rotate(I first, I middle, S last); template <ForwardRange Rng> requires Permutable<iterator_t<Rng>> tagged_pair<tag::begin(safe_iterator_t<Rng>), tag::end(safe_iterator_t<Rng>)> rotate(Rng&& rng, iterator_t<Rng> middle);

Effects: For each non-negative integer i < (last - first), places the element from the position first + i into position first + (i + (last - middle)) % (last - first).

Returns: {first + (last - middle), last}.

Remarks: This is a left rotate.

Requires: [first,middle) and [middle,last) shall be valid ranges.

Complexity: At most last - first swaps.

template <ForwardIterator I, Sentinel<I> S, WeaklyIncrementable O> requires IndirectlyCopyable<I, O> tagged_pair<tag::in(I), tag::out(O)> rotate_copy(I first, I middle, S last, O result); template <ForwardRange Rng, WeaklyIncrementable O> requires IndirectlyCopyable<iterator_t<Rng>, O> tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)> rotate_copy(Rng&& rng, iterator_t<Rng> middle, O result);

Effects: Copies the range [first,last) to the range [result,result + (last - first)) such that for each non-negative integer i < (last - first) the following assignment takes place: *(result + i) = *(first + (i + (middle - first)) % (last - first)).

Returns: {last, result + (last - first)}.

Requires: The ranges [first,last) and [result,result + (last - first)) shall not overlap.

Complexity: Exactly last - first assignments.

### 11.4.12 Shuffle [alg.random.shuffle]

template <RandomAccessIterator I, Sentinel<I> S, class Gen> requires Permutable<I> && UniformRandomNumberGenerator<remove_reference_t<Gen>> && ConvertibleTo<result_of_t<Gen&()>, difference_type_t<I>> I shuffle(I first, S last, Gen&& g); template <RandomAccessRange Rng, class Gen> requires Permutable<I> && UniformRandomNumberGenerator<remove_reference_t<Gen>> && ConvertibleTo<result_of_t<Gen&()>, difference_type_t<I>> safe_iterator_t<Rng> shuffle(Rng&& rng, Gen&& g);

Effects: Permutes the elements in the range [first,last) such that each possible permutation of those elements has equal probability of appearance.

Complexity: Exactly (last - first) - 1 swaps.

Returns: last

Remarks: To the extent that the implementation of this function makes use of random numbers, the object g shall serve as the implementation's source of randomness.

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