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