# 25 Algorithms library [algorithms]

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

### 25.3.1 Copy [alg.copy]

``` template<class InputIterator, class OutputIterator> OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result); ```

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

Returns: result + (last - first).

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

Complexity: Exactly last - first assignments.

``` template<class InputIterator, class Size, class OutputIterator> OutputIterator copy_n(InputIterator first, Size n, OutputIterator result); ```

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

Returns: result + n.

Complexity: Exactly n assignments.

``` template<class InputIterator, class OutputIterator, class Predicate> OutputIterator copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred); ```

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

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

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

Remarks: Stable.

``` template<class BidirectionalIterator1, class BidirectionalIterator2> BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result); ```

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

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

Returns: result - (last - first).

Complexity: Exactly last - first assignments.

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

### 25.3.2 Move [alg.move]

``` template<class InputIterator, class OutputIterator> OutputIterator move(InputIterator first, InputIterator last, OutputIterator result); ```

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

Returns: result + (last - first).

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

Complexity: Exactly last - first move assignments.

``` template<class BidirectionalIterator1, class BidirectionalIterator2> BidirectionalIterator2 move_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result); ```

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

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

Returns: result - (last - first).

Complexity: Exactly last - first assignments.

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

### 25.3.3 swap [alg.swap]

``` template<class ForwardIterator1, class ForwardIterator2> ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); ```

Effects: For each non-negative integer n < (last1 - first1) performs: swap(*(first1 + n), *(first2 + n)).

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

Returns: first2 + (last1 - first1).

Complexity: Exactly last1 - first1 swaps.

``` template<class ForwardIterator1, class ForwardIterator2> void iter_swap(ForwardIterator1 a, ForwardIterator2 b); ```

Effects: swap(*a, *b).

Requires: a and b shall be dereferenceable. *a shall be swappable with ([swappable.requirements]) *b.

### 25.3.4 Transform [alg.transform]

``` template<class InputIterator, class OutputIterator, class UnaryOperation> OutputIterator transform(InputIterator first, InputIterator last, OutputIterator 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); ```

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

Requires: op and binary_op shall not invalidate iterators or subranges, or modify elements in the ranges [first1,last1], [first2,first2 + (last1 - first1)], and [result,result + (last1 - first1)].272

Returns: result + (last1 - first1).

Complexity: Exactly last1 - first1 applications of op or binary_op.

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

The use of fully closed ranges is intentional.

### 25.3.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 ForwardIterator, class Predicate, class T> void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value); ```

Requires: The expression *first = new_value shall be valid.

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.

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 InputIterator, class OutputIterator, class Predicate, class T> OutputIterator replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value); ```

Requires: The results of the expressions *first and new_value shall be writable to the result output iterator. The ranges [first,last) and [result,result + (last - first)) shall not overlap.

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

```*(first + (i - result)) == old_value
pred(*(first + (i - result))) != false
```

Returns: result + (last - first).

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

### 25.3.6 Fill [alg.fill]

``` template<class ForwardIterator, class T> void fill(ForwardIterator first, ForwardIterator last, const T& value); template<class OutputIterator, class Size, class T> OutputIterator fill_n(OutputIterator first, Size n, const T& value); ```

Requires: The expression value shall be writable to the output iterator. The type Size shall be convertible to an integral type ([conv.integral], [class.conv]).

Effects: The first algorithm assigns value through all the iterators in the range [first,last). The second algorithm assigns value through all the iterators in the range [first,first + n) if n is positive, otherwise it does nothing.

Returns: fill_n returns first + n for non-negative values of n and first for negative values.

Complexity: Exactly last - first, n, or 0 assignments, respectively.

### 25.3.7 Generate [alg.generate]

``` template<class ForwardIterator, class Generator> void generate(ForwardIterator first, ForwardIterator last, Generator gen); template<class OutputIterator, class Size, class Generator> OutputIterator generate_n(OutputIterator first, Size n, Generator gen); ```

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

Requires: gen takes no arguments, Size shall be convertible to an integral type ([conv.integral], [class.conv]).

Returns: generate_n returns first + n for non-negative values of n and first for negative values.

Complexity: Exactly last - first, n, or 0 invocations of gen and assignments, respectively.

### 25.3.8 Remove [alg.remove]

``` template<class ForwardIterator, class T> ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value); template<class ForwardIterator, class Predicate> ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate pred); ```

Requires: The type of *first shall satisfy the MoveAssignable requirements (Table [moveassignable]).

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.

Returns: The end of the resulting range.

Remarks: Stable.

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

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 swapping with or moving from elements that were originally in that range.

``` template<class InputIterator, class OutputIterator, class T> OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value); template<class InputIterator, class OutputIterator, class Predicate> OutputIterator remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred); ```

Requires: The ranges [first,last) and [result,result + (last - first)) shall not overlap. The expression *result = *first shall ve valid.

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.

Returns: The end of the resulting range.

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

Remarks: Stable.

### 25.3.9 Unique [alg.unique]

``` template<class ForwardIterator> ForwardIterator unique(ForwardIterator first, ForwardIterator last); template<class ForwardIterator, class BinaryPredicate> ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred); ```

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.

Requires: The comparison function shall be an equivalence relation. The type of *first shall satisfy the MoveAssignable requirements (Table [moveassignable]).

Returns: The end of the resulting range.

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 InputIterator, class OutputIterator, class BinaryPredicate> OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred); ```

Requires: The comparison function shall be an equivalence relation. The ranges [first,last) and [result,result+(last-first)) shall not overlap. The expression *result = *first shall be valid. If neither InputIterator nor OutputIterator meets the requirements of forward iterator then the value type of InputIterator shall be CopyConstructible (Table [copyconstructible]) and CopyAssignable (Table [copyassignable]). Otherwise CopyConstructible is not required.

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.

