28 Algorithms library [algorithms]

28.6 Mutating sequence operations [alg.modifying.operations]

28.6.1 Copy [alg.copy]

🔗
template<class InputIterator, class OutputIterator> OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result);
1
#
Requires: result shall not be in the range [first, last).
2
#
Effects: Copies elements in the range [first, last) into the range [result, result + (last - first)) starting from first and proceeding to last.
For each non-negative integer n < (last - first), performs *(result + n) = *(first + n).
3
#
Returns: result + (last - first).
4
#
Complexity: Exactly last - first assignments.
🔗
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> ForwardIterator2 copy(ExecutionPolicy&& policy, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result);
5
#
Requires: The ranges [first, last) and [result, result + (last - first)) shall not overlap.
6
#
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).
7
#
Returns: result + (last - first).
8
#
Complexity: Exactly last - first assignments.
🔗
template<class InputIterator, class Size, class OutputIterator> 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);
9
#
Effects: For each non-negative integer , performs *(result + i) = *(first + i).
10
#
Returns: result + n.
11
#
Complexity: Exactly n assignments.
🔗
template<class InputIterator, class OutputIterator, class Predicate> 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);
12
#
Requires: The ranges [first, last) and [result, result + (last - first)) shall not overlap.
[ Note
:
For the overload with an ExecutionPolicy, there may be a performance cost if iterator_­traits<ForwardIterator1>​::​value_­type is not MoveConstructible (Table 23).
— end note
 ]
13
#
Effects: Copies all of the elements referred to by the iterator i in the range [first, last) for which pred(*i) is true.
14
#
Returns: The end of the resulting range.
15
#
Complexity: Exactly last - first applications of the corresponding predicate.
16
#
Remarks: Stable ([algorithm.stable]).
🔗
template<class BidirectionalIterator1, class BidirectionalIterator2> BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result);
17
#
Requires: result shall not be in the range (first, last].
18
#
Effects: Copies elements in the range [first, last) into the range [result - (last-first), result) starting from last - 1 and proceeding to first.263
For each positive integer n <= (last - first), performs *(result - n) = *(last - n).
19
#
Returns: result - (last - first).
20
#
Complexity: Exactly last - first assignments.
263)
copy_­backward should be used instead of copy when last is in the range [result - (last - first), result).

28.6.2 Move [alg.move]

🔗
template<class InputIterator, class OutputIterator> OutputIterator move(InputIterator first, InputIterator last, OutputIterator result);
1
#
Requires: result shall not be in the range [first, last).
2
#
Effects: Moves elements in the range [first, last) into the range [result, result + (last - first)) starting from first and proceeding to last.
For each non-negative integer n < (last-first), performs *(result + n) = std​::​move(*(first + n)).
3
#
Returns: result + (last - first).
4
#
Complexity: Exactly last - first move assignments.
🔗
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> ForwardIterator2 move(ExecutionPolicy&& policy, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result);
5
#
Requires: The ranges [first, last) and [result, result + (last - first)) shall not overlap.
6
#
Effects: Moves elements in the range [first, last) into the range [result, result + (last - first)).
For each non-negative integer n < (last - first), performs *(result + n) = std​::​​move(*(first + n)).
7
#
Returns: result + (last - first).
8
#
Complexity: Exactly last - first assignments.
🔗
template<class BidirectionalIterator1, class BidirectionalIterator2> BidirectionalIterator2 move_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result);
9
#
Requires: result shall not be in the range (first, last].
10
#
Effects: Moves elements in the range [first, last) into the range [result - (last-first), result) starting from last - 1 and proceeding to first.264
For each positive integer n <= (last - first), performs *(result - n) = std​::​move(*(last - n)).
11
#
Returns: result - (last - first).
12
#
Complexity: Exactly last - first assignments.
264)
move_­backward should be used instead of move when last is in the range [result - (last - first), result).

28.6.3 Swap [alg.swap]

🔗
template<class ForwardIterator1, class ForwardIterator2> 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);
1
#
Requires: The two ranges [first1, last1) and [first2, first2 + (last1 - first1)) shall not overlap.
*(first1 + n) shall be swappable with ([swappable.requirements]) *(first2 + n).
2
#
Effects: For each non-negative integer n < (last1 - first1) performs: swap(*(first1 + n), ​*(first2 + n)).
3
#
Returns: first2 + (last1 - first1).
4
#
Complexity: Exactly last1 - first1 swaps.
🔗
template<class ForwardIterator1, class ForwardIterator2> void iter_swap(ForwardIterator1 a, ForwardIterator2 b);
5
#
Requires: a and b shall be dereferenceable.
*a shall be swappable with ([swappable.requirements]) *b.
6
#
Effects: As if by swap(*a, *b).

28.6.4 Transform [alg.transform]

🔗
template<class InputIterator, class OutputIterator, class UnaryOperation> OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class UnaryOperation> ForwardIterator2 transform(ExecutionPolicy&& exec, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result, UnaryOperation op); template<class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation> 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);
1
#
Requires: op and binary_­op shall not invalidate iterators or subranges, or modify elements in the ranges
  • (1.1)
    [first1, last1],
  • (1.2)
    [first2, first2 + (last1 - first1)], and
  • (1.3)
    [result, result + (last1 - first1)].265
