Давайте напишем функцию-фильтр для решения следующей задачи: выбрать из последовательного контейнера положительные элементы и скопировать их в другой контейнер. Мы писали подобную функцию для «умного» массива (см. листинг 5.19), однако она была недостаточно обобщенная, так как предназначалась только для обработки объектов класса ТАггау.
Очевидно, что первым шагом обобщения являются шаблоны — мы должны написать шаблон функции-фильтра, чтобы не зависеть от типа элементов контейнера. Однако этого недостаточно. Если мы будем передавать контейнер в качестве параметра и возвращать новый контейнер как результат, наша функция-фильтр будет зависеть от типа контейнера. Например, напишем фильтр с таким заголовком:
template <class Т>
TArray<T> copy_if(const Tarray<T>& m, const T& t)
Мы сразу написали обобщенный вариант — сравнение элементов контейнера будет выполняться не с нулем, а с произвольным значением. Однако совершенно очевидно, что такая функция не в состоянии обрабатывать контейнеры другого типа. Кроме того, мы не сможем обрабатывать с помощью такой функции массивы.
К счастью, решение нам уже известно — итераторы. Входной контейнер, в котором должен осуществляться поиск, представляется в виде пары итераторов, задающей полуоткрытый интервал [begin, end). Однако и выходной контейнер нельзя задавать как результат — зависимость от типа контейнера останется. Поэтому лучше и выходной контейнер задать итераторами. Нам достаточно одного итератора — начального. Тогда функция может либо вообще не возвращать результат, либо возвратить выходной итератор. Естественно, типы итераторов являются параметрами шаблона, как и тип элементов контейнера.
Такое решение сразу накладывает некоторые ограничения на использование функции-фильтра:
1. Чтобы задать итератор выходного контейнера при вызове нашей функции, выходной контейнер должен существовать на момент вызова.
2. В контейнере должны существовать элементы и их должно быть достаточное количество, чтобы вместить все удовлетворяющие критерию отбора элементы входного контейнера.
3. Выходной контейнер должен быть совместим по типу элементов с входным.
Таким образом, в отношении выходного контейнера мы вынуждены полностью полагаться на программиста. Однако «овчинка стоит выделки» — мы получаем алгоритм, который действительно не зависит от входного и выходного контейнеров (листинг 12.5).
Листинг 12.5. Функция-фильтр копирования по условию
template < class Inputlterator, // входной контейнер
class Outputlterator, // выходной контейнер
class Т // тип элементов
>
void copy_if(Inputlterator first, Inputlterator last, Outputlterator result, const T &v
)
{ for ( ; first != last; ++first) if (*first > v)
{ *result = *first; ++result; } return;
}
Этот алгоритм совершенно правильно работает и с массивами, и с контейнерами, обеспечивающими последовательный доступ с помощью итераторов.
ПРИМЕЧАНИЕ
Алгоритм работает и с контейнерами стандартной библиотеки шаблонов. ^ г -
Однако он все-таки не является универсальным — критерий отбора элементов задан жестко в теле функции в виде условия оператора if. Алгоритм стал бы значительно мощнее, если бы и критерий отбора можно было задавать в виде параметра.
Это можно сделать, определив еще один параметр — указатель на функцию. Очевидно, что эта функция должна вызываться в условии оператора if, а поэтому возвращать должна результат типа bool1. Функция, возвращающая результат типа bool, называется предикатом. Функция-предикат с одним параметром называется унарным предикатом; функция-предикат с двумя параметрами — бинарным предикатом. Очевидно, наша функция — критерий отбора — является бинарным предикатом, так как вызов ее в условии оператора if может выглядеть так:
1 Конечно, это не обязательно, но мы сейчас говорим о «правильном» использовании copy_if.
if(f(v. *first)) ...
Перепишем нашу функцию-фильтр и напишем заодно пару функций-предикатов для проверки ее работы (листинг 12.6). |
Главная
Каталог файлов
