C++ для начинающих. Численный алгоритм accumulate

Опубликовано 20.10.2012 | Автор: admin

Один из немногочисленных численных алгоритмов в STL — это accumulate. По названию можно судить, что он аккумулирует значения. Но и что такое аккумулирование значений в то же время как-то не понятно. Этот алгоритм работает с численными последновательностями (векторы, массивы, списки и другое, одержащее числовые значения). Задача этого алгоритма выпоплнять какую-то одну операцию над всеми числами, собранными в таких структурах, которые можно обходить как массивы. Операцией может быть сложение, умножение, деление всех элементов (и более сложной). Смысл в том, что для каждого следующего элемента применяется операция к последнему результату.

Точка отсчёта, она же у меня сейчас была названа последним результатом, задаётся, если её нет, обычно нулём. Вот пример суммирования всех элементов:

[2 7 8 9]
0 + 2 = 2 ---> результат 2
2 + 7 = 9 ---> результат 9
9 + 8 = 17 ---> результат 17
17 + 9 = 26 ---> результат 26
---------------------
Результат суммирования всех элементов = 26

accumulate по умолчанию суммирует все элементы из последовательности.
Для использования accumulate нужно делать #include <numeric>

Вот пример:

//C++	Листинг #1.1		accumulate		сумма всех элементов
#include <vector>
#include <iostream>
#include <numeric>

using namespace std;

int main(){
   setlocale(LC_ALL, "");

   vector<int> v = {2, 7, 8, 9};

   int sum = accumulate(v.begin(), v.end(), 0);			//Здесь ноль — это либо число, к которому нужно добавить результат сложения.
   cout << "Сумма элементов в массиве v == " << sum << '\n';
}

//C++ Листинг #1.1 accumulate сумма всех элементов

#include <vector>

#include <iostream>

#include <numeric>

using namespace std;

int main(){

setlocale(LC_ALL, "");

vector<int> v = {2, 7, 8, 9};

int sum = accumulate(v.begin(), v.end(), 0); //Здесь ноль — это либо число, к которому нужно добавить результат сложения.

cout << "Сумма элементов в массиве v == " << sum << '\n';

}

Поскольку для обычного сложения переменную-результат инициализируют нулём, то точка отсчёта у нас ноль, но на место этого нуля можно подставлять какой-то вычисленный результат, если нужно просуммировать тот результат с полученной суммой (или другим результатом accumulate).

Всё хранящее набор численных значений, что можно обойти как массивы, может переварить accumulate. Например, set в C++ реализуется с помощью дерева (а деревья и массивы это совершенно разные по устройству структуры), а обойти его можно как массив, т. е. accumulate влёгкую может справиться с set:

//C++	Листинг #1.2		accumulate		сумма всех элементов
#include <set>
#include <iostream>
#include <numeric>

using namespace std;

int main(){
   setlocale(LC_ALL, "");

   set<int> s = {2, 7, 8, 9};

   int sum = accumulate(s.begin(), s.end(), 0);
   cout << "Сумма элементов в множестве s == " << sum << '\n';
}

//C++ Листинг #1.2 accumulate сумма всех элементов

#include <set>

#include <iostream>

#include <numeric>

using namespace std;

int main(){

setlocale(LC_ALL, "");

set<int> s = {2, 7, 8, 9};

int sum = accumulate(s.begin(), s.end(), 0);

cout << "Сумма элементов в множестве s == " << sum << '\n';

}

При работе с классическими массивами (теми, что объявляются с квадратными скобками) может быть необходимо использовать арифметику указателей. Если имя массива неявно преобразуется к указателю на первый элемент, то становится невозможно выяснить границу массива:

//C++	Листинг #1.3		accumulate		сумма всех элементов в массиве
#include <iostream>
#include <numeric>

using namespace std;

int foo(int *arr, const int N, const int value){
//   return accumulate(begin(arr), end(arr), value);  //ОШИБКА!
   return accumulate(arr, arr+N, value);          //НАДО ТАК!
}

int main(){
   setlocale(LC_ALL, "");

   int arr1[] = {2, 7, 8, 9};
   int arr2[] = {1, 2, 3, 4};

   int sum1 = accumulate(begin(arr1), end(arr1), 0);    //OK, можно выяснить на уровне итераторов границы массива
   int sum2 = foo(arr2, end(arr2) - begin(arr2), sum1);

   cout << "Сумма всех значений arr1 и arr2 == " << sum2 << '\n';
}

