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

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

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：
In pics: 11th China-Central Asia Cooperation Forum in Yinchuan,
Chongqing's secret sauce to internet fame
China's Zheng Qinwen claims WTA 500 Pan Pacific Open title
Protecting biodiversity in power facility projects
Hong Kong-Zhuhai-Macao Bridge accelerates integrated development
Fashion show staged at Jiefang North Road in China's Tianjin
U.S. Black women face delays, disparities in breast cancer care,
Wondrous Xinjiang: Populus euphratica forests attract tourists w
Chinese shipbuilders seek transition towards clean energy
China beats Vietnam to win 2024 CFA Team China Int'l Women's Foo

Comment list

Comment add: Name：　Check：