27 Algorithms library [algorithms]

27.7 Mutating sequence operations [alg.modifying.operations]

27.7.1 Copy [alg.copy]

🔗
template<class InputIterator, class OutputIterator> constexpr OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result); template<input_iterator I, sentinel_for<I> S, weakly_incrementable O> requires indirectly_copyable<I, O> constexpr ranges::copy_result<I, O> ranges::copy(I first, S last, O result); template<input_range R, weakly_incrementable O> requires indirectly_copyable<iterator_t<R>, O> constexpr ranges::copy_result<borrowed_iterator_t<R>, O> ranges::copy(R&& r, O result);
1
#
Let N be last - first.
2
#
Preconditions: result is not in the range [first, last).
3
#
Effects: Copies elements in the range [first, last) into the range [result, result + N) starting from first and proceeding to last.
For each non-negative integer , performs *(result + n) = *(first + n).
4
#
Returns:
  • (4.1)
    result + N for the overload in namespace std.
  • (4.2)
    {last, result + N} for the overloads in namespace ranges.
5
#
Complexity: Exactly N assignments.
🔗
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> ForwardIterator2 copy(ExecutionPolicy&& policy, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result);
6
#
Preconditions: The ranges [first, last) and [result, result + (last - first)) do not overlap.
7
#
Effects: Copies elements in the range [first, last) into the range [result, result + (last - first)).
For each non-negative integer n < (last - first), performs *(result + n) = *(first + n).
8
#
Returns: result + (last - first).
9
#
Complexity: Exactly last - first assignments.
🔗
template<class InputIterator, class Size, class OutputIterator> constexpr OutputIterator copy_n(InputIterator first, Size n, OutputIterator result); template<class ExecutionPolicy, class ForwardIterator1, class Size, class ForwardIterator2> ForwardIterator2 copy_n(ExecutionPolicy&& exec, ForwardIterator1 first, Size n, ForwardIterator2 result); template<input_iterator I, weakly_incrementable O> requires indirectly_copyable<I, O> constexpr ranges::copy_n_result<I, O> ranges::copy_n(I first, iter_difference_t<I> n, O result);
10
#
Let N be max(0, n).
11
#
Mandates: The type Size is convertible to an integral type ([conv.integral], [class.conv]).
12
#
Effects: For each non-negative integer , performs *(result + i) = *(first + i).
13
#
Returns:
  • (13.1)
    result + N for the overloads in namespace std.
  • (13.2)
    {first + N, result + N} for the overload in namespace ranges.
14
#
Complexity: Exactly N assignments.
🔗
template<class InputIterator, class OutputIterator, class Predicate> constexpr OutputIterator copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Predicate> ForwardIterator2 copy_if(ExecutionPolicy&& exec, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result, Predicate pred); template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred> requires indirectly_copyable<I, O> constexpr ranges::copy_if_result<I, O> ranges::copy_if(I first, S last, O result, Pred pred, Proj proj = {}); template<input_range R, weakly_incrementable O, class Proj = identity, indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> requires indirectly_copyable<iterator_t<R>, O> constexpr ranges::copy_if_result<borrowed_iterator_t<R>, O> ranges::copy_if(R&& r, O result, Pred pred, Proj proj = {});
15
#
Let E be:
  • (15.1)
    bool(pred(*i)) for the overloads in namespace std;
  • (15.2)
    bool(invoke(pred, invoke(proj, *i))) for the overloads in namespace ranges,
and N be the number of iterators i in the range [first, last) for which the condition E holds.
16
#
Preconditions: The ranges [first, last) and [result, result + (last - first)) do not overlap.
[Note 1: 
For the overload with an ExecutionPolicy, there might be a performance cost if iterator_traits<ForwardIterator1>​::​value_type is not Cpp17MoveConstructible (Table 31).
— end note]
17
#
Effects: Copies all of the elements referred to by the iterator i in the range [first, last) for which E is true.
18
#
Returns:
  • (18.1)
    result + N for the overloads in namespace std.
  • (18.2)
    {last, result + N} for the overloads in namespace ranges.
19
#
Complexity: Exactly last - first applications of the corresponding predicate and any projection.
20
#
Remarks: Stable ([algorithm.stable]).
🔗
template<class BidirectionalIterator1, class BidirectionalIterator2> constexpr BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result); template<bidirectional_iterator I1, sentinel_for<I1> S1, bidirectional_iterator I2> requires indirectly_copyable<I1, I2> constexpr ranges::copy_backward_result<I1, I2> ranges::copy_backward(I1 first, S1 last, I2 result); template<bidirectional_range R, bidirectional_iterator I> requires indirectly_copyable<iterator_t<R>, I> constexpr ranges::copy_backward_result<borrowed_iterator_t<R>, I> ranges::copy_backward(R&& r, I result);
21
#
Let N be last - first.
22
#
Preconditions: result is not in the range (first, last].
23
#
Effects: Copies elements in the range [first, last) into the range [result - N, result) starting from last - 1 and proceeding to first.214
For each positive integer n  ≤ N, performs *(result - n) = *(last - n).
24
#
Returns:
  • (24.1)
    result - N for the overload in namespace std.
  • (24.2)
    {last, result - N} for the overloads in namespace ranges.