//C++ Листинг #1.3 accumulate сумма всех элементов в массиве

#include <iostream>

#include <numeric>

using namespace std;

int foo(int *arr, const int N, const int value){

// return accumulate(begin(arr), end(arr), value); //ОШИБКА!

return accumulate(arr, arr+N, value); //НАДО ТАК!

}

int main(){

setlocale(LC_ALL, "");

int arr1[] = {2, 7, 8, 9};

int arr2[] = {1, 2, 3, 4};

int sum1 = accumulate(begin(arr1), end(arr1), 0); //OK, можно выяснить на уровне итераторов границы массива

int sum2 = foo(arr2, end(arr2) - begin(arr2), sum1);

cout << "Сумма всех значений arr1 и arr2 == " << sum2 << '\n';

}

Смысл работы #1.3 — это суммирование сумм. Этот код мог выглядет так:

//C++	Листинг #1.4		accumulate		сумма всех элементов в массиве
#include <iostream>
#include <numeric>

using namespace std;

int main(){
   setlocale(LC_ALL, "");

   int arr1[] = {2, 7, 8, 9};
   int arr2[] = {1, 2, 3, 4};

   int sum1 = accumulate(begin(arr1), end(arr1), 0);    //OK, можно выяснить на уровне итераторов границы массива
   int sum2 = accumulate(begin(arr2), end(arr2), sum1);    //Добавляем к существующей сумме (sum1) вычисляемую сумму (sum2)


   cout << "Сумма всех значений arr1 и arr2 == " << sum2 << '\n';
}

//C++ Листинг #1.4 accumulate сумма всех элементов в массиве

#include <iostream>

#include <numeric>

using namespace std;

int main(){

setlocale(LC_ALL, "");

int arr1[] = {2, 7, 8, 9};

int arr2[] = {1, 2, 3, 4};

int sum1 = accumulate(begin(arr1), end(arr1), 0); //OK, можно выяснить на уровне итераторов границы массива

int sum2 = accumulate(begin(arr2), end(arr2), sum1); //Добавляем к существующей сумме (sum1) вычисляемую сумму (sum2)

cout << "Сумма всех значений arr1 и arr2 == " << sum2 << '\n';

}

#1.3 демонстрирует классическую ошибку, когда указатель приравнивают к массиву, а #1.4 показывает, что должен был выполнить #1.3. Вообще на этих двух примерах можно сильно не заморачиваться, важно понимать, что алгоритм по умолчанию суммирует значения в последовательности и прибавляет их к тому значению, которое ему даётся нами в третий аргумент.

Большинство алгоритмов STL в C++ настраиваемые (accumulate среди них), что значит, что вместо суммирования можно выполнять любую другую операцию к последовательности.

Чтобы использовать в accumulate операцию по своему усмотрению, можно использовать функцию-передикат, функтор, лямбда-выражение (всё, что можно использовать как функции).

Тем, кто не знаком с функторами и лямбда-выражениями, проще всего использовать предикатные функции. Предикатными функциями обычно называют такие функции, которые возвращают булевы значения (т. е. истина или ложь), результаты которых используются алгоритмами. Но это вообще такие функции, которые пишут для использования алгоритмами.

//C++	Листинг #2.1		accumulate		умножение
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

int foo(int x, int y){		//Предикатная функция, предназначенная для умножения
   return x * y;
}

int main(){
   setlocale(LC_ALL, "");

   vector<int> v= {2, 7, 8, 9};

   if (! v.empty()){
      int result = accumulate(begin(v), end(v), 1, foo);    //OK, можно выяснить на уровне итераторов границы массива
      cout << "Произведение всех значений v == " << result << '\n';
   } else {
      cout << "Нечего умножать!";
   }
}

//C++ Листинг #2.1 accumulate умножение

#include <iostream>

#include <numeric>

#include <vector>

using namespace std;

int foo(int x, int y){ //Предикатная функция, предназначенная для умножения

return x * y;

}

