Алгоритмы, меняющие последовательность

Копировать (Copy)

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

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

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

     copy_backward копирует элементы в диапазоне [first, last) в диапазон [result - (last - first), result), начиная от last-1 и продолжая до first. Его нужно использовать вместо copy, когда last находится в диапазоне [result - (last - first), result). Для каждого положительного целого числа n <= (last - first) выполняется присваивание *(result - n) = *(last - n). copy_backward возвращает result - (last - first). Точно делается last - first присваиваний. Результат copy_backward не определён, если result находится в диапазоне [first, last).

Обменять (Swap)

template <class T> 
void swap(T& a, T& b);

     swap обменивает значения, хранимые в двух местах.

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

     iter_swap обменивает значения, указанные двумя итераторами a и b.

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

     Для каждого неотрицательного целого числа n < (last1 - first1) выполняется перестановка: swap(*(first1 + n), *(first2 + n)). swap_ranges возвращает first2 + (last1 - first1). Выполняется точно last1 - first1 перестановок. Результат swap_ranges не определён, если два диапазона [first1, last1) и [first2, first2 + (last1 - first1)) перекрываются.

Преобразовать (Transform)

template  <class InputIterator, class OutputIterator, class Unary0peration> 
OutputIterator transform(InputIterator first, InputIterator last, 
    OutputIterator result, UnaryOperation op);

template  <class InputIterator1, class InputIterator2, 
    class OutputIterator, class Binary0peration> 
OutputIterator transform(InputIterator1 first1, InputIterator1 last1, 
    InputIterator2 first2, OutputIterator result,
    BinaryOperation binary_op);

     transform присваивает посредством каждого итератора i в диапазоне [result, result + (last1 - first1)) новое соответствующее значение, равное op(* (first1 + (i - result)) или binary_op(*(first1 + (i - result), *(first2 + (i - result))). transform возвращает result + (last1 - first1). Применяются op или binary_op точно last1 - first1 раз. Ожидается, что op и binary_op не имеют каких-либо побочных эффектов. result может быть равен first в случае унарного преобразования или first1 либо first2 в случае бинарного.

Заменить (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);

     replace заменяет элементы, указанные итератором i в диапазоне [first, last), значением new_value, когда выполняются следующие соответствующие условия: *i == old_value, pred(*i) == true. Соответствующий предикат применяется точно 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 Iterator, class OutputIterator, class Predicate, class T> 
OutputIterator replace_copy_if(Iterator first, Iterator last,
    OutputIterator result, Predicate pred, const T& new_value);

     replace_copy присваивает каждому итератору i в диапазоне [result, result + (last - first)) значение new_value или *(first + (i - result)) в зависимости от выполнения следующих соответствующих условий: *(first + (i - result)) == old_value, pred(*(first + (i - result))) == true. replace_copy возвращает result + (last - first). Соответствующий предикат применяется точно last - first раз.

Заполнить (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(Output Iterator first, Size n, const T& value);

     fill присваивает значения через все итераторы в диапазоне [first, last) или [first, first + n). fill_n возвращает first + n. Точно делается last - first (или n) присваиваний.

Породить (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);

     generate вызывает функциональный объект gen и присваивает возвращаемое gen значение через все итераторы в диапазоне [first, last) или [first, first + n). gen не берёт никакие параметры. generate_n возвращает first + n. Точно выполняется last - first (или n) вызовов gen и присваиваний.

Удалить (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);

     remove устраняет все элементы, указываемые итератором i в диапазоне [first, last), для которых выполнены следующие соответствующие условия: *i == value, pred (*i) == true. remove возвращает конец возникающего в результате своей работы диапазона. remove устойчив, то есть относительный порядок элементов, которые не удалены, такой же, как их относительный порядок в первоначальном диапазоне. Соответствующий предикат применяется точно last -first раз.

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

     remove_copy копирует все элементы, указываемые итератором i в диапазоне [first, last), для которых не выполнены следующие соответствующие условия:*i == value, pred (*i) == true. remove_copy возвращает конец возникающего в результате своей работы диапазона. remove_copy устойчив, то есть относительный порядок элементов в результирующем диапазоне такой же, как их относительный порядок в первоначальном диапазоне. Соответствующий предикат применяется точно last - first раз.

Убрать повторы (Unique)

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

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

     unique устраняет все, кроме первого, элементы из каждой последовательной группы равных элементов, указываемые итератором i в диапазоне [first, last), для которых выполнены следующие соответствующие условия: *i == *(i - 1) или binary_pred(*i, *(i - 1)) == true. unique возвращает конец возникающего в результате диапазона. Соответствующий предикат применяется точно (last - first) - 1 раз.

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

     unique_copy копирует только первый элемент из каждой последовательной группы равных элементов, указываемых итератором i в диапазоне [first, last), для которых выполнены следующие соответствующие условия: *i == *(i - 1) или binary_pied(*i, *(i - 1)) == true. unique_copy возвращает конец возникающего в результате диапазона. Соответствующий предикат применяется точно (last - first) - 1 раз.

Расположить в обратном порядке (Reverse)

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

     Для каждого неотрицательного целого числа i <= (last - first)/2 функция reverse применяет перестановку ко всем парам итераторов first + i, (last - i) - 1. Выполняется точно (last - first)/2 перестановок.

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

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

Переместить по кругу (Rotate)

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

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

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

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

Перетасовать (Random shuffle)

template <class RandomAccessIterator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffie(RandomAccessIterator first, RandomAccessIterator last, 
    RandomNumberGenerator& rand);

     random_shuffle переставляет элементы в диапазоне [first, last) с равномерным распределением. Выполняется точно last - first перестановок. random_shuffle может брать в качестве параметра особый генерирующий случайное число функциональный объект rand такой, что rand берёт положительный параметр n типа расстояния RandomAccessIterator и возвращает случайно выбранное значение между 0 и n-1.

Разделить (Partitions)

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

     partition помещает все элементы в диапазоне [first, last), которые удовлетворяют pred, перед всеми элементами, которые не удовлетворяют. Возвращается итератор i такой, что для любого итератора j в диапазоне [first, i) будет pred (*j) == true, а для любого итератора k в диапазоне [i, last) будет pred(*k) == false. Делается максимально (last - first)/2 перестановок. Предикат применяется точно last - first раз.

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

     stable_partition помещает все элементы в диапазоне [first, last), которые удовлетворяют pred, перед всеми элементами, которые не удовлетворяют. Возвращается итератор i такой, что для любого итератора j в диапазоне [first, i) будет pred(*j) == true, а для любого итератора k в диапазоне [i, last) будет pred(*k) == false. Относительный порядок элементов в обеих группах сохраняется. Делается максимально (last - first) * log(last - first) перестановок, но только линейное число перестановок, если имеется достаточная дополнительная память. Предикат применяется точно last - first раз.