C++ STL数值算法（头文件numeric内）

accumulate

//版本1
template <typename InputIterator, typename T>
T accumulate(InputIterator first, InputIterator last, T init) {
	for ( ; first != last; ++first)
		init = init + *first;
	return init;
}

//版本2
template <typename InpurIterator, typename T, typename BinaryOperation>
T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation op) {
	for ( ; first != last; ++first)
		init = op(init, *first);
	return init;
}

       STL算法accumulate用来计算init和[first, last)内所有元素的总和，需要提供初始值init。accumulate有两个版本，版本2需要提供一个二元操作符，在C++11之前这个二元操作符不能是side effect的，C++11后取消了这一约束，只规定操作符不得使任何迭代器（包括尾后迭代器）失效，也不能修改所涉及范围内的任何元素。
对于版本2需要提供的二元操作符，可以是自定义的函数或仿函数，也可以使用标准库functional中给出的几种常用二元操作符，如加、减、乘、除、取模等。

#include <iostream>
#include <numeric>
#include <functional>
#include <vector>

int double_op(int x, int y) {
	return x+2*y;
}

template <typename T>
struct double_obj {
	T operator()(T x, T y) {
		return x+2*y;
	}
};

int main()
{
	using std::cout;
	using std::accumulate;
	using std::endl;
	std::vector<int> iv = {1, 2, 3, 4, 5};
	cout << accumulate(iv.begin(), iv.end(), 0) << endl;
	cout << accumulate(iv.begin(), iv.end(), 0, double_op) << endl;
	cout << accumulate(iv.begin(), iv.end(), 0, double_obj<int>()) << endl;
	cout << accumulate(iv.begin(), iv.end(), 0, std::minus<int>()) << endl;
	return 0;
}

 

iota (since C++11)

 

template <typename ForwardIterator, typename T>
void iota(ForwardIterator first, ForwardIterator last, T value) {
	while (first != last) {
		*first++ = value;
		++value;
	}
}

       iota用于填充容器指定范围内的元素，初始值由用户设定，每前进一步填充值也自增1。需要注意的是，该算法只能用于递增填充。

 

adjacent_difference

       该算法用来计算[first, last)中相邻元素的差值。算法有两种实现：

//版本1
template <typename InputIt, typename OutputIt>
OutputIt adjacent_difference(InputIt first, InputIt last, OutputIt d_first) {
	if (first == last)
		return d_first;
	typedef typename std::iterator_traits<InputIt>::value_type value_t;
	value_t acc = *first;
	*d_first = acc;
	while (++first != last) {
		value_t val = *first;
		*++d_first = val-acc;
		acc = std::move(val);
	}
	return ++d_first;
}

//版本2
template <typename InputIt, typename OutputIt, typename BinaryOperation>
OutputIt adjacent_difference(InputIt first, InputIt last, OutputIt d_first, BinaryOperation op) {
	if (first == last)
		return d_first;
	typedef typename std::iterator_traits<InputIt>::value_type value_t;
	value_t acc = *first;
	*d_first = acc;
	while (++first != last) {
		*++d_first = op(val, acc);
		acc = std::move(val);
	}
	return ++d_first;
}

       源码中的std::move函数是C++11新增，C++14改进后的函数，在这里的作用是将一个左值(val)转换为右值引用，并将此右值val的资源移动到一个左值(acc)中去，要注意的是，完成std::move后，val将不再拥有资源，即val的内容被移动到了acc中，此时val不拥有任何资源。关于std::move的详述参见另一篇博文。
       由源码可知，算法adjacent_difference将*first赋值给*d_first，并针对[first+1, last)内的每个迭代器i，将*i-*(i-1)赋值给*d_first+((i-first))。如果需要原地运算，只需要令d_first=first。在这种情况下，这会改变原容器内元素的值。第二版本由外界提供二元操作，将op(*i, *(i-1))的运算结果赋值给*(d_first+(i-first))。
       这种“存储第一元素的值，然后存储后继元素的差值”的做法很有用，因为这么一来就有足够的信息可以重建输入区间的原始内容（因为第一元素不变），这便是加解密的基础思想。例如，如果加法与减法的定义与常规相同，那么adjacent_difference与partial_sum互为逆运算。即，如果对区间值1,2,3,4,5运用adjacent_difference算法，得到的结果是1,1,1,1,1，再对此结果执行partial_sum，便会获得原始区间1,2,3,4,5。

