OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result)

{

while (first != last) *result++ = *first++;

Return result;

}

У алгоритма copy есть модификация copy_backward, которая копирует элементы в обратном порядке (в отличие от copy, где необходимы входные итераторы, здесь требуются двунаправленные итераторы). Алгоритм преобразования transform также по существу является модификацией алгоритма copy, но он осуществляет копирование после применения к каждому элементу исходного контейнера некоторой операции. Определение для этого алгоритма приведено ниже.

template <class InputIterator, class OutputIterator, class UnaryOperation>

OutputIterator transform (InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op)

{

while (first != last) *result++ = op(*first++);

Return result;

}

К числу других алгоритмов рассматриваемого класса относятся replace (замена каждого появления в диапазоне контейнера некоторого значения old_value на новое значение new_value), replace_if (замена при выполнении некоторого условия-предиката), fill (заполнение диапазона контейнера заданным значением), swap (обмен местами двух значений или итераторов), remove_copy (копирование содержимого контейнера в другой, исключая заданное значение), __reverse (инвертирование порядка элементов контейнера) и т.д.

Третья категория включает сортирующие алгоритмы. К их числу относятся быстрая сортировка и ее модификации, сортировка вставками и модификации, линейная вставка, сортировка слиянием, устойчивая сортировка, частичная сортировка, нахождение медианы и т.д.

Наиболее распространенный алгоритм сортировки – алгоритм sort, который сортирует элементы контейнера в нужном порядке. Для обеспечения максимальной эффективности алгоритм работает в два этапа. На первом выполняется быстрая сортировка, на втором – сортировка вставками. Порядок сортировки элементов передается через функтор comp. Определение шаблона sort имеет вид

template <class RandomAccessIterator, class Compare>

Void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp)

{

if (!(first == last))

{

__Quick_sort_loop(first, last, comp); __final_insertion_sort(first, last, comp);

}

}

Здесь функция __quick_sort_loop реализует основной цикл быстрой сортировки путем вызова явно рекурсивной функции __quick_sort_loop_aux. Условием завершения этого цикла является разбиение сортируемого контейнера на достаточно «короткие» сегменты, к которым можно эффективно применить сортировку вставками. Сортировку вставками выполняет функция __final_insertion_sort; сама процедура вставок в ней осуществляется через функцию линейной вставки __linear_insert.

Вместо шаблона sort для сортировки специфическим методом можно явно использовать другие шаблоны, например, __insertion_sort (сортировка вставками).

Четвертая группа алгоритмов содержит обобщенные численные алгоритмы. К их числу относится, к примеру, алгоритм for_each. Этот алгоритм применяет заданный функтор к разыменованному итератору в указанном диапазоне значений итератора. Определение данного алгоритма очень простое и выглядит так:

template <class InputIterator, class Function>

Function for_each(InputIterator first, InputIterator last, Function f)

{

while (first != last) f(*first++);

return f;

}

Пример использования алгоритма for_each:

// функтор для суммирования значений

template <class T> class sum_up {

public:

void operator() (const T & value) { sum += value; }

const T & read_sum() { return sum; }

private:

static T sum;

};

int sum_up<int>::sum;

...

void main(void) {

deque<int> d(3,2); // очередь вида 2 2 2

sum_up<int> s; // создание функтора для суммирования

for_each (d.begin(), d.end(), s); // суммирование

cout << s.read_sum(); // вывод суммы

}

Еще одним полезным алгоритмом рассматриваемой категории является accumulate. Фактически он делает то же самое, что и for_each в приведенном примере. С помощью алгоритма accumulate можно организовать, например, накапливающее суммирование или умножение с учетом начального значения. Заголовок этого алгоритма определен в виде:

template <class InputIterator, class T, Function F>