C++ Coding Reference: std::accumulate() and examples

Time：2020-09-17 14:37:27
Class：Weblog
Read：26

The Reduce in terms of Map-Reduce is often referring to reducing many values (vector) to a single value (scalar). In C++, the STL has a accumulate() method that allows you to reduce a vector/list to a single value by providing the initial value, and the reducer function.

The std::accumulate() is provided in C++ header numeric and it has the following template definition:

// FUNCTION TEMPLATE accumulate
template<class _InIt,
    class _Ty,
    class _Fn>
    _NODISCARD inline _Ty accumulate(const _InIt _First, const _InIt _Last, _Ty _Val, _Fn _Reduce_op)
    {   // return noncommutative and nonassociative reduction of _Val and all in [_First, _Last), using _Reduce_op
    _Adl_verify_range(_First, _Last);
    auto _UFirst = _Get_unwrapped(_First);
    const auto _ULast = _Get_unwrapped(_Last);
    for (; _UFirst != _ULast; ++_UFirst)
        {
        _Val = _Reduce_op(_Val, *_UFirst);
        }
 
    return (_Val);
    }

// FUNCTION TEMPLATE accumulate
template<class _InIt,
	class _Ty,
	class _Fn>
	_NODISCARD inline _Ty accumulate(const _InIt _First, const _InIt _Last, _Ty _Val, _Fn _Reduce_op)
	{	// return noncommutative and nonassociative reduction of _Val and all in [_First, _Last), using _Reduce_op
	_Adl_verify_range(_First, _Last);
	auto _UFirst = _Get_unwrapped(_First);
	const auto _ULast = _Get_unwrapped(_Last);
	for (; _UFirst != _ULast; ++_UFirst)
		{
		_Val = _Reduce_op(_Val, *_UFirst);
		}

	return (_Val);
	}

By default, if the reduce op (or Reducer function) is not specified, the accumulator will use a plus operator. For example,

1 2	vector<int> nums({1, 2, 3, 4, 5}); cout << std::accumulate(begin(nums), end(nums), 0); // output 15, which is 1+2+3+4+5

vector<int> nums({1, 2, 3, 4, 5});
cout << std::accumulate(begin(nums), end(nums), 0); // output 15, which is 1+2+3+4+5

The first and second parameter specifies the range of the vector, which you can pass begin() and end() iterators of a C++ vector for example. The third parameter of the accumulate() is the initial value that will be accumulated from.

Default reducer can be expressed explicitly by the lambda function, for example,

vector<int> nums({1, 2, 3, 4, 5});
cout << std::accumulate(begin(nums), end(nums), 0, [](auto &a, auto &b) {
    return a + b;
}); // output 15, which is 1+2+3+4+5

vector<int> nums({1, 2, 3, 4, 5});
cout << std::accumulate(begin(nums), end(nums), 0, [](auto &a, auto &b) {
    return a + b;
}); // output 15, which is 1+2+3+4+5

We can also use other pre-defined reducer, for example, std::multiplies which is defined in header xstddef.

// STRUCT TEMPLATE multiplies
template<class _Ty = void>
    struct multiplies
    {   // functor for operator*
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty first_argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty second_argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty result_type;
 
    constexpr _Ty operator()(const _Ty& _Left, const _Ty& _Right) const
        {   // apply operator* to operands
        return (_Left * _Right);
        }
    };

// STRUCT TEMPLATE multiplies
template<class _Ty = void>
	struct multiplies
	{	// functor for operator*
	_CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty first_argument_type;
	_CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty second_argument_type;
	_CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty result_type;

	constexpr _Ty operator()(const _Ty& _Left, const _Ty& _Right) const
		{	// apply operator* to operands
		return (_Left * _Right);
		}
	};

An example for the integer factorial e.g. 5! = 5x4x3x2x1 = 120. Remember to set the initial reducer value to 1 instead of 0.

1
2
3

vector<int> nums({1, 2, 3, 4, 5});
// output 120, which is 1*2*3*4*5
cout << std::accumulate(begin(nums), end(nums), 1, std::multiplies<int>());

vector<int> nums({1, 2, 3, 4, 5});
// output 120, which is 1*2*3*4*5
cout << std::accumulate(begin(nums), end(nums), 1, std::multiplies<int>());

C++ accumulate() the string

We can use accumulate() to apply to strings, however, the initial value has to be string explicitly. By default, empty string with double quotes in C++ is treated as const char * which is not desired.

1
2
3

string s = "Hello";
string ss = std::accumulate(begin(s), end(s), string(""));
std::cout << ss.c_str(); // Hello

string s = "Hello";
string ss = std::accumulate(begin(s), end(s), string(""));
std::cout << ss.c_str(); // Hello

The string(“”) can also be expressed as string{}. Another example with the lambda reducer function.

string s = "Hello";
string ss = std::accumulate(begin(s), end(s), string{}, [](auto &a, auto &b) {
   return a + b + ",";
});
std::cout << ss.c_str(); // H,e,l,l,o,

string s = "Hello";
string ss = std::accumulate(begin(s), end(s), string{}, [](auto &a, auto &b) {
   return a + b + ",";
});
std::cout << ss.c_str(); // H,e,l,l,o,

We are using the auto to let the compiler deduce the type, but if you want to explicitly specify the type in the reducer function, that is OK:

1
2
3

string ss = std::accumulate(begin(s), end(s), string{}, [](const string &a, const char &b) {
    return a + b + ",";
});

string ss = std::accumulate(begin(s), end(s), string{}, [](const string &a, const char &b) {
	return a + b + ",";
});

The C++ std::accumulate performs a left-fold meaning that the values in the vector are reduced from left to right. To reduce in right-fold i.e. from right to left, you can either reverse the argument vector, or pass the reverse iterators.

–EOF (The Ultimate Computing & Technology Blog) —

Recommend：
Summits set epoch-making milestone in history of China-Arab ties
In the face of COVID-19 pandemic, China and Arab countries have
15 Macao residents qualify as candidates for deputies to nationa
Study finds genetic solution to pre-harvest sprouting in rice, w
Bodybuilders dying as coaches, judges encourage extreme measures
Malta's Marsaskala, China's Dujiangyan sign sister city agreemen
U.S. mortgage applications continue slide amid surging interest
Russian, UAE presidents discuss bilateral cooperation over phone
Hate crimes in U.S. Los Angeles County rise to highest level sin
Chinese mainland reports 4,031 new local confirmed COVID-19 case

Comment list

Comment add: Name：　Check：