25 Algorithms library [algorithms]

25.7 Mutating sequence operations [alg.modifying.operations]

25.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 .
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
:
For the overload with an ExecutionPolicy, there may be a performance cost if iterator_­traits<ForwardIterator1>​::​value_­type is not Cpp17MoveConstructible (Table 28).
— 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.231
For each positive integer , 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.
231)
copy_­backward should be used instead of copy when last is in the range [result - N, result).
⮥

25.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.232
For each positive integer , 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.
232)
move_­backward should be used instead of move when last is in the range [result - N, result).
⮥

25.7.3 Swap [alg.swap]

🔗
template<class ForwardIterator1, class ForwardIterator2> constexpr ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); 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 .
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).

25.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 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.
233)
The use of fully closed ranges is intentional.
⮥

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

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

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

25.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 30).
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
#
Remarks: Stable ([algorithm.stable]).
6
#
Complexity: Exactly last - first applications of the corresponding predicate and any projection.
7
#
[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.
— 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
:
For the overloads with an ExecutionPolicy, there may be a performance cost if iterator_­traits<ForwardIterator1>​::​value_­type does not meet the Cpp17MoveConstructible (Table 28) 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]).

25.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 namepace std, pred is an equivalence relation and the type of *first meets the Cpp17MoveAssignable requirements (Table 30).
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 meets the Cpp17ForwardIterator requirements, 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 31) requirements. Otherwise, T meets both the Cpp17CopyConstructible (Table 29) and Cpp17CopyAssignable requirements.
      [Note
      : For the overloads with an ExecutionPolicy, there may 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.

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

25.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 28) and Cpp17MoveAssignable (Table 30) 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
:
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), result);

25.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 elements (the sample) from [first, last) (the population) to out such that each possible sample has equal probability of appearance.
[Note
:
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 meets the Cpp17ForwardIterator requirements. 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.

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

25.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);
1
#
Preconditions: n >= 0 is true.
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.
In the first overload case, does so in order starting from i = 0 and proceeding to i = (last - first) - n - 1.
3
#
Returns: first + (last - first - n) if n < last - first, otherwise first.
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);
5
#
Preconditions: n >= 0 is true.
The type of *first meets the Cpp17MoveAssignable requirements.
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.
In the first overload case, if ForwardIterator meets the Cpp17BidirectionalIterator requirements, does so in order starting from i = (last - first) - n - 1 and proceeding to i = 0.
7
#
Returns: first + n if n < last - first, otherwise last.
8
#
Complexity: At most (last - first) - n assignments or swaps.