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

Requires: result не должно быть в диапазоне [first, last).

Effects: Копирует элементы диапазона [first, last) в диапазон, [result, result + (last - first)) начиная с first и до last. Для каждого неотрицательного целого числа n < (last - first)выполняется *(result + n) = *(first + n).

Returns: result + (last - first).

Complexity: Собственно last - first задания.

template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> ForwardIterator2 copy(ExecutionPolicy&& policy, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result);

Requires: Диапазоны [first, last) и [result, result + (last - first)) не должны перекрываться.

Effects: Копирует элементы диапазона [first, last) в диапазон [result, result + (last - first)). Для каждого неотрицательного целого числа n < (last - first)выполняется *(result + n) = *(first + n).

Returns: result + (last - first).

Complexity: Собственно last - first задания.

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

Effects: Для каждого неотрицательного целого числа $i < n$ выполняется *(result + i) = *(first + i).

Returns: result + n.

Complexity: Собственно n задания.

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

Requires: Диапазоны [first, last) и [result, result + (last - first)) не должны перекрываться. [ Note: Для перегрузки с a ExecutionPolicyможет возникнуть снижение производительности, если iterator_traits<ForwardIterator1>::value_type это не так MoveConstructible (таблица 23). ] — end note

Effects: Копирует все элементы, на которые ссылается итератор, i в диапазоне, [first, last) для которого pred(*i) есть true.

Returns: Конец получившегося диапазона.

Complexity: Точно last - first применения соответствующего предиката.

Remarks: Stable.

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

Requires: result не должно быть в диапазоне (first, last].

Effects: Копирует элементы диапазона [first, last) в диапазон, [result - (last-first), result) начиная с last - 1 и до first.263 Для каждого положительного целого числа n <= (last - first)выполняется *(result - n) = *(last - n).

Returns: result - (last - first).

Complexity: Собственно last - first задания.

263)

copy_backward следует использовать вместо копирования, когда он last находится в диапазоне [result - (last - first), result).

28.6.2 Move [alg.move]

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

Requires: result не должно быть в диапазоне [first, last).

Effects: Перемещает элементы диапазона [first, last) в диапазон, [result, result + (last - first)) начиная с первого и заканчивая последним. Для каждого неотрицательного целого числа n < (last-first)выполняется *(result + n) = std::move(*(first + n)).

Returns: result + (last - first).

Complexity: Ровно last - first перемещайте задания.

template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> ForwardIterator2 move(ExecutionPolicy&& policy, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result);

Requires: Диапазоны [first, last) и [result, result + (last - first)) не должны перекрываться.

Effects: Перемещает элементы из диапазона [first, last) в диапазон [result, result + (last - first)). Для каждого неотрицательного целого числа n < (last - first)выполняется *(result + n) = std::move(*(first + n)).

Returns: result + (last - first).

Complexity: Собственно last - first задания.

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

Requires: result не должно быть в диапазоне (first, last].

Effects: Перемещает элементы в диапазоне [first, last) в диапазон, [result - (last-first), result) начиная с last - 1 первого и переходя к нему.264 Для каждого положительного целого числа n <= (last - first)выполняется *(result - n) = std::move(*(last - n)).

Returns: result - (last - first).

Complexity: Собственно last - first задания.

264)

move_backward следует использовать вместо move, когда последний находится в диапазоне [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);

Requires: Эти два диапазона , [first1, last1) и [first2, first2 + (last1 - first1)) не должны перекрывать. *(first1 + n) будет swappable with *(first2 + n).

Effects: Для каждого неотрицательных целого числа n < (last1 - first1) выполняет: swap(*(first1 + n), *(first2 + n)).

Returns: first2 + (last1 - first1).

Complexity: Ровно last1 - first1 свопы.

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

Requires: a и b должно быть разыменовано. *a будет swappable with *b.

Effects: Как будто мимо 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);

Requires: op и binary_op не должен аннулировать итераторы или поддиапазоны или изменять элементы в диапазонах

(1.1)
[first1, last1],
(1.2)
[first2, first2 + (last1 - first1)], а также
(1.3)
[result, result + (last1 - first1)].265

Effects: Назначает каждому итератору i в диапазоне [result, result + (last1 - first1)) новое соответствующее значение, равное op(*(first1 + (i - result))) или binary_op(*(first1 + (i - result)), *(first2 + (i - result))).

Returns: result + (last1 - first1).

Complexity: Собственно last1 - first1 приложения op или binary_op. Это требование также распространяется на перегрузку с расширением ExecutionPolicy .

