5.3 Обобщенные алгоритмы и функторы

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

Примером обобщенного алгоритма, обрабатывающего входной контейнер «по месту», может служить функция сортировки, которая может иметь следующий прототип

template <class Iterator>

void sort(Iterator first, Iterator last);

Примером алгоритма, перебирающего входной контейнер и записывающего результаты в выходной, может служить алгоритм копирования. Прототип алгоритма примерно следующий:

template <class Inputlterator, class Outputlterator>

Output Iterator copy(

Inputlterator first,

Inputlterator last,

Outputlterator result);

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

Часто параметром алгоритма является функтор. Функтор представляет собой объект, ведущий себя как функция. Класс, в котором перегружена операция operator() вызова функции, называется классом-функтором. Объект такого класса называют объектом-функцией, или функтором.

Например, функтор, определяющий нечетность своего аргумента, пишется так:

class Odd

{

public:

int operator()(const int &d)

{ return (d % 2); }

};

Вызов данного функтора выглядит как вызов обычной функции:

Odd f;

f(5);

Функтор, возвращающий булевский результат, называется функтором-предикатом. Функтор с одним аргументом называется унарным функтором; функтор с двумя аргументами  бинарным.

Класс-функтор является обычным классом, поэтому в нем могут быть определены любые поля, конструкторы, методы. Любые методы, в том числе и перегруженные операции вызова функции (их может быть несколько), могут быть объявлены виртуальными. Класс-функтор вправе участвовать в иерархии наследования, вправе запрашивать динамическую память, может быть абстрактным. Пример класса-функтора с полями и конструктором:

class GreaterEqual

{

int value;

public:

GreaterEqual(const int &v): value(v) { }

bool operator()(const int &d)

{ return (d >= value); }

};

При наличии конструктора инициализации вызов функтора можно представить как вызов конструктора, например:

Greater(3);

Обычно функтор оформляют в виде шаблона класса, например:

template <class Т>

class GreaterEqual

{

Т value;

public:

GreaterEqual(const T &v): value(v) { }

bool operator()(const T &d)

{ return (d >= value);

};

Шаблон класса-функтора – это еще один способ реализации шаблона функции, к которой разрешается применять все «прелести» шаблонов классов.

Примером обобщенного алгоритма, использующего функтор, может служить алгоритм foreach() со следующим прототипом:

template <class Iterator, class Function>

void for_each(Iterator first, Iterator last, Function f);

Алгоритм применяет функтор f к каждому элементу контейнера из заданного интервала. Реализация обобщенного алгоритма с функтором показана в листинге 11.6.

Листинг 11.6. Обобщенный алгоритм copy_if() с функтором

template < class Inputlterator,

class Outputlterator,

class Predicate

>

void copy_if( Inputlterator first,

Inputlterator last,

Outputlterator result,

Predicate Functor )

{

for ( ; first != last: ++first)

if (Functor(*first))

// вызов функтора

{ *result = *first; ++result; }

return; - *-

}

Данный алгоритм копирует элементы, удовлетворяющие предикату Functor, из заданного интервала входного контейнера в выходной. Этот алгоритм с приве­денными выше функторами может пригодиться для следующих задач:

int а[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0};

int b[10] = { 0 };

copy_if(a, а+10, b, Odd());

Odd f;

copy_if(a, a+10, b, f);

GreaterEqual five(5);

copy_if(a, a+10, b, five);

copy_if(a, a+10, b, GreaterEqual(6));

copy_if(a, a+10, b, GreaterEqual<int>(4));