Скотт Мейерс - Эффективное использование STL
template<typename InputIterator,// Не совсем правильная
typename OutputIterator,// реализация copy_if
typename Predicate>
OutputIterator copy_if(InputIterator begin,
InputIterator end,
OutputIterator destBegin,
Predicate p)
{
return remove_copy_if(begin,end,destBegin,not1(p));
}
Решение основано на простом факте: хотя STL не позволяет сказать «скопировать все элементы, для которых предикат равен true», но зато можно потребовать «скопировать все элементы, кроме тех, для которых предикат неравен true». Создается впечатление, что для реализации copy_if достаточно поставить not1 перед предикатом, который должен передаваться copy_if, после чего передать полученный предикат remove_copy_if. Результатом является приведенный выше код.
Если бы эти рассуждения были верны, копирование дефектных объектов Widget можно было бы произвести следующим образом:
copy_if(widgets.begin(),.widgets.end(),// Хорошо задумано,
ostream_iterator<Widget>(cerr,"n"), // но не компилируется
isDefective);
Компилятор недоволен попыткой применения not1 к isDefective (это происходит внутри copy_if). Как объясняется в совете 41, not1 не может напрямую применяться к указателю на функцию — сначала указатель должен пройти через ptr_fun. Чтобы вызвать эту реализацию copy_if, необходимо передать не просто объект функции, а адаптируемый объект функции. Сделать это несложно, однако возлагать эти хлопоты на будущих клиентов алгоритма STL нельзя. Стандартные алгоритмы STL никогда не требуют, чтобы их функторы были адаптируемыми, поэтому нельзя предъявлять это требование к copy_if. Приведенная выше реализация хороша, но недостаточно хороша.
Правильная реализация copy_if должна выглядеть так:
template<typename InputIterator,// Правильная
typename OutputIterator,// реализация copy_if
typename Predicate> OutputIterator copy_if(InputIterator begin.
InputIterator end, OutputIterator destBegin. Predicate p)
{
while begin!=end) { f(p(*begin)) *destBegn++ = *begin; ++begin;
}
return destBegn;
}
Поскольку алгоритм copy_if чрезвычайно полезен, а неопытные программисты STL часто полагают, что он входит в библиотеку, можно порекомендовать разместить реализацию copy_if — правильную реализацию! — в локальной вспомогательной библиотеке и использовать ее в случае надобности.
Совет 37. Используйте accumulate или for_each для обобщения интервальных данных
Иногда возникает необходимость свести целый интервал к одному числу или, в более общем случае, к одному объекту. Для стандартных задач обобщения существуют специальные алгоритмы. Так, алгоритм count возвращает количество элементов в интервале, а алгоритм count_if возвращает количество элементов, соответствующих заданному предикату. Минимальное и максимальное значение элемента в интервале можно получить при помощи алгоритмов min_element и max_element.
Но в некоторых ситуациях возникает необходимость обработки интервальных данных по нестандартным критериям, и в таких случаях нужны более гибкие и универсальные средства, нежели алгоритмы count, count_if, min_element и max_element. Предположим, вы хотите вычислить сумму длин строк в контейнере, произведение чисел из заданного интервала, усредненные координаты точек и т. д. В каждом из этих случаев производится обобщение интервала, но при этом критерий обобщения вы должны определять самостоятельно. Для подобных ситуаций в STL предусмотрен специальный алгоритм accumulate. Многим программистам этот алгоритм незнаком, поскольку в отличие от большинства алгоритмов он не находится в <algorthm>, а вместе с тремя другими «числовыми алгоритмами» (inner_product, adjacent_difference и partial_sum) выделен в библиотеку <numeric>.
Как и многие другие алгоритмы, accumulate существует в двух формах. Первая форма, получающая пару итераторов и начальное значение, возвращает начальное значение в сумме со значениями из интервала, определяемого итераторами:
list<double> ld;// Создать список и заполнить
// несколькими значениями типа double.
double sum = accumulate(ld.begin(),ld.end(),0,0); // Вычислить сумму чисел
// с начальным значением 0.0
Обратите внимание: в приведенном примере начальное значение задается в форме 0.0. Эта подробность важна. Число 0.0 относится к типу double, поэтому accumulate использует для хранения вычисляемой суммы переменную типа double. Предположим, вызов выглядит следующим образом:
double sum = accumulate(ld.begin(),ld.end(),0): // Вычисление суммы чисел
// с начальным значением 0; // неправильно!
В качестве начального значения используется int 0, поэтому accumulate накапливает вычисляемое значение в переменной типа int. В итоге это значение будет возвращено алгоритмом accumulate и использовано для инициализации переменной sum. Программа компилируется и работает, но значение sum будет неправильным. Вместо настоящей суммы списка чисел типа double переменная содержит сумму всех чисел, преобразуемую к int после каждого суммирования.
Алгоритм accumulate работает только с итераторами ввода и поэтому может использоваться даже с istream_iterator и istreambuf_iterator (см. совет 29):
cout << "The sum of the ints on the standard input is " // Вывести сумму
<< accumulate(istream_iterator<int>(cin),// чисел из входного
istream_iterator<int>(),// потока
0);
Из-за своей первой, стандартной формы алгоритм accumulate был отнесен к числовым алгоритмам. Но существует и другая, альтернативная форма, которой при вызове передается начальное значение и произвольная обобщающая функция. В этом варианте алгоритм accumulate становится гораздо более универсальным.
В качестве примера рассмотрим возможность применения accumulate для вычисления суммы длин всех строк в контейнере. Для вычисления суммы алгоритм должен знать две вещи: начальное значение суммы (в данном случае 0) и функцию обновления суммы для каждой новой строки. Следующая функция берет предыдущее значение суммы, прибавляет к нему длину новой строки и возвращает обновленную сумму:
string::size_type // См. далее
stringLengthSum(string::size_type sumSoFar, const string& s)
{
return sumSoFar + s.size();
}
Тело функции убеждает в том, что происходящее весьма тривиально, но на первый взгляд смущают объявления string::size_type. На самом деле в них нет ничего страшного. У каждого стандартного контейнера STL имеется определение типа size_type, относящееся к счетному типу данного контейнера. В частности, значение этого типа возвращается функцией size. Для всех стандартных контейнеров определение size_type должно совпадать с size_t, хотя теоретически нестандартные STL-совместимые контейнеры могут использовать в size_type другой тип (хотя я не представляю, для чего это может понадобиться). Для стандартных контейнеров запись контейнер:: size_type можно рассматривать как специальный синтаксис для size_t.
Функция stringLenghSum является типичным представителем обобщающих функций, используемых при вызове accumulate. Функция получает текущее значение суммы и следующий элемент интервала, а возвращает новое значение накапливаемой суммы. Накапливаемая сумма (сумма длин строк, встречавшихся ранее) относится к типу string::size_type, а обрабатываемый элемент относится к типу string. Как это часто бывает, возвращаемое значение относится к тому же типу, что и первый параметр функции.
Функция stringLenghSum используется в сочетании с accumulate следующим образом:
set<string> ss;// Создать контейнер строк
// и заполнить его данными
string::size_type lengthSum =// Присвоить lengthSum
accumulate(ss.begin(),ss.end(), // результат вызова stringLengthSum 0,stringLengthSum); // для каждого элемента ss
// с нулевым начальным значением
Изящно, не правда ли? Произведение вычисляется еще проще, поскольку вместо написания собственной функции суммирования можно обойтись стандартным функтором multiplies:
vector<float> vf;// Создать контейнер типа float
// и заполнить его данными
float product =// Присвоить product результат
accumulate(vf.begin(),vf.end(), // вызова multiplies<float>
1.0,multples<float>()); // для каждого элемента vf
// с начальным значением 1.0
Только не забудьте о том, что начальное значение вместо нуля должно быть равно единице (в вещественном формате, не в int!). Если начальное значение равно нулю, то результат всегда будет равен нулю — ноль, умноженный на любое число, остается нулем.
Последний пример не столь тривиален. В нем вычисляется среднее арифметическое по интервалу точек, представленных структурами следующего вида:
struct Point {
Point(double initX. double initY):x(initX),y(initY){};
double x.y;
};
В этом примере обобщающей функцией будет функтор PointAverage, но перед рассмотрением класса этого функтора стоит рассмотреть его использование при вызове accumulate:
list<Point> lp;
Point avg=
accumulate(lp.begin(),lp.end(),
Point(0,0),
PointAverage());
// Вычисление среднего
// арифметического по точкам,
// входящим в список lр
Просто и бесхитростно, как и должно быть. На этот раз в качестве начального значения используется объект Point, соответствующий началу координат, а нам остается лишь помнить о необходимости исключения этой точки из вычислений.