Remarks: result может быть равно first в случае унарного преобразования, first1 или first2 в случае двоичного преобразования.

265)

Использование полностью замкнутых диапазонов является преднамеренным.

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

Requires: Выражение *first = new_value действительно.

Effects: Заменяет элементы, на которые ссылается итератор i в диапазоне [first, last) с new_value, при выполнении следующих соответствующих условий: *i == old_value, pred(*i) != false.

Complexity: Точно last - first применения соответствующего предиката.

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

Requires: Результаты выражений *first и new_value должны быть writable в result выходном итератор. Диапазоны [first, last) и [result, result + (last - first)) не должны перекрываться.

Effects: Присваивается каждому итератору i в диапазоне [result, result + (last - first)) либо, new_value либо в *(first + (i - result)) зависимости от того, выполняются ли следующие соответствующие условия:

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

Returns: result + (last - first).

Complexity: Точно last - first применения соответствующего предиката.

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

Requires: Выражение value должно быть writable передано итератору вывода. Тип Size должен быть преобразован в целочисленный тип ([conv.integral], [class.conv]).

Effects: Эти fill алгоритмы назначения value через все итераторы в диапазоне [first, last). Эти fill_n алгоритмы назначение value через все итераторы в диапазоне , [first, first + n) если n положительно, в противном случае они ничего не делают.

Returns: fill_n возвращает first + n для неотрицательных значений n и first для отрицательных значений.

Complexity: Ровно last - first, nили 0 присвоений соответственно.

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

Requires: gen не принимает аргументов, Size может быть преобразован в целочисленный тип ([conv.integral], [class.conv]).

Effects: Эти generate алгоритмы вызвать объект функции gen и присвоить возвращаемое значение gen через все итераторы в диапазоне [first, last). Эти generate_n алгоритмы вызов функции объекта gen и присвоить возвращаемое значение gen через все итераторы в диапазоне , [first, first + n) если n положительно, в противном случае они ничего не делают.

Returns: generate_n возвращает first + n для неотрицательных значений n и first для отрицательных значений.

Complexity: Точно last - first, nили 0 вызовов gen и присваиваний соответственно.

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

Requires: Тип *first должен удовлетворять требованиям MoveAssignable requirements.

Effects: Устраняет все элементы ссылаются итератором i в диапазоне , [first, last) для которых выполняются следующие соответствующие условия: *i == value, pred(*i) != false.

Returns: Конец получившегося диапазона.

Remarks: Stable.

Complexity: Точно last - first применения соответствующего предиката.

[ Note: Каждый элемент в диапазоне [ret, last), где ret - возвращаемое значение, имеет допустимое, но неуказанное состояние, потому что алгоритмы могут исключать элементы, перемещаясь из элементов, которые изначально находились в этом диапазоне. ] — 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);

Requires: Диапазоны [first, last) и [result, result + (last - first)) не должны перекрываться. Выражение *result = *first действительно. [ Note: Для перегрузок с a ExecutionPolicyможет возникнуть снижение производительности, если iterator_traits<ForwardIterator1>::value_type это не так MoveConstructible (таблица 23). ] — end note

Effects: Копирование всех элементов , упомянутых в итератор i в диапазоне ,[first, last) для которых выполняются соответствующие условия не выполняются: *i == value, pred(*i) != false.

Returns: Конец получившегося диапазона.

Complexity: Точно last - first применения соответствующего предиката.

Remarks: 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);

Requires: Функция сравнения должна быть отношением эквивалентности. Тип *first должен удовлетворять требованиям MoveAssignable requirements.

Effects: Для непустого диапазона удаляет все элементы, кроме первого, из каждой последующей группы эквивалентных элементов, на которые ссылается итератор, i в диапазоне, [first + 1, last) для которого выполняются следующие условия: *(i - 1) == *i или pred(*(i - 1), *i) != false.

Returns: Конец получившегося диапазона.

Complexity: Для непустых диапазонов - в точности (last - first) - 1 применения соответствующего предиката.

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

Requires:

(5.1)
Функция сравнения должна быть отношением эквивалентности.
(5.2)
Диапазоны [first, last) и [result, result+(last-first)) не должны перекрываться.
(5.3)
Выражение *result = *first действительно.
(5.4)
Для перегрузок без значения ExecutionPolicyпозвольте T быть типом значения InputIterator. Если InputIterator соответствует требованиям прямого итератора, то дополнительных требований для T. В противном случае, если OutputIterator соответствует требованиям прямого итератора и его тип значения такой же, как T, то T должно быть CopyAssignable. В противном случае T должны быть оба CopyConstructible и CopyAssignable. [ Note: Для перегрузок с an ExecutionPolicyможет возникнуть снижение производительности, если тип значения ForwardIterator1 не является одновременно CopyConstructible и CopyAssignable. ] — end note

