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).
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).
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.
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.
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.
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.
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.
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]).
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.
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.
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.
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.
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.