25
#
Complexity: Exactly N assignments.
214)214)
copy_backward can be used instead of copy when last is in the range [result - N, result).

27.7.2 Move [alg.move]

🔗
template<class InputIterator, class OutputIterator> constexpr OutputIterator move(InputIterator first, InputIterator last, OutputIterator result); template<input_iterator I, sentinel_for<I> S, weakly_incrementable O> requires indirectly_movable<I, O> constexpr ranges::move_result<I, O> ranges::move(I first, S last, O result); template<input_range R, weakly_incrementable O> requires indirectly_movable<iterator_t<R>, O> constexpr ranges::move_result<borrowed_iterator_t<R>, O> ranges::move(R&& r, O result);
1
#
Let E be
  • (1.1)
    std​::​move(*(first + n)) for the overload in namespace std;
  • (1.2)
    ranges​::​iter_move(first + n) for the overloads in namespace ranges.
Let N be last - first.
2
#
Preconditions: result is not in the range [first, last).
3
#
Effects: Moves elements in the range [first, last) into the range [result, result + N) starting from first and proceeding to last.
For each non-negative integer , performs *(result + n) = E.
4
#
Returns:
  • (4.1)
    result + N for the overload in namespace std.
  • (4.2)
    {last, result + N} for the overloads in namespace ranges.
5
#
Complexity: Exactly N assignments.
🔗
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> ForwardIterator2 move(ExecutionPolicy&& policy, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result);
6
#
Let N be last - first.
7
#
Preconditions: The ranges [first, last) and [result, result + N) do not overlap.
8
#
Effects: Moves elements in the range [first, last) into the range [result, result + N).
For each non-negative integer , performs *(result + n) = std​::​​move(*(first + n)).
9
#
Returns: result + N.
10
#
Complexity: Exactly N assignments.
🔗
template<class BidirectionalIterator1, class BidirectionalIterator2> constexpr BidirectionalIterator2 move_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result); template<bidirectional_iterator I1, sentinel_for<I1> S1, bidirectional_iterator I2> requires indirectly_movable<I1, I2> constexpr ranges::move_backward_result<I1, I2> ranges::move_backward(I1 first, S1 last, I2 result); template<bidirectional_range R, bidirectional_iterator I> requires indirectly_movable<iterator_t<R>, I> constexpr ranges::move_backward_result<borrowed_iterator_t<R>, I> ranges::move_backward(R&& r, I result);
11
#
Let E be
  • (11.1)
    std​::​move(*(last - n)) for the overload in namespace std;
  • (11.2)
    ranges​::​iter_move(last - n) for the overloads in namespace ranges.
Let N be last - first.
12
#
Preconditions: result is not in the range (first, last].
13
#
Effects: Moves elements in the range [first, last) into the range [result - N, result) starting from last - 1 and proceeding to first.215
For each positive integer n  ≤ N, performs *(result - n) = E.
14
#
Returns:
  • (14.1)
    result - N for the overload in namespace std.
  • (14.2)
    {last, result - N} for the overloads in namespace ranges.
15
#
Complexity: Exactly N assignments.
215)215)
move_backward can be used instead of move when last is in the range [result - N, result).

27.7.3 Swap [alg.swap]

🔗
template<class ForwardIterator1, class ForwardIterator2> constexpr ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); // freestanding template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> ForwardIterator2 swap_ranges(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2> requires indirectly_swappable<I1, I2> constexpr ranges::swap_ranges_result<I1, I2> ranges::swap_ranges(I1 first1, S1 last1, I2 first2, S2 last2); template<input_range R1, input_range R2> requires indirectly_swappable<iterator_t<R1>, iterator_t<R2>> constexpr ranges::swap_ranges_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>> ranges::swap_ranges(R1&& r1, R2&& r2);
1
#
Let:
  • (1.1)
    last2 be first2 + (last1 - first1) for the overloads with no parameter named last2;
  • (1.2)
    M be min(last1 - first1,  last2 - first2).
2
#
Preconditions: The two ranges [first1, last1) and [first2, last2) do not overlap.
For the overloads in namespace std, *(first1 + n) is swappable with ([swappable.requirements]) *(first2 + n).
3
#
Effects: For each non-negative integer performs:
  • (3.1)
    swap(*(first1 + n), *(first2 + n)) for the overloads in namespace std;
  • (3.2)
    ranges​::​iter_swap(first1 + n, first2 + n) for the overloads in namespace ranges.
4
#
Returns:
  • (4.1)
    last2 for the overloads in namespace std.
  • (4.2)
    {first1 + M, first2 + M} for the overloads in namespace ranges.
5
#
Complexity: Exactly M swaps.
🔗
template<class ForwardIterator1, class ForwardIterator2> constexpr void iter_swap(ForwardIterator1 a, ForwardIterator2 b);
6
#
Preconditions: a and b are dereferenceable.
*a is swappable with ([swappable.requirements]) *b.
7
#
Effects: As if by swap(*a, *b).

27.7.4 Transform [alg.transform]

