Эффективное использование STL

Но в некоторых ситуациях возникает необходимость обработки интервальных данных по нестандартным критериям, и в таких случаях нужны более гибкие и универсальные средства, нежели алгоритмы 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!). Если начальное значение равно нулю, то результат всегда будет равен нулю — ноль, умноженный на любое число, остается нулем.