Returns: The end of the resulting range.

Complexity: For nonempty ranges, exactly last - first - 1 applications of the corresponding predicate.

### 25.3.10 Reverse [alg.reverse]

``` template<class BidirectionalIterator> void reverse(BidirectionalIterator first, BidirectionalIterator last); ```

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

Requires: *first shall be swappable ([swappable.requirements]).

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

``` template<class BidirectionalIterator, class OutputIterator> OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result); ```

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

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

Returns: result + (last - first).

Complexity: Exactly last - first assignments.

### 25.3.11 Rotate [alg.rotate]

``` template<class ForwardIterator> ForwardIterator rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last); ```

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

Returns: first + (last - middle).

Remarks: This is a left rotate.

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 [moveconstructible]) and the requirements of MoveAssignable (Table [moveassignable]).

Complexity: At most last - first swaps.

``` template<class ForwardIterator, class OutputIterator> OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result); ```

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

Returns: result + (last - first).

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

Complexity: Exactly last - first assignments.

### 25.3.12 Random shuffle [alg.random.shuffle]

``` template<class RandomAccessIterator> void random_shuffle(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class RandomNumberGenerator> void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator&& rand); template<class RandomAccessIterator, class UniformRandomNumberGenerator> void shuffle(RandomAccessIterator first, RandomAccessIterator last, UniformRandomNumberGenerator&& g); ```

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

Requires: RandomAccessIterator shall satisfy the requirements of ValueSwappable ([swappable.requirements]). The random number generating function object rand shall have a return type that is convertible to iterator_traits<RandomAccessIterator>::difference_type, and the call rand(n) shall return a randomly chosen value in the interval [0,n), for n > 0 of type iterator_traits<RandomAccessIterator>::difference_type. The type UniformRandomNumberGenerator shall meet the requirements of a uniform random number generator ([rand.req.urng]) type whose return type is convertible to iterator_traits<RandomAccessIterator>::difference_type.

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

Remarks: To the extent that the implementation of these functions makes use of random numbers, the implementation shall use the following sources of randomness:

The underlying source of random numbers for the first form of the function is implementation-defined. An implementation may use the rand function from the standard C library.

In the second form of the function, the function object rand shall serve as the implementation's source of randomness.

In the third shuffle form of the function, the object g shall serve as the implementation's source of randomness.

### 25.3.13 Partitions [alg.partitions]

``` template <class InputIterator, class Predicate> bool is_partitioned(InputIterator first, InputIterator last, Predicate pred); ```

Requires: InputIterator's value type shall be convertible to Predicate's argument type.

Returns: true if [first,last) is empty or if [first,last) is partitioned by pred, i.e. if all elements that satisfy pred appear before those that do not.

Complexity: Linear. At most last - first applications of pred.

``` template<class ForwardIterator, class Predicate> ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred); ```

Effects: Places all the elements in the range [first,last) that satisfy pred before all the elements that do not satisfy it.

Returns: An iterator i such that for any iterator j in the range [first,i) pred(*j) != false, and for any iterator k in the range [i,last), pred(*k) == false.

Requires: ForwardIterator shall satisfy the requirements of ValueSwappable ([swappable.requirements]).

Complexity: If ForwardIterator meets the requirements for a BidirectionalIterator, at most (last - first) / 2 swaps are done; otherwise at most last - first swaps are done. Exactly last - first applications of the predicate are done.

``` template<class BidirectionalIterator, class Predicate> BidirectionalIterator stable_partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred); ```

Effects: Places all the elements in the range [first,last) that satisfy pred before all the elements that do not satisfy it.

Returns: An iterator i such that for any iterator j in the range [first,i), pred(*j) != false, and for any iterator k in the range [i,last), pred(*k) == false. The relative order of the elements in both groups is preserved.

Requires: BidirectionalIterator shall satisfy the requirements of ValueSwappable ([swappable.requirements]). The type of *first shall satisfy the requirements of MoveConstructible (Table [moveconstructible]) and of MoveAssignable (Table [moveassignable]).

Complexity: At most (last - first) * log(last - first) swaps, but only linear number of swaps if there is enough extra memory. Exactly last - first applications of the predicate.

``` template <class InputIterator, class OutputIterator1, class OutputIterator2, class Predicate> pair<OutputIterator1, OutputIterator2> partition_copy(InputIterator first, InputIterator last, OutputIterator1 out_true, OutputIterator2 out_false, Predicate pred); ```

Requires: InputIterator's value type shall be Assignable, and shall be writable to the out_true and out_false OutputIterators, and shall be convertible to Predicate's argument type. The input range shall not overlap with either of the output ranges.

Effects: For each iterator i in [first,last), copies *i to the output range beginning with out_true if pred(*i) is true, or to the output range beginning with out_false otherwise.

Returns: A pair p such that p.first is the end of the output range beginning at out_true and p.second is the end of the output range beginning at out_false.

Complexity: Exactly last - first applications of pred.

``` template<class ForwardIterator, class Predicate> ForwardIterator partition_point(ForwardIterator first, ForwardIterator last, Predicate pred); ```

Requires: ForwardIterator's value type shall be convertible to Predicate's argument type. [first,last) shall be partitioned by pred, i.e. all elements that satisfy pred shall appear before those that do not.

Returns: An iterator mid such that all_of(first, mid, pred) and none_of(mid, last, pred) are both true.

Complexity: Ο(log(last - first)) applications of pred.