Совет 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? Пока я еще не слышал убедительного ответа на этот вопрос.