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>

T accumulate(InputIterator first, InputIterator last, T init, Function F);

Здесь first и last задают диапазон значений итератора, а init устанавливает начальное значение (для аддитивных операций это 0, а для мультипликативных – 1), F – функтор, определяющий вид операции.

Пример

vector<int> v;

v.push_back(2); v.push_back(5);

cout << accumulate(v.begin(), v.end(), 10, divides<int>());

Кроме рассмотренных алгоритмов, четвертая группа включает также алгоритмы inner_product, partial_sum и adjacent_difference.

Функторы

Функтором в STL называют объект, класс которого инкапсулирует операцию функционального вызова operator(). Функторы удобно использовать для представления предикатов и других функций, передаваемых алгоритмам (выше в примерах мы уже несколько раз использовали функторы). Простейшими стандартными функторами являются функтор отрицания и функтор суммирования. Их определения даны ниже.

template <class T> // функтор отрицания

struct negate: unary_function<T, T> {

T operator()(const T & x) const { return -x; }

};

template <class T> // функтор суммирования

struct plus: binary_function<T, T, T> {

T operator()(const T & x, const T & y) const { return x + y; }

};

Шаблон negate, представляющий функтор отрицания, открыто наследует от шаблона unary_function, а шаблон plus, соответствующий функтору суммирования, – от шаблона binary_function. Сами эти шаблоны, по сути, не представляют классы, поскольку не определяют никакого поведения, а лишь вводят типы данных для аргументов и результата. Их определения имеют вид:

template <class Arg, class Result> struct unary_function

{

typedef Arg argument_type;

typedef Result result_type;

};

template <class Arg1, class Arg2, class Result> struct binary_function

{

typedef Arg1 first_argument_type;

typedef Arg2 second_argument_type;

typedef Result result_type;

};

Как шаблоны unary_function, binary_function, так и рассмотренные выше (и многие другие) функторы определены в заголовочном файле function.h. В этом файле имеется много разнообразных функторов, в частности, представляющие базовые логические операции, арифметические операции, операции сравнения.

Кроме стандартных функторов, любая программа может содержать определенные пользователем функторы. Примеры таких определений имеются выше. Ниже приведен еще один подобный пример. В нем определяется функтор prod_odd, который возвращает логическое значение. Оно индицирует, является ли произведение аргументов функтора нечетным числом. Сам функтор используется для поиска в списке первых двух смежных значений, произведение которых нечетно.

Пример

template <class T> class prod_odd {

public:

int operator() (const T & v1, const T & v2) {

return v1%2!= 0 && v2%2!= 0;

}

};

...

list<int> l;

// заполняем список значениями

...

list<int>::iterator i = // поиск стандартным алгоритмом adjacent_find

adjacent_find(l.begin(), l.end(), prod_odd<int>());

if (i!= l.end())

cout << *i++ << " " *i++;

else cout << "таких значений в списке нет";

 

Ассоциативные контейнеры

Ассоциативные контейнеры – это особый вид контейнеров, которые позволяют быстро получать доступ к хранимым в них данным за счет использования механизма ключей. В STL определены следующие виды таких контейнеров: набор (set), мультинабор (multiset), отображение (map), мультиотображение (multimap). Все указанные контейнеры хранят данные сортированными, причем для обеспечения максимальной скорости получения данных в качестве «внутреннего» контейнера они используют дерево специального вида. Отличие между контейнерами set (map) и multiset (multimap) состоит в том, что set и map используют уникальные ключи для идентификации данных, а multiset и multimap нет. Для того чтобы включить поддержку рассматриваемых контейнеров, нужно подключить заголовочные файлы set.h и map.h соответственно.

Шаблон set инкапсулирует свойства и операции над упорядоченным набором объектов. Ключевые данные для упорядочения – сами хранимые объекты (т.е. хранимый объект – это и данные, и ключ). Параметрами шаблона являются: тип хранимых объектов (он же – тип ключа), функтор Compare, задающий способ упорядочения объектов (по умолчанию упорядочением управляет стандартный функтор less<T>), а также аллокатор, инкапсулирующий модель памяти программы. Число, порядок и назначение параметров шаблона multiset аналогичны (ключи в multiset, напомним, необязательно уникальны, т.е. multiset может содержать один и тот же объект многократно). Примеры определения набора и мультинабора даны ниже (создать контейнер рассматриваемых классов можно также из другого ассоциативного контейнера, или из последовательности элементов с указанием диапазона значений итератора).

Примеры

set < MyClass, greater<MyClass> > MyClassSet;

// порядок сортировки данных задается классом greater<MyClass>

multiset <MyClass> MyClassMultiSet;

// а здесь порядок задается классом less<MyClass> по умолчанию

 

Контейнеры set и multiset включают «типичные» для всех контейнеров компонентные функции begin, end, rbegin, rend, empty, size, max_size, swap и ряд других. Действие этих функций не отличается от действия их аналогов в последовательных контейнерах. Для перебора компонент set и multiset используют двунаправленные итераторы. Присваивание выполняется операцией operator =, а сравнение операцией operator ==. Добавление объектов производится функцией insert, удаление – функцией erase. К контейнерам set и multiset применимы теоретико-множественные операции, такие как пересечение, включение элемента, разность и т.д.

Пример