2
#
Effects: Assigns through every iterator i in the range [result, result + (last1 - first1)) a new corresponding value equal to op(*(first1 + (i - result))) or binary_­op(*(first1 + (i - result)), *(first2 + (i - result))).
3
#
Returns: result + (last1 - first1).
4
#
Complexity: Exactly last1 - first1 applications of op or binary_­op.
This requirement also applies to the overload with an ExecutionPolicy .
5
#
Remarks: result may be equal to first in case of unary transform, or to first1 or first2 in case of binary transform.
265)
The use of fully closed ranges is intentional.

28.6.5 Replace [alg.replace]

🔗
template<class ForwardIterator, class T> 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> 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);
1
#
Requires: The expression *first = new_­value shall be valid.
2
#
Effects: Substitutes elements referred by the iterator i in the range [first, last) with new_­value, when the following corresponding conditions hold: *i == old_­value, pred(*i) != false.
3
#
Complexity: Exactly last - first applications of the corresponding predicate.
🔗
template<class InputIterator, class OutputIterator, class T> 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> 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);
4
#
Requires: The results of the expressions *first and new_­value shall be writable ([iterator.requirements.general]) to the result output iterator.
The ranges [first, last) and [result, result + (last - first)) shall not overlap.
5
#
Effects: Assigns to every iterator i in the range [result, result + (last - first)) either new_­value or *​(first + (i - result)) depending on whether the following corresponding conditions hold:
*(first + (i - result)) == old_value
pred(*(first + (i - result))) != false
6
#
Returns: result + (last - first).
7
#
Complexity: Exactly last - first applications of the corresponding predicate.

28.6.6 Fill [alg.fill]

🔗
template<class ForwardIterator, class T> 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> 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);
1
#
Requires: The expression value shall be writable ([iterator.requirements.general]) to the output iterator.
The type Size shall be convertible to an integral type ([conv.integral], [class.conv]).
2
#
Effects: The fill algorithms assign value through all the iterators in the range [first, last).
The fill_­n algorithms assign value through all the iterators in the range [first, first + n) if n is positive, otherwise they do nothing.
3
#
Returns: fill_­n returns first + n for non-negative values of n and first for negative values.
4
#
Complexity: Exactly last - first, n, or 0 assignments, respectively.

28.6.7 Generate [alg.generate]

🔗
template<class ForwardIterator, class Generator> 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> 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);
1
#
Requires: gen takes no arguments, Size shall be convertible to an integral type ([conv.integral], [class.conv]).
2
#
Effects: The generate algorithms invoke the function object gen and assign the return value of gen through all the iterators in the range [first, last).
The generate_­n algorithms invoke the function object gen and assign the return value of gen through all the iterators in the range [first, first + n) if n is positive, otherwise they do nothing.
3
#
Returns: generate_­n returns first + n for non-negative values of n and first for negative values.
4
#
Complexity: Exactly last - first, n, or 0 invocations of gen and assignments, respectively.

28.6.8 Remove [alg.remove]

🔗
template<class ForwardIterator, class T> 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> 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);
1
#
Requires: The type of *first shall satisfy the MoveAssignable requirements (Table 25).
2
#
Effects: Eliminates all the elements referred to by iterator i in the range [first, last) for which the following corresponding conditions hold: *i == value, pred(*i) != false.
3
#
Returns: The end of the resulting range.
4
#
Remarks: Stable ([algorithm.stable]).
5
#
Complexity: Exactly last - first applications of the corresponding predicate.
6
#
[ 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> 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> 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);
7
#
Requires: The ranges [first, last) and [result, result + (last - first)) shall not overlap.
The expression *result = *first shall be valid.
[ Note
:
For the overloads with an ExecutionPolicy, there may be a performance cost if iterator_­traits<ForwardIterator1>​::​value_­type is not MoveConstructible (Table 23).
— end note
 ]
8
#
Effects: Copies all the elements referred to by the iterator i in the range [first, last) for which the following corresponding conditions do not hold: *i == value, pred(*i) != false.
9
#
Returns: The end of the resulting range.
10
#
Complexity: Exactly last - first applications of the corresponding predicate.
11
#
Remarks: Stable ([algorithm.stable]).

28.6.9 Unique [alg.unique]