🔗
template<class InputIterator, class OutputIterator, class UnaryOperation> constexpr OutputIterator transform(InputIterator first1, InputIterator last1, OutputIterator result, UnaryOperation op); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class UnaryOperation> ForwardIterator2 transform(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 result, UnaryOperation op); template<class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation> constexpr OutputIterator transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperation binary_op); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class BinaryOperation> ForwardIterator transform(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator result, BinaryOperation binary_op); template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, copy_constructible F, class Proj = identity> requires indirectly_writable<O, indirect_result_t<F&, projected<I, Proj>>> constexpr ranges::unary_transform_result<I, O> ranges::transform(I first1, S last1, O result, F op, Proj proj = {}); template<input_range R, weakly_incrementable O, copy_constructible F, class Proj = identity> requires indirectly_writable<O, indirect_result_t<F&, projected<iterator_t<R>, Proj>>> constexpr ranges::unary_transform_result<borrowed_iterator_t<R>, O> ranges::transform(R&& r, O result, F op, Proj proj = {}); template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2, weakly_incrementable O, copy_constructible F, class Proj1 = identity, class Proj2 = identity> requires indirectly_writable<O, indirect_result_t<F&, projected<I1, Proj1>, projected<I2, Proj2>>> constexpr ranges::binary_transform_result<I1, I2, O> ranges::transform(I1 first1, S1 last1, I2 first2, S2 last2, O result, F binary_op, Proj1 proj1 = {}, Proj2 proj2 = {}); template<input_range R1, input_range R2, weakly_incrementable O, copy_constructible F, class Proj1 = identity, class Proj2 = identity> requires indirectly_writable<O, indirect_result_t<F&, projected<iterator_t<R1>, Proj1>, projected<iterator_t<R2>, Proj2>>> constexpr ranges::binary_transform_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O> ranges::transform(R1&& r1, R2&& r2, O result, F binary_op, Proj1 proj1 = {}, Proj2 proj2 = {});
1
#
Let:
  • (1.1)
    last2 be first2 + (last1 - first1) for the overloads with parameter first2 but no parameter last2;
  • (1.2)
    N be last1 - first1 for unary transforms, or min(last1 - first1,  last2 - first2) for binary transforms;
  • (1.3)
    E be
    • (1.3.1)
      op(*(first1 + (i - result))) for unary transforms defined in namespace std;
    • (1.3.2)
      binary_op(*(first1 + (i - result)), *(first2 + (i - result))) for binary transforms defined in namespace std;
    • (1.3.3)
      invoke(op, invoke(proj, *(first1 + (i - result)))) for unary transforms defined in namespace ranges;
    • (1.3.4)
      invoke(binary_op, invoke(proj1, *(first1 + (i - result))), invoke(proj2,
      *(first2 + (i - result))))       for binary transforms defined in namespace ranges.
2
#
Preconditions: op and binary_op do not invalidate iterators or subranges, nor modify elements in the ranges
3
#
Effects: Assigns through every iterator i in the range [result, result + N) a new corresponding value equal to E.
4
#
Returns:
  • (4.1)
    result + N for the overloads defined in namespace std.
  • (4.2)
    {first1 + N, result + N} for unary transforms defined in namespace ranges.
  • (4.3)
    {first1 + N, first2 + N, result + N} for binary transforms defined in namespace ranges.
5
#
Complexity: Exactly N applications of op or binary_op, and any projections.
This requirement also applies to the overload with an ExecutionPolicy.
6
#
Remarks: result may be equal to first1 or first2.
216)216)
The use of fully closed ranges is intentional.

27.7.5 Replace [alg.replace]

🔗
template<class ForwardIterator, class T> constexpr void replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value); template<class ExecutionPolicy, class ForwardIterator, class T> void replace(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value); template<class ForwardIterator, class Predicate, class T> constexpr void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value); template<class ExecutionPolicy, class ForwardIterator, class Predicate, class T> void replace_if(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value); template<input_iterator I, sentinel_for<I> S, class T1, class T2, class Proj = identity> requires indirectly_writable<I, const T2&> && indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T1*> constexpr I ranges::replace(I first, S last, const T1& old_value, const T2& new_value, Proj proj = {}); template<input_range R, class T1, class T2, class Proj = identity> requires indirectly_writable<iterator_t<R>, const T2&> && indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T1*> constexpr borrowed_iterator_t<R> ranges::replace(R&& r, const T1& old_value, const T2& new_value, Proj proj = {}); template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred> requires indirectly_writable<I, const T&> constexpr I ranges::replace_if(I first, S last, Pred pred, const T& new_value, Proj proj = {}); template<input_range R, class T, class Proj = identity, indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> requires indirectly_writable<iterator_t<R>, const T&> constexpr borrowed_iterator_t<R> ranges::replace_if(R&& r, Pred pred, const T& new_value, Proj proj = {});
1
#
Let E be
  • (1.1)
    bool(*i == old_value) for replace;
  • (1.2)
    bool(pred(*i)) for replace_if;
  • (1.3)
    bool(invoke(proj, *i) == old_value) for ranges​::​replace;
  • (1.4)
    bool(invoke(pred, invoke(proj, *i))) for ranges​::​replace_if.
