STL算法之数值算法＜stl_numeric.h＞

       

        这一节介绍的算法，统称为数值(numeric)算法。STL规定，欲使用它们，客户端必须包含头文件<numeric>.SGI将它们实现与<stl_numeric.h>文件中。

目录

运用实例

accumulate

adjacent_difference

inner_product

partial_sum

power

iota

---

运用实例

        观察这些算法的源码之前，首先运行几个实例。

#include <numeric>
#include <vector>
#include <functional>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;int main() {int ia[5] = {1, 2, 3, 4, 5};vector<int> iv(ia, ia + 5);cout << accumulate(iv.begin(), iv.end(), 10) << endl;// 25, i.e. 10 + 1 + 2 + 3 + 4 + 5 cout << accumulate(iv.begin(), iv.end(), 25, minus<int>()) << endl;// 10, i.e. 25 - 1 - 2 - 3 - 4 - 5   注意25并没有执行minus<int>运算cout << inner_product(iv.begin() + 1, iv.end(), iv.begin(), 10) << endl;// 50, i.e. 10 + 2*1 + 3*2 + 4*3 + 5*4cout << inner_product(iv.begin() + 1, iv.end(), iv.begin(), 10, minus<int>(), plus<int>()) << endl;// -14, i.e. 10 - (2+1) - (3+2) - (4+3) - (5+4)cout << inner_product(iv.begin() + 1, iv.end(), iv.begin(), 10, minus<int>(), minus<int>()) << endl;// 6, i.e. 10 - (2-1) - (3-2) - (4-3) - (5-4)ostream_iterator<int> oite(cout, " ");partial_sum(iv.begin(), iv.end(), oite);// 1 3 6 10 15cout << endl;partial_sum(iv.begin(), iv.end(), oite, minus<int>());// 1 -1 -4 -8 -13cout << endl;adjacent_difference(iv.begin(), iv.end(), oite);// 1 1 1 1 1cout << endl;adjacent_difference(iv.begin(), iv.end(), oite, plus<int>());// 1 3 5 7 9cout << endl;int n = 3;iota (iv.begin(), iv.end() , n);for (int i =0; i < iv.size(); ++i) {cout << iv[i] << ' '; // 3 4 5 6 7}cout << endl;return 0;
}

代码中的注释，标示了其运行结果；运行完这段代码，会对这几个数值算法有个基本的认识。

accumulate

        

template<class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init) {for (; first != last; ++first) init += *first;return init;
}template<class InputIterator, class T, class BinaryOperation>
T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op) {for (; first != last; ++first) init = binary_op(init, *first);return init;
}

        算法accumulate用来计算init和[first,last)内所有元素的总和。注意，我们必须提供初始值init，这么做的原因之一是当[first,last)为空区间时，仍能获得一个明确定义的值。如果希望计算[first,last)中所有数值的总和，应该将init设为0.

        式中的二元操作符不必满足交换律(commutative)和结合律(associative)。【如果需要将算法改造为可并行运算的算法，可能需要考虑结合律，暂不展开，后续博文进行尝试改造】

        accumulate的行为顺序有明确的定义：现将init初始化，然后针对[first,last）区间中的每一个迭代器i,依次执行init = init + *i或者init=binary(init, *i)。

adjacent_difference

//版本一
template<class InputIterator, class OutputIterator>
OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result) {if (first == last) return result;*result = *first; // 首先记录第一个元素return __adjacent_difference(first, last, result, value_type(first));
}template<class InputIterator, class OutputIterator, class T>
OutputIterator __adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, T*) {T value = *first;while(++first != last) {T tmp = *first;*++result = tmp - value;value = tmp;}return ++result;
}//版本二
template<class InputIterator, class OutputIterator, class BinaryOperator>
OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, BinaryOperator binary_op ) {if (first == last) return result;*result = *first; // 首先记录第一个元素return __adjacent_difference(first, last, result, value_type(first), binary_op);
}template<class InputIterator, class OutputIterator, class T, class BinaryOperator>
OutputIterator __adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, T*, BinaryOperator binary_op) {T value = *first;while(++first != last) {T tmp = *first;*++result = binary_op(tmp, value);value = tmp;}return ++result;
}

        算法adjacent_difference用来计算[first, last)中相邻元素的差额。也就是说，它将*first赋给*result，并针对[first+1, last)内的每个迭代器i,将*i-*(i-1)之值赋给*(result+(i-first))。

        注意，我们可以采用就地（inplace）运算方式，也就是另result等于first，在这种情况下，它是一个质变算法(mutating algorithm)。

        "存储第一元素之值，然后存储后继元素之差值"这种做法很有用，因为这么一来便有足够的信息可以重建输入区间的原始内容。如果加法与减法定义如常规定义，那么adjacent_difference与partial_sum(稍后介绍)互为逆运算。这意思是，如果对区间1,2,3,4,5执行adjacent_difference,获得结果1,1,1,1,1，再对结果执行partial_sum便会获得原始区间1,2,3,4,5。

        第一个版本使用operator-作为默认差额运算符，第二个版本采用外界提供的二元仿函数。第一个版本针对[first, last)中的每个迭代器i，将*i-*(i-1)赋值给*(resut+(i-first)),第二个版本则是将binary_op(*i, *(i-1))的运算结果赋值给*(result+(i-first))。