int main(){

setlocale(LC_ALL, "");

vector<int> v= {2, 7, 8, 9};

if (! v.empty()){

int result = accumulate(begin(v), end(v), 1, foo); //OK, можно выяснить на уровне итераторов границы массива

cout << "Произведение всех значений v == " << result << '\n';

} else {

cout << "Нечего умножать!";

}

Поскольку умножение на ноль даёт ноль, точка отсчёта не должны быть нулём, поэтому делаем её единицей. Но если точка отсчёта единица, то результат умножений для пустого массива окажется единицей, поэтому контроллируем этот момент. Да ещё и за типами нужно следить. Слишком много умножений в int могут не поместиться. Когда алгоритм обходит последовательность, он использует два значения (чтобы сделать умножение, нужно минимум два значения), поэтому предикатная функция должна принимать два параметра (первый — это текущий результат, а второй — это очередной элемент последовательности). Вместо умножения может быть любое другое арифметическое действие.

С введением в C++ лямбда-выражений стало модно использовать лямбда-выражения. В большинстве случаев, когда нужно немного кода, они на самом деле удобны, хоть и не очень могут быть понятны поначалу.

//C++	Листинг #2.2		accumulate		умножение
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

int main(){
   setlocale(LC_ALL, "");

   vector<int> v= {2, 7, 8, 9};

   if (! v.empty()){
      int result = accumulate(begin(v), end(v), 1, [](int x, int y){ return x * x; });    //OK, можно выяснить на уровне итераторов границы массива
      cout << "Произведение всех значений v == " << result << '\n';
   } else {
      cout << "Нечего умножать!";
   }
}

//C++ Листинг #2.2 accumulate умножение

#include <iostream>

#include <numeric>

#include <vector>

using namespace std;

int main(){

setlocale(LC_ALL, "");

vector<int> v= {2, 7, 8, 9};

if (! v.empty()){

int result = accumulate(begin(v), end(v), 1, [](int x, int y){ return x * x; }); //OK, можно выяснить на уровне итераторов границы массива

cout << "Произведение всех значений v == " << result << '\n';

} else {

cout << "Нечего умножать!";

}

Кроме лямбда выражений могут быть использованы функторы. Некоторые функторы для арифметических операций встроенны в язык: plus (для сложения), minus (для вычитания), divides (для деления). Чтобы включить эти функторы, нужно задействовать #include <functional>. Конечно, там не будет всех возможных операций, но на то нам и руки, чтоб если чего не было, кодить: если готового функтора нет, надо его написать.

//C++	Листинг #2.3		accumulate		умножение
#include <iostream>
#include <numeric>
#include <vector>
#include <functional>

using namespace std;

int main(){
   setlocale(LC_ALL, "");

   vector<int> v= {2, 7, 8, 9};

   if (! v.empty()){
      int result = accumulate(begin(v), end(v), 1, multiplies<int>());    //Использовали встроенный в С++ функтор для произведения
      cout << "Произведение всех значений v == " << result << '\n';
   } else {
      cout << "Нечего умножать!";
   }
}

//C++ Листинг #2.3 accumulate умножение

#include <iostream>

#include <numeric>

#include <vector>

#include <functional>

using namespace std;

int main(){

setlocale(LC_ALL, "");

vector<int> v= {2, 7, 8, 9};

if (! v.empty()){

int result = accumulate(begin(v), end(v), 1, multiplies<int>()); //Использовали встроенный в С++ функтор для произведения

cout << "Произведение всех значений v == " << result << '\n';

} else {

cout << "Нечего умножать!";

}

Одна из ошибок, способных возникнуть при использовании accumulate — это ошибка с приведениями типов. Для компилятора, конечно, оно не ошибка, а так и задумано, а для людей, которые видят не те результаты, может выглядеть как ошибка:

//C++	Листинг #3.1		accumulate		ошибка с типами
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

int main(){
   setlocale(LC_ALL, "");

   vector<double> v= {2.7, 7};   // (2.7 + 7) = 9.7
   cout << accumulate(v.begin(), v.end(), 0) << '\n';  // 9 (а ждём 9.7)
}

//C++ Листинг #3.1 accumulate ошибка с типами

#include <iostream>

#include <numeric>

#include <vector>

using namespace std;

int main(){

setlocale(LC_ALL, "");

vector<double> v= {2.7, 7}; // (2.7 + 7) = 9.7

cout << accumulate(v.begin(), v.end(), 0) << '\n'; // 9 (а ждём 9.7)

}

C++ частенько автоматически преобразует типы. Из-за таких преобразований можно ловить такие результаты, что 5/2 = 2, а не 2.5. Наверняка вы сталкивались с этим делом, когда только начинали писать на C++. В #2.4 происходит именно такое действие, что вычисленный результат аккумулейтом, имеющий не целый тип, преобразывается самим аккумулейтом в целочисленный. Точнее, так работают шаблоны. А связано это с типом стартового значения: у нуля тип — целое число. accumulate преобразует свой результат именно к тому типу, который у значения-старта (в данном случае к типу нуля). Чтобы всё работало правильно, если имеем дело с нецелыми числами, то тип нулю нужно задать подходящий (не меньшей вместимости, чем тип у значений из последовательности). Делать это можно несколькими способами, я остановлюсь только на одном. Смысл только в том, что тип нулю нужно перевести в такой, какой мы хотим от результатов работы accumulate

//C++	Листинг #3.2		accumulate		исправление ошибки с типами
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

int main(){
   setlocale(LC_ALL, "");

   vector<double> v= {2.7, 7};   // (2.7 + 7) = 9.7
   cout << accumulate(v.begin(), v.end(), static_cast<double>(0)) << '\n';  // Теперь всё ОК
}

//C++ Листинг #3.2 accumulate исправление ошибки с типами

#include <iostream>

#include <numeric>

#include <vector>

using namespace std;

int main(){

setlocale(LC_ALL, "");

vector<double> v= {2.7, 7}; // (2.7 + 7) = 9.7

cout << accumulate(v.begin(), v.end(), static_cast<double>(0)) << '\n'; // Теперь всё ОК

}

accumulate — это прежде всего численный алгоритм, поэтому его прямое предназнычение — аккуммулирование результата из набора чисел. Но переварить он может не только численные последовательности, но и вообще любые, что можно обходить как массивы. Например, можно сложить две строки:

//C++	Листинг #4.1		accumulate		нетипичные применения		конкатенация строк
#include <iostream>
#include <numeric>
#include <string>

using namespace std;

int main(){
   setlocale(LC_ALL, "");

   string S1 = "hello";
   string S2 = "world";
   cout << accumulate(S1.begin(), S1.end(), S2);
}

//C++ Листинг #4.1 accumulate нетипичные применения конкатенация строк

#include <iostream>

#include <numeric>

#include <string>

using namespace std;

int main(){

setlocale(LC_ALL, "");

string S1 = "hello";

string S2 = "world";

cout << accumulate(S1.begin(), S1.end(), S2);

}

С помощью предикатной функции можно посчитать сколько раз встречается символ в строке:

//C++	Листинг #4.2		accumulate		нетипичные применения		считаем число символов
#include <iostream>
#include <numeric>
#include <string>

using namespace std;

int my_pred(int sum, const char ch){

   if ('o' == ch){      //считаем число о
      sum++;
   };
   return sum;
}

int main(){
   setlocale(LC_ALL, "");

   string S1 = "hello, mister coder";
   cout << accumulate(S1.begin(), S1.end(), 0, my_pred); //o встретилась 2 раза
}

//C++ Листинг #4.2 accumulate нетипичные применения считаем число символов

#include <iostream>

#include <numeric>

#include <string>

using namespace std;

int my_pred(int sum, const char ch){

if ('o' == ch){ //считаем число о

sum++;

};

return sum;

}

int main(){

setlocale(LC_ALL, "");

string S1 = "hello, mister coder";

cout << accumulate(S1.begin(), S1.end(), 0, my_pred); //o встретилась 2 раза

}

По #4.2 можно легко увидеть, что первое значение в обработке accumulate — это что-то вроде переменной-результата, а во второе значение попадают значения из обходимой последовательности. Возможно, это поможет понять общий принцип работы алгоритма, но практиковать такое не нужно.

У меня есть ещё один пример, который комбинирует строку и числа: в строке только цифры, а нужно почитать сумму всех цифр числа, представляемого строкой. Этот пример был взят из одного популярного форума, но как он работает, я не могу сказать, не хватает математических познаний, простите.

#include <numeric>
#include <iostream>

using namespace std;

int main(){
  string s = "78954";   //7 + 8 + 9 + 5 + 4 = 33
  int sum = accumulate(s.begin(),s.end(), '0' * -s.size()) ;
  cout << sum << '\n';
}

#include <numeric>

#include <iostream>

using namespace std;

int main(){

string s = "78954"; //7 + 8 + 9 + 5 + 4 = 33

int sum = accumulate(s.begin(),s.end(), '0' * -s.size()) ;

cout << sum << '\n';

}

Статья была обновлена 01.01.2022

Рубрика: Без рубрики

C++ для начинающих. Численный алгоритм accumulate

7 комментариев на «“C++ для начинающих. Численный алгоритм accumulate”»

Добавить комментарий Отменить ответ

Поиск

Последние темы

Случайная книга в электронном формате

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

Мета