2
#
Mandates: new_value is writable ([iterator.requirements.general]) to first.
3
#
Effects: Substitutes elements referred by the iterator i in the range [first, last) with new_value, when E is true.
4
#
Returns: last for the overloads in namespace ranges.
5
#
Complexity: Exactly last - first applications of the corresponding predicate and any projection.
🔗
template<class InputIterator, class OutputIterator, class T> constexpr OutputIterator replace_copy(InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T& new_value); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class T> ForwardIterator2 replace_copy(ExecutionPolicy&& exec, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result, const T& old_value, const T& new_value); template<class InputIterator, class OutputIterator, class Predicate, class T> constexpr OutputIterator replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Predicate, class T> ForwardIterator2 replace_copy_if(ExecutionPolicy&& exec, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result, Predicate pred, const T& new_value); template<input_iterator I, sentinel_for<I> S, class T1, class T2, output_iterator<const T2&> O, class Proj = identity> requires indirectly_copyable<I, O> && indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T1*> constexpr ranges::replace_copy_result<I, O> ranges::replace_copy(I first, S last, O result, const T1& old_value, const T2& new_value, Proj proj = {}); template<input_range R, class T1, class T2, output_iterator<const T2&> O, class Proj = identity> requires indirectly_copyable<iterator_t<R>, O> && indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T1*> constexpr ranges::replace_copy_result<borrowed_iterator_t<R>, O> ranges::replace_copy(R&& r, O result, const T1& old_value, const T2& new_value, Proj proj = {}); template<input_iterator I, sentinel_for<I> S, class T, output_iterator<const T&> O, class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred> requires indirectly_copyable<I, O> constexpr ranges::replace_copy_if_result<I, O> ranges::replace_copy_if(I first, S last, O result, Pred pred, const T& new_value, Proj proj = {}); template<input_range R, class T, output_iterator<const T&> O, class Proj = identity, indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> requires indirectly_copyable<iterator_t<R>, O> constexpr ranges::replace_copy_if_result<borrowed_iterator_t<R>, O> ranges::replace_copy_if(R&& r, O result, Pred pred, const T& new_value, Proj proj = {});
6
#
Let E be
  • (6.1)
    bool(*(first + (i - result)) == old_value) for replace_copy;
  • (6.2)
    bool(pred(*(first + (i - result)))) for replace_copy_if;
  • (6.3)
    bool(invoke(proj, *(first + (i - result))) == old_value) for ranges​::​replace_copy;
  • (6.4)
    bool(invoke(pred, invoke(proj, *(first + (i - result))))) for ranges​::​replace_copy_if.
7
#
Mandates: The results of the expressions *first and new_value are writable ([iterator.requirements.general]) to result.
8
#
Preconditions: The ranges [first, last) and [result, result + (last - first)) do not overlap.
9
#
Effects: Assigns through every iterator i in the range [result, result + (last - first)) a new corresponding value
  • (9.1)
    new_value if E is true or
  • (9.2)
    *(first + (i - result)) otherwise.
10
#
Returns:
  • (10.1)
    result + (last - first) for the overloads in namespace std.
  • (10.2)
    {last, result + (last - first)} for the overloads in namespace ranges.
11
#
Complexity: Exactly last - first applications of the corresponding predicate and any projection.

27.7.6 Fill [alg.fill]

🔗
template<class ForwardIterator, class T> constexpr void fill(ForwardIterator first, ForwardIterator last, const T& value); template<class ExecutionPolicy, class ForwardIterator, class T> void fill(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, const T& value); template<class OutputIterator, class Size, class T> constexpr OutputIterator fill_n(OutputIterator first, Size n, const T& value); template<class ExecutionPolicy, class ForwardIterator, class Size, class T> ForwardIterator fill_n(ExecutionPolicy&& exec, ForwardIterator first, Size n, const T& value); template<class T, output_iterator<const T&> O, sentinel_for<O> S> constexpr O ranges::fill(O first, S last, const T& value); template<class T, output_range<const T&> R> constexpr borrowed_iterator_t<R> ranges::fill(R&& r, const T& value); template<class T, output_iterator<const T&> O> constexpr O ranges::fill_n(O first, iter_difference_t<O> n, const T& value);
1
#
Let N be max(0, n) for the fill_n algorithms, and last - first for the fill algorithms.
2
#
Mandates: The expression value is writable ([iterator.requirements.general]) to the output iterator.
The type Size is convertible to an integral type ([conv.integral], [class.conv]).
3
#
Effects: Assigns value through all the iterators in the range [first, first + N).
4
#
Returns: first + N.
5
#
Complexity: Exactly N assignments.

27.7.7 Generate [alg.generate]

🔗
template<class ForwardIterator, class Generator> constexpr void generate(ForwardIterator first, ForwardIterator last, Generator gen); template<class ExecutionPolicy, class ForwardIterator, class Generator> void generate(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Generator gen); template<class OutputIterator, class Size, class Generator> constexpr OutputIterator generate_n(OutputIterator first, Size n, Generator gen); template<class ExecutionPolicy, class ForwardIterator, class Size, class Generator> ForwardIterator generate_n(ExecutionPolicy&& exec, ForwardIterator first, Size n, Generator gen); template<input_or_output_iterator O, sentinel_for<O> S, copy_constructible F> requires invocable<F&> && indirectly_writable<O, invoke_result_t<F&>> constexpr O ranges::generate(O first, S last, F gen); template<class R, copy_constructible F> requires invocable<F&> && output_range<R, invoke_result_t<F&>> constexpr borrowed_iterator_t<R> ranges::generate(R&& r, F gen); template<input_or_output_iterator O, copy_constructible F> requires invocable<F&> && indirectly_writable<O, invoke_result_t<F&>> constexpr O ranges::generate_n(O first, iter_difference_t<O> n, F gen);
1
#
Let N be max(0, n) for the generate_n algorithms, and last - first for the generate algorithms.
2
#
Mandates: Size is convertible to an integral type ([conv.integral], [class.conv]).
3
#
Effects: Assigns the result of successive evaluations of gen() through each iterator in the range [first, first + N).
4
#
Returns: first + N.
5
#
Complexity: Exactly N evaluations of gen() and assignments.