🔗
template<class ForwardIterator> ForwardIterator unique(ForwardIterator first, ForwardIterator last); template<class ExecutionPolicy, class ForwardIterator> ForwardIterator unique(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last); template<class ForwardIterator, class BinaryPredicate> 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);
1
#
Requires: The comparison function shall be an equivalence relation.
The type of *first shall satisfy the MoveAssignable requirements (Table 25).
2
#
Effects: For a nonempty range, eliminates all but the first element from every consecutive group of equivalent elements referred to by the iterator i in the range [first + 1, last) for which the following conditions hold: *(i - 1) == *i or pred(*(i - 1), *i) != false.
3
#
Returns: The end of the resulting range.
4
#
Complexity: For nonempty ranges, exactly (last - first) - 1 applications of the corresponding predicate.
🔗
template<class InputIterator, class OutputIterator> 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> 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);
5
#
Requires:
  • (5.1)
    The comparison function shall be an equivalence relation.
  • (5.2)
    The ranges [first, last) and [result, result+(last-first)) shall not overlap.
  • (5.3)
    The expression *result = *first shall be valid.
  • (5.4)
    For the overloads with no ExecutionPolicy, let T be the value type of InputIterator.
    If InputIterator meets the forward iterator requirements, then there are no additional requirements for T.
    Otherwise, if OutputIterator meets the forward iterator requirements and its value type is the same as T, then T shall be CopyAssignable (Table 26).
    Otherwise, T shall be both CopyConstructible (Table 24) and CopyAssignable.
    [ Note
    :
    For the overloads with an ExecutionPolicy, there may be a performance cost if the value type of ForwardIterator1 is not both CopyConstructible and CopyAssignable.
    — end note
     ]
6
#
Effects: Copies only the first element from every consecutive group of equal elements referred to by the iterator i in the range [first, last) for which the following corresponding conditions hold: *i == *(i - 1) or pred(*i, *(i - 1)) != false.
7
#
Returns: The end of the resulting range.
8
#
Complexity: For nonempty ranges, exactly last - first - 1 applications of the corresponding predicate.

28.6.10 Reverse [alg.reverse]

🔗
template<class BidirectionalIterator> void reverse(BidirectionalIterator first, BidirectionalIterator last); template<class ExecutionPolicy, class BidirectionalIterator> void reverse(ExecutionPolicy&& exec, BidirectionalIterator first, BidirectionalIterator last);
1
#
Requires: *first shall be swappable ([swappable.requirements]).
2
#
Effects: For each non-negative integer i < (last - first) / 2, applies iter_­swap to all pairs of iterators first + i, (last - i) - 1.
3
#
Requires: BidirectionalIterator shall satisfy the requirements of ValueSwappable ([swappable.requirements]).
4
#
Complexity: Exactly (last - first)/2 swaps.
🔗
template<class BidirectionalIterator, class OutputIterator> 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);
5
#
Requires: The ranges [first, last) and [result, result + (last - first)) shall not overlap.
6
#
Effects: Copies the range [first, last) to the range [result, result + (last - first)) such that for every non-negative integer i < (last - first) the following assignment takes place: *(result + (last - first) - 1 - i) = *(first + i).
7
#
Returns: result + (last - first).
8
#
Complexity: Exactly last - first assignments.

28.6.11 Rotate [alg.rotate]

🔗
template<class ForwardIterator> ForwardIterator rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last); template<class ExecutionPolicy, class ForwardIterator> ForwardIterator rotate(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator middle, ForwardIterator last);
1
#
Requires: [first, middle) and [middle, last) shall be valid ranges.
ForwardIterator shall satisfy the requirements of ValueSwappable ([swappable.requirements]).
The type of *first shall satisfy the requirements of MoveConstructible (Table 23) and the requirements of MoveAssignable (Table 25).
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).
3
#
Returns: first + (last - middle).
4
#
Remarks: This is a left rotate.
5
#
Complexity: At most last - first swaps.
🔗
template<class ForwardIterator, class OutputIterator> 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);
6
#
Requires: The ranges [first, last) and [result, result + (last - first)) shall not overlap.
7
#
Effects: Copies the range [first, last) to the range [result, result + (last - first)) such that for each non-negative integer i < (last - first) the following assignment takes place: *(result + i) = *(first + (i + (middle - first)) % (last - first)).
8
#
Returns: result + (last - first).
9
#
Complexity: Exactly last - first assignments.

28.6.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);
1
#
Requires:
2
#
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
:
Algorithms that obtain such effects include selection sampling and reservoir sampling.
— end note
 ]
3
#
Returns: The end of the resulting sample range.
4
#
Complexity: .
5
#
Remarks:
  • (5.1)
    Stable if and only if PopulationIterator satisfies the requirements of a forward iterator.
  • (5.2)
    To the extent that the implementation of this function makes use of random numbers, the object g shall serve as the implementation's source of randomness.

28.6.13 Shuffle [alg.random.shuffle]

🔗
template<class RandomAccessIterator, class UniformRandomBitGenerator> void shuffle(RandomAccessIterator first, RandomAccessIterator last, UniformRandomBitGenerator&& g);
1
#
Requires: RandomAccessIterator shall satisfy the requirements of ValueSwappable ([swappable.requirements]).
The type remove_­reference_­t<UniformRandomBitGenerator> shall meet the requirements of a uniform random bit generator ([rand.req.urng]) type whose return type is convertible to iterator_­traits<RandomAccessIterator>​::​difference_­type.
2
#
Effects: Permutes the elements in the range [first, last) such that each possible permutation of those elements has equal probability of appearance.
3
#
Complexity: Exactly (last - first) - 1 swaps.
4
#
Remarks: To the extent that the implementation of this function makes use of random numbers, the object g shall serve as the implementation's source of randomness.