#include <iostream>
#include <vector>
#include <numeric>

int main()
{
	std::vector<int> iv1 = {1, 2, 3, 4, 5};
	std::vector<int> iv2(5, 0);//iv2的大小不得小于iv1的大小，否则得不到预期结果
	std::adjacent_difference(iv.begin(), iv.end, iv2.begin());
	for (auto &x : iv2)
		std::cout << x << " ";
	std::cout << std::endl;
	for (auto &x : iv)
		std::cout << x << " ";
	std::cout << std::endl;


	std::adjacent_difference(iv.begin(), iv.end(), iv.begin());
	for (auto &x : iv)
		std::cout << x << " ";
	std::cout << std::endl;
	return 0;
}
partial_sum
//版本1
template <typename InputIt, tpyename OutputIt>
OutputIt partial_sum(InputIt first, InputIt last, Output d_first) {
	if (first == last)
		return d_first;
	typename std::iterator_traits<InputIt>::value_type sum = *first;
	*d_first = sum;
	while (++first != last) {
		sum = sum + *first;
		*++d_first = sum;
	}
	return ++d_first;
}

//版本2
template <typename InputIt, typename OutputIt, typename BinaryOperation>
OutputIt partial_sum(InputIt first, InputIt last, Output d_first, BinaryOperation op) {
	if (first == last)
		return d_first;
	typename std::iterator_traits<InputIt>::value_type sum = *first;
	*d_first = sum;
	while (++first != last) {
		sum = op(sum, *first);
		*++d_first = sum;
	}
	return ++d_first;
}

       该算法用来计算局部总和，其原理与adjacent_difference相似。
 

inner_product

//版本1
template <typename InputIt, typename OutputIt, typename T>
T inner_product(InputIt first1, InputIt last1, InputIt first2, InputIt last2, T value) {
	while (first1 != last1) {
		value = value + *first2 * *first2;
		++first1;
		++first2;
	}
	return value;
}
//版本2
template <typename InputIt, typename OutputIt, typename T, typename BinaryOperation1, typename BinaryOperation2>
T inner_product(InputIt first1, InputIt last1, InputIt first2, InputIt last2, T value, BinaryOperation1 op1, BinaryOperation op2) {
	while (first1 != first2) {
		value = op1(value, op2(*first1, *first2));
		++first1;
		++first2;
	}
}

       该算法能够计算[first1, last1)和[first2, first2+(last1-first1))的一般内积。需要注意的是该算法第二个版本要提供两个二元操作符，并且算法先计算第二个操作符。比如版本1的op1就是+，op2就是*。

 

gcd(since C++17)

       gcd函数用来求两个正整数的最大公约数，用到辗转相除法（也叫欧几里得算法）。

template<typename _EuclideanRingElement>
_EuclideanRingElement __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
{
	while (__n != 0) {
		_EuclideanRingElement __t = __m % __n;
		__m = __n;
		__n = __t;
    }
    return __m;
}

 

lcm(since C++17)

       lcm函数用来求两个正整数的最小公倍数。

template <typename _Mn, typename _Nn>
constexpr common_type_t<_Mn, _Nn> __lcm(_Mn __m, _Nn __n) {
	return (__m != 0 && __n != 0) ? (__detail::__abs_integral(__m) / __detail::__gcd(__m, __n)) * __detail::abs_integral(__n) : 0; //__abs_integral()取绝对值
}

 

 

 

 

                                                                      本文部分代码摘自http://en.cppreference.com