27.7.8 Remove [alg.remove]

🔗
template<class ForwardIterator, class T> constexpr ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value); template<class ExecutionPolicy, class ForwardIterator, class T> ForwardIterator remove(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, const T& value); template<class ForwardIterator, class Predicate> constexpr ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate pred); template<class ExecutionPolicy, class ForwardIterator, class Predicate> ForwardIterator remove_if(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Predicate pred); template<permutable I, sentinel_for<I> S, class T, class Proj = identity> requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*> constexpr subrange<I> ranges::remove(I first, S last, const T& value, Proj proj = {}); template<forward_range R, class T, class Proj = identity> requires permutable<iterator_t<R>> && indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*> constexpr borrowed_subrange_t<R> ranges::remove(R&& r, const T& value, Proj proj = {}); template<permutable I, sentinel_for<I> S, class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred> constexpr subrange<I> ranges::remove_if(I first, S last, Pred pred, Proj proj = {}); template<forward_range R, class Proj = identity, indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> requires permutable<iterator_t<R>> constexpr borrowed_subrange_t<R> ranges::remove_if(R&& r, Pred pred, Proj proj = {});
1
#
Let E be
  • (1.1)
    bool(*i == value) for remove;
  • (1.2)
    bool(pred(*i)) for remove_if;
  • (1.3)
    bool(invoke(proj, *i) == value) for ranges​::​remove;
  • (1.4)
    bool(invoke(pred, invoke(proj, *i))) for ranges​::​remove_if.
2
#
Preconditions: For the algorithms in namespace std, the type of *first meets the Cpp17MoveAssignable requirements (Table 33).
3
#
Effects: Eliminates all the elements referred to by iterator i in the range [first, last) for which E holds.
4
#
Returns: Let j be the end of the resulting range.
Returns:
  • (4.1)
    j for the overloads in namespace std.
  • (4.2)
    {j, last} for the overloads in namespace ranges.
5
#
Complexity: Exactly last - first applications of the corresponding predicate and any projection.
6
#
Remarks: Stable ([algorithm.stable]).
7
#
[Note 1: 
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.
— end note]
🔗
template<class InputIterator, class OutputIterator, class T> constexpr OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class T> ForwardIterator2 remove_copy(ExecutionPolicy&& exec, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result, const T& value); template<class InputIterator, class OutputIterator, class Predicate> constexpr OutputIterator remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Predicate> ForwardIterator2 remove_copy_if(ExecutionPolicy&& exec, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result, Predicate pred); template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class T, class Proj = identity> requires indirectly_copyable<I, O> && indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*> constexpr ranges::remove_copy_result<I, O> ranges::remove_copy(I first, S last, O result, const T& value, Proj proj = {}); template<input_range R, weakly_incrementable O, class T, class Proj = identity> requires indirectly_copyable<iterator_t<R>, O> && indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*> constexpr ranges::remove_copy_result<borrowed_iterator_t<R>, O> ranges::remove_copy(R&& r, O result, const T& value, Proj proj = {}); template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred> requires indirectly_copyable<I, O> constexpr ranges::remove_copy_if_result<I, O> ranges::remove_copy_if(I first, S last, O result, Pred pred, Proj proj = {}); template<input_range R, weakly_incrementable O, class Proj = identity, indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> requires indirectly_copyable<iterator_t<R>, O> constexpr ranges::remove_copy_if_result<borrowed_iterator_t<R>, O> ranges::remove_copy_if(R&& r, O result, Pred pred, Proj proj = {});
8
#
Let E be
  • (8.1)
    bool(*i == value) for remove_copy;
  • (8.2)
    bool(pred(*i)) for remove_copy_if;
  • (8.3)
    bool(invoke(proj, *i) == value) for ranges​::​remove_copy;
  • (8.4)
    bool(invoke(pred, invoke(proj, *i))) for ranges​::​remove_copy_if.
9
#
Let N be the number of elements in [first, last) for which E is false.
10
#
Mandates: *first is writable ([iterator.requirements.general]) to result.
11
#
Preconditions: The ranges [first, last) and [result, result + (last - first)) do not overlap.
[Note 2: 
For the overloads with an ExecutionPolicy, there might be a performance cost if iterator_traits<ForwardIterator1>​::​value_type does not meet the Cpp17MoveConstructible (Table 31) requirements.
— end note]
12
#
Effects: Copies all the elements referred to by the iterator i in the range [first, last) for which E is false.
13
#
Returns:
  • (13.1)
    result + N, for the algorithms in namespace std.
  • (13.2)
    {last, result + N}, for the algorithms in namespace ranges.
