Д. Стефенс - C++. Сборник рецептов

Для диапазона требуется выполнить алгоритм, и ни один из стандартных алгоритмов не удовлетворяет требованиям.

Напишите алгоритм в виде шаблона функции и с помощью имен параметров шаблона укажите свои требования к итератору. В примере 7.10 показан измененный стандартный алгоритм сору.

Пример 7.10. Написание собственного алгоритма

#include

#include

#include

#include

#include

#include

#include

#include "utils.h" // Для printContainer(): см. 7.10

using namespace std;

template

Out copyIf(In first, In last, Out result, UnPred pred) {

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

if (pred(*first)) *results = *first;

return(result);

}

int main() {

cout << "Введите несколько строк: ";

istream_iterator start(cin);

istream_iterator end; // Здесь создается "маркер"

vector v(start, end);

list lst;

copyIf(v.begin(), v.end(), back_inserter >(lst),

bind2nd(less(), "cookie"));

printContainer(lst);

}

Запуск примера 7.10 будет выглядеть примерно так.

Введите несколько строк: apple banana danish eclaire

^Z

-----

apple banana

Вы видите, что он копирует в результирующий диапазон только те значения, которые меньше, чем «cookie».

Стандартная библиотека содержит шаблон функции сору, который копирует элементы из одного диапазона в другой, но нет стандартной версии, которая принимает предикат и выполняет условное копирование элементов (т.е. алгоритм copy_if), так что пример 7.10 делает именно это. Его поведение довольно просто: при наличии диапазона-источника и начала диапазона-приемника производится копирование в целевой диапазон элементов, для которых унарный функтор-предикат возвращает true.

Этот алгоритм прост, но в его реализации есть еще кое-что, что привлекает внимание. Посмотрев на объявление, вы увидите, что в нем присутствует три параметра шаблона.

template

Out copyIf(In first, In last, Out result UnPred pred) {

Первый параметр шаблона In— это тип входного итератора. Так как это входной диапазон, все, что должен иметь возможность сделать с ним copyIf, — это извлечь разыменованное значение этого итератора и перевести итератор на следующий элемент. Это дает описание категории итератора ввода (категории итераторов описаны в рецепте 7.1), так что с помощью указания имени параметра шаблона Inмы объявляем именно этот тип итератора. Стандартного соглашения здесь нет ( Inи Out— это мои соглашения, которые я описал в первом рецепте этой главы), но вы легко можете придумать свои собственные соглашения об именах: InIter, Input_Tили даже InputIterator.Второй параметр шаблона Out— это тип итератора, который указывает на диапазон, в который будут копироваться элементы, copyIfдолжен иметь возможность записать разыменованное значение в выходной итератор и увеличить его значение, что дает нам описание оператора вывода. Объявив требования к итераторам с помощью имен параметров шаблона, вы делаете соглашения о вызовах алгоритма понятными без документации. Но зачем использовать две разные категории итераторов?

Имеется, по крайней мере, две причины использования в copyIfдвух различных категорий итераторов. Во-первых, операции с каждым диапазоном несколько отличаются друг от друга, и так как мне никогда не потребуется возвращаться назад по входному диапазону или присваивать ему значения, все, что мне требуется, — это итератор ввода. Аналогично мне никогда не потребуется читать из выходного диапазона, так что все, что здесь требуется, — это итератор вывода. Имеются требования к каждому из итераторов, которые не применимы к другому итератору, так что нет никакого смысла использовать для обоих диапазонов, например, два двунаправленных итератора. Во-вторых, использование различных типов итераторов позволяет вызывающему коду читать из одного типа диапазона и записывать в другой. В примере 7.10 я читаю из vectorи записываю в list.

vector v(start, end);

list lst;

copyIf(v.begin(), v.end(), back_inserter >(lst),

bind2nd(less(), "cookie"));

Если попробовать сделать то же самое, использовав в алгоритме один и тот же тип итераторов, то он просто не скомпилируется.

В примере 7.10 я в качестве начала выходного диапазона передаю back_inserter, а не, скажем, итератор, возвращаемый lst.begin. Это делается потому, что lst не содержит элементов, и в этом алгоритме (как и в стандартном алгоритме копирования) целевой диапазон должен быть достаточно большим, чтобы вместить все элементы, которые будут в него скопированы. В противном случае увеличение итератора вывода в copyIfприведет к неопределенному поведению. back_inserterвозвращает итератор вывода, который при его увеличении вызывает для контейнера метод push_back. В результате этого при каждом увеличении выходного итератора размер lstувеличивается на один. Более подробно шаблон класса back_inserterя описываю в рецепте 7.5.