Effects: Копирует только первый элемент из каждой последовательной группы равных элементов, на которую ссылается итератор, i в диапазоне, [first, last) для которого выполняются следующие соответствующие условия: *i == *(i - 1) или pred(*i, *(i - 1)) != false.

Returns: Конец получившегося диапазона.

Complexity: Для непустых диапазонов - в точности last - first - 1 применения соответствующего предиката.

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

Requires: *first будет swappable.

Effects: Для каждого неотрицательного целого числа i < (last - first) / 2применяется iter_swap ко всем парам итераторов first + i, (last - i) - 1.

Requires: BidirectionalIterator должны удовлетворять требованиям ValueSwappable.

Complexity: Ровно (last - first)/2 свопы.

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

Requires: Диапазоны [first, last) и [result, result + (last - first)) не должны перекрываться.

Effects: Копирование диапазона [first, last) к диапазону [result, result + (last - first)) , что для любого целого неотрицательного числа i < (last - first) следующего присваивания происходит: *(result + (last - first) - 1 - i) = *(first + i).

Returns: result + (last - first).

Complexity: Собственно last - first задания.

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

Requires: [first, middle) и [middle, last) должны быть допустимые диапазоны. ForwardIterator должны удовлетворять требованиям ValueSwappable. Тип *first должен удовлетворять требованиям MoveConstructible и требованиям MoveAssignable.

Effects: Для каждого неотрицательного целого числа i < (last - first)помещает элемент из позиции first + i в позицию first + (i + (last - middle)) % (last - first).

Returns: first + (last - middle).

Remarks: Это левый поворот.

Complexity: В большинстве last - first свопов.

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

Requires: Диапазоны [first, last) и [result, result + (last - first)) не должны перекрываться.

Effects: Копирование диапазона [first, last) к диапазону [result, result + (last - first)) , что для каждого неотрицательного целого числа i < (last - first) следующего присваивания происходит: *(result + i) = *(first + (i + (middle - first)) % (last - first)).

Returns: result + (last - first).

Complexity: Собственно last - first задания.

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

Requires:

(1.1)
PopulationIterator должны удовлетворять требованиям input iterator.
(1.2)
SampleIterator должны удовлетворять требованиям output iterator.
(1.3)
SampleIterator должен удовлетворять дополнительным требованиям а, random access iterator если не PopulationIterator удовлетворяет дополнительным требованиям а forward iterator.
(1.4)
PopulationIteratorТип значения должен быть writable to out.
(1.5)
Distance должен быть целочисленным типом.
(1.6)
remove_reference_t<UniformRandomBitGenerator> должен соответствовать требованиям uniform random bit generator типа, возвращаемый тип которого может быть преобразован в Distance.
(1.7)
out не должно быть в диапазоне [first, last).

Effects: Копирует min(last - first, n) элементы (the sample) из [first, last) (the population) в так out , чтобы каждый возможный образец имел равную вероятность появления. [ Note: Алгоритмы, обеспечивающие такие эффекты, включают selection sampling и reservoir sampling. ] — end note

Returns: Конец результирующего диапазона выборки.

Complexity: $O (last - first)$ .

Remarks:

(5.1)
Стабильно тогда и только тогда, когда PopulationIterator удовлетворяет требованиям прямого итератора.
(5.2)
В той степени, в которой реализация этой функции использует случайные числа, объект g должен служить источником случайности реализации.

28.6.13 Shuffle [alg.random.shuffle]

template<class RandomAccessIterator, class UniformRandomBitGenerator> void shuffle(RandomAccessIterator first, RandomAccessIterator last, UniformRandomBitGenerator&& g);

Requires: RandomAccessIterator должны удовлетворять требованиям ValueSwappable. Тип remove_reference_t<UniformRandomBitGenerator> должен соответствовать требованиям uniform random bit generator типа, в который можно преобразовать возвращаемый тип iterator_traits<RandomAccessIterator>::difference_type.

Effects: Переставляет элементы в диапазоне [first, last) таким образом, чтобы каждая возможная перестановка этих элементов имела равную вероятность появления.

Complexity: Ровно (last - first) - 1 свопы.

Remarks: В той степени, в которой реализация этой функции использует случайные числа, объект g должен служить источником случайности реализации.