14
#
Complexity: Exactly last - first applications of the corresponding predicate and any projection.
15
#
Remarks: Stable ([algorithm.stable]).

27.7.9 Unique [alg.unique]

🔗
template<class ForwardIterator> constexpr ForwardIterator unique(ForwardIterator first, ForwardIterator last); template<class ExecutionPolicy, class ForwardIterator> ForwardIterator unique(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last); template<class ForwardIterator, class BinaryPredicate> constexpr ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred); template<class ExecutionPolicy, class ForwardIterator, class BinaryPredicate> ForwardIterator unique(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, BinaryPredicate pred); template<permutable I, sentinel_for<I> S, class Proj = identity, indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to> constexpr subrange<I> ranges::unique(I first, S last, C comp = {}, Proj proj = {}); template<forward_range R, class Proj = identity, indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to> requires permutable<iterator_t<R>> constexpr borrowed_subrange_t<R> ranges::unique(R&& r, C comp = {}, Proj proj = {});
1
#
Let pred be equal_to{} for the overloads with no parameter pred, and let E be
  • (1.1)
    bool(pred(*(i - 1), *i)) for the overloads in namespace std;
  • (1.2)
    bool(invoke(comp, invoke(proj, *(i - 1)), invoke(proj, *i))) for the overloads in namespace ranges.
2
#
Preconditions: For the overloads in namespace std, pred is an equivalence relation and the type of *first meets the Cpp17MoveAssignable requirements (Table 33).
3
#
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 E is true.
4
#
Returns: Let j be the end of the resulting range.
Returns:
  • (4.1)
    j for the overloads in namespace std.
  • (4.2)
    {j, last} for the overloads in namespace ranges.
5
#
Complexity: For nonempty ranges, exactly (last - first) - 1 applications of the corresponding predicate and no more than twice as many applications of any projection.
🔗
template<class InputIterator, class OutputIterator> constexpr OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> ForwardIterator2 unique_copy(ExecutionPolicy&& exec, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result); template<class InputIterator, class OutputIterator, class BinaryPredicate> constexpr OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator2 unique_copy(ExecutionPolicy&& exec, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result, BinaryPredicate pred); template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class Proj = identity, indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to> requires indirectly_copyable<I, O> && (forward_iterator<I> || (input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>) || indirectly_copyable_storable<I, O>) constexpr ranges::unique_copy_result<I, O> ranges::unique_copy(I first, S last, O result, C comp = {}, Proj proj = {}); template<input_range R, weakly_incrementable O, class Proj = identity, indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to> requires indirectly_copyable<iterator_t<R>, O> && (forward_iterator<iterator_t<R>> || (input_iterator<O> && same_as<range_value_t<R>, iter_value_t<O>>) || indirectly_copyable_storable<iterator_t<R>, O>) constexpr ranges::unique_copy_result<borrowed_iterator_t<R>, O> ranges::unique_copy(R&& r, O result, C comp = {}, Proj proj = {});
6
#
Let pred be equal_to{} for the overloads in namespace std with no parameter pred, and let E be
  • (6.1)
    bool(pred(*i, *(i - 1))) for the overloads in namespace std;
  • (6.2)
    bool(invoke(comp, invoke(proj, *i), invoke(proj, *(i - 1)))) for the overloads in namespace ranges.
7
#
Mandates: *first is writable ([iterator.requirements.general]) to result.
8
#
Preconditions:
  • (8.1)
    The ranges [first, last) and [result, result+(last-first)) do not overlap.
  • (8.2)
    For the overloads in namespace std:
    • (8.2.1)
      The comparison function is an equivalence relation.
    • (8.2.2)
      For the overloads with no ExecutionPolicy, let T be the value type of InputIterator.
      If InputIterator models forward_iterator ([iterator.concept.forward]), then there are no additional requirements for T.
      Otherwise, if OutputIterator meets the Cpp17ForwardIterator requirements and its value type is the same as T, then T meets the Cpp17CopyAssignable (Table 34) requirements.
      Otherwise, T meets both the Cpp17CopyConstructible (Table 32) and Cpp17CopyAssignable requirements.
      [Note 1: 
      For the overloads with an ExecutionPolicy, there might be a performance cost if the value type of ForwardIterator1 does not meet both the Cpp17CopyConstructible and Cpp17CopyAssignable requirements.
      — end note]
9
#
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 E holds.
10
#
Returns:
  • (10.1)
    result + N for the overloads in namespace std.
  • (10.2)
    {last, result + N} for the overloads in namespace ranges.
11
#
Complexity: Exactly last - first - 1 applications of the corresponding predicate and no more than twice as many applications of any projection.

27.7.10 Reverse [alg.reverse]

