алгоритма accumulate() с четырьмя аргументами, позволяющая задавать используемую операцию.
template<class In, class T, class BinOp>
T accumulate(In first, In last, T init, BinOp op)
{
while (first!=last) {
init = op(init, *first);
++first;
}
return init;
}
Здесь можно использовать любую бинарную операцию, получающую два аргумента, тип которых совпадает с типом аккумулятора. Рассмотрим пример.
array<double,4> a = { 1.1, 2.2, 3.3, 4.4 }; // см. раздел 20.9
cout << accumulate(a.begin(),a.end(), 1.0, multiplies<double>());
Этот фрагмент кода выводит на печать число 35.1384, т.е. 1.0*1.1*2.2*3.3*4.4 (1.0 — начальное значение). Бинарный оператор multiplies<double>(), передаваемый как аргумент, представляет собой стандартный объект-функцию, выполняющий умножение; объект-функция multiplies<double> перемножает числа типа double, объект-функция multiplies<int> перемножает числа типа int и т.д. Существуют и другие бинарные объекты-функции: plus (сложение), minus (вычитание), divides и modulus (вычисление остатка от деления). Все они определены в заголовке <functional> (раздел Б.6.2).
Обратите внимание на то, что для умножения чисел с плавающей точкой естественным начальным значением является число 1.0. Как и в примере с алгоритмом sort() (см. раздел 21.4.2), нас часто интересуют данные, хранящиеся в объектах классов, а не обычные данные встроенных типов. Например, мы могли бы вычислить общую стоимость товаров, зная стоимость их единицы и общее количество.
struct Record {
double unit_price;
int units; // количество проданных единиц
// ...
};
Мы можем поручить какому-то оператору в определении алгоритма accumulate извлекать данные units из соответствующего элемента класса Record и умножать на значение аккумулятора.
double price(double v,const Record& r)
{
return v + r.unit_price * r.units; // вычисляет цену
// и накапливает итог
}
void f(const vector<Record>& vr)
{
double total = accumulate(vr.begin(),vr.end(),0.0,price);
// ...
}
Мы поленились и использовали для вычисления цены функцию, а не объект-функцию, просто, чтобы показать, что так тоже можно делать. И все же мы рекомендуем использовать объекты функции в следующих ситуациях.
• Если между вызовами необходимо сохранять данные.
• Если они настолько короткие, что их можно объявлять подставляемыми (по крайней мере, для некоторых примитивных операций).
В данном случае мы могли бы использовать объект-функцию, руководствуясь вторым пунктом этого списка.
ПОПРОБУЙТЕ
Определите класс vector<Record>, проинициализируйте его четырьмя записями по своему выбору и вычислите общую стоимость, используя приведенные выше функции.
21.5.3. Алгоритм inner_product
Возьмите два вектора, перемножьте их элементы попарно и сложите эти произведения. Результат этих вычислений называется скалярным произведением (inner product) двух векторов и является наиболее широко используемой операцией во многих областях (например, в физике и линейной алгебре; раздел 24.6).
Если вы словам предпочитаете программу, то прочитайте версию этого алгоритма из библиотеки STL.
template<class In, class In2, class T>
T inner_product(In first, In last, In2 first2, T init)
// примечание: вычисляет скалярное произведение двух векторов
{
while(first!=last) {
init = init + (*first) * (*first2); // перемножаем
// элементы
++first;
++first2;
}
return init;
}
Эта версия алгоритма обобщает понятие скалярного произведения для любого вида последовательностей с любым типом элементов. Рассмотрим в качестве примера биржевой индекс. Он вычисляется путем присваивания компаниям неких весов. Например, индекс Доу–Джонса Alcoa на момент написания книги составлял 2,4808. Для того чтобы определить текущее значение индекса, умножаем цену акции каждой компании на ее вес и складываем полученные результаты. Очевидно, что такой индекс представляет собой скалярное произведение цен и весов. Рассмотрим пример.
// вычисление индекса Доу-Джонса
vector<double> dow_price; // цена акции каждой компании
dow_price.push_back(81.86);
dow_price.push_back(34.69);
dow_price.push_back(54.45);
// ...
list<double> dow_weight; // вес каждой компании в индексе
dow_weight.push_back(5.8549);
dow_weight.push_back(2.4808);
dow_weight.push_back(3.8940);
// ...
double dji_index = inner_product( // умножаем пары (weight,value)
// и суммируем
dow_price.begin(),dow_price.end(),dow_weight.begin(),0.0);
cout << "Значение DJI" << dji_index << 'n';
Обратите внимание на то, что алгоритм inner_product() получает две последовательности. В то же время он получает только три аргумента: у второй последовательности задается только начало. Предполагается, что вторая последовательность содержит не меньше элементов, чем первая. В противном случае мы получим сообщение об ошибке во время выполнения программы. В алгоритме inner_product() вторая последовательность вполне может содержать больше элементов, чем первая; лишние элементы просто не будут использоваться.
Две последовательности не обязательно должны иметь одинаковый тип или содержать элементы одинаковых типов. Для того чтобы проиллюстрировать это утверждение, мы записали цены в объект класса vector, а веса — в объект класса list.
21.5.4. Обобщение алгоритма inner_product()
Алгоритм inner_product() можно обобщить так же, как и алгоритм accumulate(). Однако в отличие от предыдущего обобщения алгоритму inner_product() нужны еще два аргумента: первый — для связывания аккумулятора с новым значением, точно так же как в алгоритме accumulate(), а второй — для связывания с парами значений.
template<class In,class In2,class T,class BinOp,class BinOp2 >
T inner_product(In first,In last,In2 first2,T init,BinOp op,BinOp2 op2)
{
while(first!=last) {
init = op(init,op2(*first,*first2));
++first;
++first2;
}
return init;
}
В разделе 21.6.3 мы еще вернемся к примеру с индексом Доу–Джонса и используем обобщенную версию алгоритма inner_product() как часть более элегантного решения задачи.
21.6. Ассоциативные контейнеры
После класса vector вторым по частоте использования, вероятно, является стандартный контейнер map, представляющий собой упорядоченную последовательность пар (ключ,значение) и позволяющий находить значение по ключу; например, элемент my_phone_book["Nicholas"] может быть телефонным номером Николаса. Единственным достойным конкурентом класса map по популярности является класс unordered_map (см. раздел 21.6.4), оптимизированный для ключей, представляющих собой строки. Структуры данных, аналогичные контейнерам map и unordered_map, известны под разными названиями, например ассоциативные массивы (associative arrays), хеш-таблицы (hash tables) и красно-черные