C++ accumulate

Date: 2019-06-16Last modified: 2024-11-02

Table of contents

Folding
Possible output

Folding

Folding (or reduction) is the process of combining a collection of values together to generate a reduced number of results. Most of the time, we are speaking about a single result. Folding abstracts the process of iterating over structures that are recursive in nature.

The std::accumulate function is a perfect example of folding functionality because it combines values in the collection. Take a look at the following simple example:

std::vector<double> elems{1.1, 2.2, 3.3, 4.4, 5.5};
auto sum = std::accumulate(elems.begin(), elems.end(), 0);

The last argument to the function is the accumulator. This is the initial value that should be used as the previous value for the first element of the collection.

⚡ Tip

A better alternative to the std::accumulate function is the std::reduce function. reduce() is similar to accumulate(), except it doesn’t keep the order of the operation; that is, it doesn’t necessarily process the collection elements sequentially. You can pass an execution policy to the std::reduce function and change its behavior, say, to processing elements in parallel.

☢ Warning

Though std::reduce seems faster compared to std::accumulate, you should be careful when using it with non-commutative binary operations.

☕ Information

Folding and recursion go hand in hand. Recursive functions also solve a problem by decomposing it into smaller tasks and solving them one by one.

template <typename T>
struct my_multiplies {
  constexpr T operator()( const T &lhs, const T &rhs ) const
  {
    return lhs * rhs;
  }
};

  vector<int> v{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

  int sum1     = accumulate( v.begin(), v.end(), 0 );
  int sum2     = accumulate( v.begin(), v.end(), 0, plus<int>() );
  int product1 = accumulate( v.begin(), v.end(), 1, multiplies<int>() );
  int product2 = accumulate( v.begin(), v.end(), 1, my_multiplies<int>() );

  cout << "sum1: " << sum1 << "\nsum2: " << sum2 << '\n'
       << "product1: " << product1 << "\nproduct2: " << product2 << '\n';

  auto dash_fold = []( string a, int b ) { return std::move( a ) + '-' + to_string( b ); };

  // Concatena separando por traço
  // 1-2-3-4-5-6-7-8-9-10
  string s = accumulate(
      next( v.begin() ), // pula um elemento
      v.end(),
      to_string( v[0] ), // começa com o primeiro elemento
      dash_fold );

  cout << "dash-separated string: " << s << '\n';

  // Concatena separando por traço (de trás pra frente)
  // 10-9-8-7-6-5-4-3-2-1
  string rs = accumulate(
      next( v.rbegin() ),    // pula um elemento
      v.rend(),
      to_string( v.back() ), // começa pelo último
      dash_fold );

  cout << "dash-separated string (right-folded): " << rs << '\n';

  // twitter @SimonToth83
  // std::inclusive_scan and std::exclusive_scan scan are std::reduce variants that instead of producing a single value,
  // emit each partial result. For inclusive_scan the first output value already includes the first input element.

  vector<int> scan1;
  inclusive_scan( v.begin(), v.end(), back_inserter( scan1 ) );
  // implicit init == int{} == 0
  cout << "scan1: ";
  for( const auto &i : scan1 ) {
    cout << i << " ";
  }

  vector<int> scan2;
  exclusive_scan( v.begin(), v.end(), back_inserter( scan2 ), 100 );
  // init is mandatory for exclusive_scan
  cout << "\nscan2: ";
  for( const auto &i : scan2 ) {
    cout << i << " ";
  }

  vector<int> scan3;
  exclusive_scan( v.begin(), v.end(), back_inserter( scan3 ), 1000, multiplies<>{} );
  cout << "\nscan3: ";
  for( const auto &i : scan3 ) {
    cout << i << " ";
  }

  cout << endl;

Possible output

sum1: 55
sum2: 55
product1: 3628800
product2: 3628800
dash-separated string: 1-2-3-4-5-6-7-8-9-10
dash-separated string (right-folded): 10-9-8-7-6-5-4-3-2-1
scan1: 1 3 6 10 15 21 28 36 45 55 
scan2: 100 101 103 106 110 115 121 128 136 145 
scan3: 1000 1000 2000 6000 24000 120000 720000 5040000 40320000 362880000