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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Совет 17: Безопасность данных

Из книги автора

Совет 17: Безопасность данных Благодаря удаленным хранилищам, даже в случае полного вымирания человеческого рода в результате какого-либо катаклизма, будущие инопланетные исследователи Земли смогут полюбоваться на интерьеры земных туалетов и лифтов, заслоненных


Совет 25: Кража игровых данных

Из книги автора

Совет 25: Кража игровых данных Некто взломал ваши учетные записи в онлайн-играх, украл навороченный меч, угнал любимый танк и увел со двора свинью девятого уровня? Удивляться нечему, закон рынка гласит: всякая вещь стоит столько, сколько за нее готовы заплатить. Поэтому


Совет 68: Сохранение данных

Из книги автора

Совет 68: Сохранение данных Кинули файлы на флешку и выдернули ее из компа? Готовьтесь к тому, что их там не окажется. Нет, это не диверсия. Как ни странно, это сделано для удобства пользователей. Дело в том, что флешка записывает данные гораздо медленнее, чем компьютер их


Отношение обобщения

Из книги автора

Отношение обобщения Отношение обобщения является обычным таксономическим отношением между более общим элементом (родителем или предком) и более частным или специальным элементом (дочерним или потомком). Данное отношение может использоваться для представления


Совет 5. Используйте интервальные функции вместо одноэлементных

Из книги автора

Совет 5. Используйте интервальные функции вместо одноэлементных Есть два вектора, v1 и v2. Как проще всего заполнить v1 содержимым второй половины v2? Только не надо мучительно размышлять над тем, что считать «половиной» при нечетном количестве элементов в v2. Просто


Совет 17. Используйте «фокус с перестановкой» для уменьшения емкости

Из книги автора

Совет 17. Используйте «фокус с перестановкой» для уменьшения емкости Предположим, вы пишете программу для нового телешоу «Бешеные деньги». Информация о потенциальных участниках хранится в векторе:class Contestant {...};vector<Contestant> contestants;При объявлении набора участников заявки


Совет 27. Используйте distance и advance для преобразования const_iterator в iterator

Из книги автора

Совет 27. Используйте distance и advance для преобразования const_iterator в iterator Как было сказано в совете 26, некоторые функции контейнеров, вызываемые с параметрами-итераторами, ограничиваются типом iterator; const_iterator им не подходит. Что же делать, если имеется const_iterator и вы хотите вставить


Совет 43. Используйте алгоритмы вместо циклов

Из книги автора

Совет 43. Используйте алгоритмы вместо циклов Каждому алгоритму передается по крайней мере одна пара итераторов, определяющих интервал объектов для выполнения некоторой операции. Так, алгоритм min_element находит минимальное значение в интервале, алгоритм accumulate вычисляет


Совет 44. Используйте функции контейнеров вместо одноименных алгоритмов

Из книги автора

Совет 44. Используйте функции контейнеров вместо одноименных алгоритмов Некоторые контейнеры содержат функции, имена которых совпадают с именами алгоритмов STL. Так, в ассоциативных контейнерах существуют функции count, find, lower_bound, upper_bound и equal_range, а в контейнере list


4. Обобщения

Из книги автора

4. Обобщения Очередным видом связи классов сущностей между собой, который мы рассмотрим, является связь вида обобщение. Это также нерекурсивный вид связи.Итак, связь типа обобщение реализуется как взаимосвязь одного родительского класса сущностей с несколькими


Накопление (Accumulate)

Из книги автора

Накопление (Accumulate) template ‹class InputIterator, class T›T accumulate(InputIterator first, InputIterator last, T init);template ‹class InputIterator, class T, class BinaryOperation›T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op);accumulate подобен оператору APL reduction и функции Common Lisp reduce, но он избегает трудности определения результата


8.13. Функция setitimer(): задание интервальных таймеров

Из книги автора

8.13. Функция setitimer(): задание интервальных таймеров Функция setitimer() является обобщением системного вызова alarm(). Она планирует доставку сигнала по истечении заданного промежутка времени.С помощью функции setitimer() можно создавать таймеры трех типов.? ITIMER_REAL. По истечении


Алгоритм for_each()

Из книги автора

Алгоритм for_each() template class InputIterator, class Function Functionfor_each( InputIterator first,InputIterator last, Function func );for_each() применяет объект-функцию func к каждому элементу в диапазоне [first,last). func не может изменять элементы, поскольку итератор записи не гарантирует поддержки присваивания. Если же модификация