inner_product

//版本一
template<class InputIterator1, class InputIterator2, class T>
T inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init) {for (; first1 != last1; ++first1, ++first2)init += (*first1) * (*first2);return init;
}//版本二
template<class InputIterator1, class InputIterator2, class T, class BinaryOperator1, class BinaryOperator2>
T inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init, BinaryOperator1 binary_op1, BinaryOperator2 binary_op2) {for (; first1 != last1; ++first1, ++first2)init = binary_op1(init,  binary_op2(*first1, *first2));return init;
}

        算法inner_product能够计算[first1,last1)和[first2, first2+ (last1-first1))的一般内积(generalized inner product)。注意，你一定得提供初值init。这么做的原因之一是当[first,last）为空时，仍可获得一个明确定义的结果。如果我们想计算两个vectors的一般内积，应该将init设为0.

        第一个版本会将两个区间的内积结果加上init。也就是说，现将结果初始化为init，然后针对[first1, last1)的每一个迭代器i，有头到尾依序执行result=result+(*i)* *(first2+(i-first1))。

        第二个版本与第一个版本唯一的差异是外界提供仿函数取代了operator+和operator*。也就是说，首先将结果初始化为init，然后针对[first1, last1)的每一个迭代器i，由头至尾执行result=binary_op1(result, binary_op2(*i, *(first2+(i-first1))))。

        式中所用的二元仿函数不必满足交换律和结合律。inner_product所有运算的行为的顺序都有明确的设定。

partial_sum

//版本1
template <class InputIterator, class OutputIterator>
OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result) {if (first == last) return result;*result = *first;return __partial_sum(first, last, result, value_type(result));
}template <class InputIterator, class OutputIterator, class T>
OutputIterator __partial_sum(InputIterator first, InputIterator last, OutputIterator result, T*) {T value = *first;while(++first != last) {value = value + *first;*++result = value;    }return ++result;
}//版本2
template <class InputIterator, class OutputIterator, class BinaryOperation>
OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op) {if (first == last) return result;*result = *first;return __partial_sum(first, last, result, value_type(result), binary_op);
}template <class InputIterator, class OutputIterator, class T, class BinaryOperation>
OutputIterator __partial_sum(InputIterator first, InputIterator last, OutputIterator result, T*, BinaryOperation binary_op) {T value = *first;while(++first != last) {value = binary_op(value, *first);*++result = value;    }return ++result;
}

        算法partial_sum用来计算局部总和。他会将*frist赋值给*result,将*first和*(first+1)的和赋值给*(result+1),依次类推。注意，result可以等于first，这使得我们完成就地inplace计算。在这种情况下它是一个质变算法(mutating algorithm)。

        运算中的总和首先初始化为*first,然后赋值给*result。对于[first,last)中每个迭代器i，从头至尾依次执行sum=sum+*i或者sum=binary_op(sum, *i),然后将sum赋值给*(result + (i-first))。

        本算法返回输出区间的尾端result+(last-first)。

        如果加法和减法的定义一如常规定义，那么partial_sum与先前介绍的adjacent_difference互为逆运算。（具体含义参见adjacent_difference那节的介绍）

power

        这个算法是SGI专属，并不在STL标准之列。它用来计算某数的n幂次方。这个所谓的n幂次是指自己对自己进行某种运算，达到n次。运算类型可由外界指定；如果指定为乘法，那就是乘幂。

template<class T, class Integer>
inline T power(T x, Integer n) {return power(x, n, multiplies<T>());
}template<class T, class Integer, class MonoidOperation>
T power(T x, Integer n, MonoidOperation op) {if (n == 0) {return identity_element(op);} else {while ((n&1) == 0) {n >>= 1;x = op(x, x);}T result = x;n >> 1;while (n != 0) {x = op(x, x);if ((n & 1) !=0 ) {result = op(result, x);}n >> 1;}return result;}}

iota

        这个算法由SGI专属（clang++编译貌似可以通过），并不在STL标准之列。它用来设定某个区间的内容，使其的每一个元素从指定的value值开始，呈现递增状态。它改变了区间内容，所以是质变算法。

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

参考文档《STL源码剖析》--侯捷