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

  • 时间：2020-09-17 14:37:27
  • 分类：网络文摘
  • 阅读：97 次

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

// 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,

1
2
3
4

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.

1
2
3
4
5
6
7
8
9
10
11
12
13

// 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.

1
2
3
4
5

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) —

推荐阅读：
Using the Windows Hardware Tool to Error Checking and Optimize Y　 The Union Find (Disjoint Set) Implementation in Java/C++　 How to use the Leetcode’s Mock Interview Overview to Nail 　 Replace Harddrives when CrystalDiskInfo Shows Caution Health Sta　 Finding the Predecessor and Successor Node of a Binary Search Tr　 Algorithms to Detect Pattern of Length M Repeated K or More Time　 Using the stdout to debug print the solution in the leetcode con　 Tutorial: How to Set Up a API Load Balancer by Using CloudFlare 　 Introducing the Pancake Sorting Algorithm　 What Should You Blog About During the Pandemic and Beyond?　
评论列表
添加评论