Совет 37. Используйте accumulate или for_each для обобщения интервальных данных
Совет 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, соответствующий началу координат, а нам остается лишь помнить о необходимости исключения этой точки из вычислений.
Функтор PointAverage отслеживает количество обработанных точек, а также суммы их компонентов х и у. При каждом вызове он обновляет данные и возвращает средние координаты по обработанным точкам. Поскольку для каждой точки в интервале функтор вызывается ровно один раз, он делит суммы по составляющим х и у на количество точек в интервале. Начальная точка, переданная при вызове accumulate, игнорируется.
class PointAverage:
publiс binary_function<Point,Point,Point>{ public:
PointAverage():xSum(0),ySum(0),numPoints(0) {}
const Point operator() (const Point& avgSoFar, const Point& p)
++numPoints;
xSum += p.x;
ySum += p.y;
return Point(xSum/numPoints,ySum/numPoints);
}
private:
size_t numPoints;
double xSum;
double ySum;
Такое решение прекрасно работает, и лишь из-за периодических контактов с неординарно мыслящими личностями (многие из которых работают в Комитете по стандартизации) я могу представить себе реализации STL, в которых возможны проблемы. Тем не менее, PointAverage нарушает параграф 2 раздела 26.4.1 Стандарта, который, как вы помните, запрещает побочные эффекты по отношению к функции,передаваемой accumulate. Модификация переменных numPoints, xSum и ySum относится к побочным эффектам, поэтому с технической точки зрения приведенный выше фрагмент приводит к непредсказуемым последствиям. На практике трудно представить, что приведенный код может не работать, но чтобы моя совесть была чиста, я обязан специально оговорить это обстоятельство.
Впрочем, у меня появляется удобная возможность упомянуть о for_each — другом алгоритме, который может использоваться для обобщения интервалов. На for_each не распространяются ограничения, установленные для accumulate. Алгоритм for_each, как и accumulate, получает интервал и функцию (обычно в виде объекта функции), вызываемую для каждого элемента в интервале, однако функция, передаваемая for_each, получает только один аргумент (текущий элемент интервала), а после завершения работы for_each возвращает свою функцию (а точнее, ее копию — см. совет 38). Что еще важнее, переданная (и позднее возвращаемая) функция может обладать побочными эффектами.
Помимо побочных эффектов между for_each и accumulate существуют два основных различия. Во-первых, само название accumulate ассоциируется с вычислением сводного значения по интервалу, а название for_each скорее предполагает выполнение некой операции с каждым элементом интервала. Алгоритм for_each может использоваться дя вычисления сводной величины, но такие решения по наглядности уступают accumulate.
Во-вторых, accumulate непосредственно возвращает вычисленное значение, а for_each возвращает объект функции, используемый для дальнейшего получения информации. В С++ это означает, что в класс функтора необходимо включить функцию для получения искомых данных.
Ниже приведен предыдущий пример, в котором вместо accumulate используется for_each:
struct Point{...};// См. ранее
class PointAverage;
public unary_function<Point,void>{// См. совет 40
public:
PointAverage():xSum(0).ySum(0),numPoints(0) {}
void operator() (const Point& p)
{
++numPoints;
xSum += p.x;
ySum += p.y:
}
Point result() const {
return Point(xSum/numPoints,ySum/numPoints);
}
private:
size t numPoints;
double xSum;
double ySum;
};
list<Point> lp:
Point avg = for_each(lp.begin(),lp.end(),PointAverage()).result();
Лично я предпочитаю обобщать интервальные данные при помощи accumulate, поскольку мне кажется, что этот алгоритм наиболее четко передает суть происходящего, однако foreach тоже работает, а вопрос побочных эффектов для for_each не так принципиален, как для accumulate. Словом, для обобщения интервальных данных могут использоваться оба алгоритма; выберите тот, который вам лучше подойдет.
Возможно, вас интересует, почему у for_each параметр-функция может иметь побочные эффекты, а у accumulate — не может? Представьте, я бы тоже хотел это знать. Что ж, дорогой читатель, некоторые тайны остаются за пределами наших познаний. Чем accumulate принципиально отличается от for_each? Пока я еще не слышал убедительного ответа на этот вопрос.