🔗
template<class BidirectionalIterator> constexpr void reverse(BidirectionalIterator first, BidirectionalIterator last); template<class ExecutionPolicy, class BidirectionalIterator> void reverse(ExecutionPolicy&& exec, BidirectionalIterator first, BidirectionalIterator last); template<bidirectional_iterator I, sentinel_for<I> S> requires permutable<I> constexpr I ranges::reverse(I first, S last); template<bidirectional_range R> requires permutable<iterator_t<R>> constexpr borrowed_iterator_t<R> ranges::reverse(R&& r);
1
#
Preconditions: For the overloads in namespace std, BidirectionalIterator meets the Cpp17ValueSwappable requirements ([swappable.requirements]).
2
#
Effects: For each non-negative integer i < (last - first) / 2, applies std​::​iter_swap, or ranges​::​​iter_swap for the overloads in namespace ranges, to all pairs of iterators first + i, (last - i) - 1.
3
#
Returns: last for the overloads in namespace ranges.
4
#
Complexity: Exactly (last - first)/2 swaps.
🔗
template<class BidirectionalIterator, class OutputIterator> constexpr OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result); template<class ExecutionPolicy, class BidirectionalIterator, class ForwardIterator> ForwardIterator reverse_copy(ExecutionPolicy&& exec, BidirectionalIterator first, BidirectionalIterator last, ForwardIterator result); template<bidirectional_iterator I, sentinel_for<I> S, weakly_incrementable O> requires indirectly_copyable<I, O> constexpr ranges::reverse_copy_result<I, O> ranges::reverse_copy(I first, S last, O result); template<bidirectional_range R, weakly_incrementable O> requires indirectly_copyable<iterator_t<R>, O> constexpr ranges::reverse_copy_result<borrowed_iterator_t<R>, O> ranges::reverse_copy(R&& r, O result);
5
#
Let N be last - first.
6
#
Preconditions: The ranges [first, last) and [result, result + N) do not overlap.
7
#
Effects: Copies the range [first, last) to the range [result, result + N) such that for every non-negative integer i < N the following assignment takes place: *(result + N - 1 - i) = *(first + i).
8
#
Returns:
  • (8.1)
    result + N for the overloads in namespace std.
  • (8.2)
    {last, result + N} for the overloads in namespace ranges.
9
#
Complexity: Exactly N assignments.

27.7.11 Rotate [alg.rotate]

🔗
template<class ForwardIterator> constexpr ForwardIterator rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last); template<class ExecutionPolicy, class ForwardIterator> ForwardIterator rotate(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator middle, ForwardIterator last); template<permutable I, sentinel_for<I> S> constexpr subrange<I> ranges::rotate(I first, I middle, S last);
1
#
Preconditions: [first, middle) and [middle, last) are valid ranges.
For the overloads in namespace std, ForwardIterator meets the Cpp17ValueSwappable requirements ([swappable.requirements]), and the type of *first meets the Cpp17MoveConstructible (Table 31) and Cpp17MoveAssignable (Table 33) requirements.
2
#
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).
[Note 1: 
This is a left rotate.
— end note]
3
#
Returns:
  • (3.1)
    first + (last - middle) for the overloads in namespace std.
  • (3.2)
    {first + (last - middle), last} for the overload in namespace ranges.
4
#
Complexity: At most last - first swaps.
🔗
template<forward_range R> requires permutable<iterator_t<R>> constexpr borrowed_subrange_t<R> ranges::rotate(R&& r, iterator_t<R> middle);
5
#
Effects: Equivalent to: return ranges​::​rotate(ranges​::​begin(r), middle, ranges​::​end(r));
🔗
template<class ForwardIterator, class OutputIterator> constexpr OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> ForwardIterator2 rotate_copy(ExecutionPolicy&& exec, ForwardIterator1 first, ForwardIterator1 middle, ForwardIterator1 last, ForwardIterator2 result); template<forward_iterator I, sentinel_for<I> S, weakly_incrementable O> requires indirectly_copyable<I, O> constexpr ranges::rotate_copy_result<I, O> ranges::rotate_copy(I first, I middle, S last, O result);
6
#
Let N be last - first.
7
#
Preconditions: [first, middle) and [middle, last) are valid ranges.
The ranges [first, last) and [result, result + N) do not overlap.
8
#
Effects: Copies the range [first, last) to the range [result, result + N) such that for each non-negative integer the following assignment takes place: *(result + i) = *(first + (i + (middle - first)) % N).
9
#
Returns:
  • (9.1)
    result + N for the overloads in namespace std.
  • (9.2)
    {last, result + N} for the overload in namespace ranges.
10
#
Complexity: Exactly N assignments.
🔗
template<forward_range R, weakly_incrementable O> requires indirectly_copyable<iterator_t<R>, O> constexpr ranges::rotate_copy_result<borrowed_iterator_t<R>, O> ranges::rotate_copy(R&& r, iterator_t<R> middle, O result);
11
#
Effects: Equivalent to: return ranges::rotate_copy(ranges::begin(r), middle, ranges::end(r), std::move(result));

27.7.12 Sample [alg.random.sample]

🔗
template<class PopulationIterator, class SampleIterator, class Distance, class UniformRandomBitGenerator> SampleIterator sample(PopulationIterator first, PopulationIterator last, SampleIterator out, Distance n, UniformRandomBitGenerator&& g); template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class Gen> requires (forward_iterator<I> || random_access_iterator<O>) && indirectly_copyable<I, O> && uniform_random_bit_generator<remove_reference_t<Gen>> O ranges::sample(I first, S last, O out, iter_difference_t<I> n, Gen&& g); template<input_range R, weakly_incrementable O, class Gen> requires (forward_range<R> || random_access_iterator<O>) && indirectly_copyable<iterator_t<R>, O> && uniform_random_bit_generator<remove_reference_t<Gen>> O ranges::sample(R&& r, O out, range_difference_t<R> n, Gen&& g);
1
#
Mandates: For the overload in namespace std, Distance is an integer type and *first is writable ([iterator.requirements.general]) to out.
2
#
Preconditions: out is not in the range [first, last).
For the overload in namespace std:
3
#
Effects: Copies min(last - first,  n) elements (the sample) from [first, last) (the population) to out such that each possible sample has equal probability of appearance.
[Note 1: 
Algorithms that obtain such effects include selection sampling and reservoir sampling.
— end note]
4
#
Returns: The end of the resulting sample range.
5
#
Complexity: .
6
#
Remarks:
  • (6.1)
    For the overload in namespace std, stable if and only if PopulationIterator models forward_iterator.
    For the first overload in namespace ranges, stable if and only if I models forward_iterator.
  • (6.2)
    To the extent that the implementation of this function makes use of random numbers, the object g serves as the implementation's source of randomness.

27.7.13 Shuffle [alg.random.shuffle]

🔗
template<class RandomAccessIterator, class UniformRandomBitGenerator> void shuffle(RandomAccessIterator first, RandomAccessIterator last, UniformRandomBitGenerator&& g); template<random_access_iterator I, sentinel_for<I> S, class Gen> requires permutable<I> && uniform_random_bit_generator<remove_reference_t<Gen>> I ranges::shuffle(I first, S last, Gen&& g); template<random_access_range R, class Gen> requires permutable<iterator_t<R>> && uniform_random_bit_generator<remove_reference_t<Gen>> borrowed_iterator_t<R> ranges::shuffle(R&& r, Gen&& g);
1
#
Preconditions: For the overload in namespace std:
2
#
Effects: Permutes the elements in the range [first, last) such that each possible permutation of those elements has equal probability of appearance.
3
#
Returns: last for the overloads in namespace ranges.
4
#
Complexity: Exactly (last - first) - 1 swaps.
5
#
Remarks: To the extent that the implementation of this function makes use of random numbers, the object referenced by g shall serve as the implementation's source of randomness.

27.7.14 Shift [alg.shift]

🔗
template<class ForwardIterator> constexpr ForwardIterator shift_left(ForwardIterator first, ForwardIterator last, typename iterator_traits<ForwardIterator>::difference_type n); template<class ExecutionPolicy, class ForwardIterator> ForwardIterator shift_left(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, typename iterator_traits<ForwardIterator>::difference_type n); template<permutable I, sentinel_for<I> S> constexpr subrange<I> ranges::shift_left(I first, S last, iter_difference_t<I> n); template<forward_range R> requires permutable<iterator_t<R>> constexpr borrowed_subrange_t<R> ranges::shift_left(R&& r, range_difference_t<R> n)
1
#
Preconditions: n >= 0 is true.
For the overloads in namespace std, the type of *first meets the Cpp17MoveAssignable requirements.
2
#
Effects: If n == 0 or n >= last - first, does nothing.
Otherwise, moves the element from position first + n + i into position first + i for each non-negative integer i < (last - first) - n.
For the overloads without an ExecutionPolicy template parameter, does so in order starting from i = 0 and proceeding to i = (last - first) - n - 1.
3
#
Returns: Let NEW_LAST be first + (last - first - n) if n < last - first, otherwise first.
  • (3.1)
    NEW_LAST for the overloads in namespace std.
  • (3.2)
    {first, NEW_LAST} for the overloads in namespace ranges.
4
#
Complexity: At most (last - first) - n assignments.
🔗
template<class ForwardIterator> constexpr ForwardIterator shift_right(ForwardIterator first, ForwardIterator last, typename iterator_traits<ForwardIterator>::difference_type n); template<class ExecutionPolicy, class ForwardIterator> ForwardIterator shift_right(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, typename iterator_traits<ForwardIterator>::difference_type n); template<permutable I, sentinel_for<I> S> constexpr subrange<I> ranges::shift_right(I first, S last, iter_difference_t<I> n); template<forward_range R> requires permutable<iterator_t<R>> constexpr borrowed_subrange_t<R> ranges::shift_right(R&& r, range_difference_t<R> n);
5
#
Preconditions: n >= 0 is true.
For the overloads in namespace std, the type of *first meets the Cpp17MoveAssignable requirements, and ForwardIterator meets the Cpp17BidirectionalIterator requirements ([bidirectional.iterators]) or the Cpp17ValueSwappable requirements.
6
#
Effects: If n == 0 or n >= last - first, does nothing.
Otherwise, moves the element from position first + i into position first + n + i for each non-negative integer i < (last - first) - n.
Does so in order starting from i = (last - first) - n - 1 and proceeding to i = 0 if:
  • (6.1)
    for the overload in namespace std without an ExecutionPolicy template parameter, ForwardIterator meets the Cpp17BidirectionalIterator requirements,
  • (6.2)
    for the overloads in namespace ranges, I models bidirectional_iterator.
7
#
Returns: Let NEW_FIRST be first + n if n < last - first, otherwise last.
  • (7.1)
    NEW_FIRST for the overloads in namespace std.
  • (7.2)
    {NEW_FIRST, last} for the overloads in namespace ranges.
8
#
Complexity: At most (last - first) - n assignments or swaps.