优化网站的网站,黄冈做网站,广西网站建设企业,wordpress保存帖子数据库这一节介绍的算法#xff0c;统称为数值(numeric)算法。STL规定#xff0c;欲使用它们#xff0c;客户端必须包含头文件numeric.SGI将它们实现与stl_numeric.h文件中。
目录
运用实例
accumulate
adjacent_difference
inner_product
partial_sum
pow… 这一节介绍的算法统称为数值(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};vectorint 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, minusint()) endl;// 10, i.e. 25 - 1 - 2 - 3 - 4 - 5 注意25并没有执行minusint运算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, minusint(), plusint()) endl;// -14, i.e. 10 - (21) - (32) - (43) - (54)cout inner_product(iv.begin() 1, iv.end(), iv.begin(), 10, minusint(), minusint()) endl;// 6, i.e. 10 - (2-1) - (3-2) - (4-3) - (5-4)ostream_iteratorint oite(cout, );partial_sum(iv.begin(), iv.end(), oite);// 1 3 6 10 15cout endl;partial_sum(iv.begin(), iv.end(), oite, minusint());// 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, plusint());// 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 templateclass InputIterator, class T
T accumulate(InputIterator first, InputIterator last, T init) {for (; first ! last; first) init *first;return init;
}templateclass 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或者initbinary(init, *i)。
adjacent_difference
//版本一
templateclass 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));
}templateclass 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;
}//版本二
templateclass 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);
}templateclass 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并针对[first1, 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
//版本一
templateclass 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;
}//版本二
templateclass 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有头到尾依序执行resultresult(*i)* *(first2(i-first1))。 第二个版本与第一个版本唯一的差异是外界提供仿函数取代了operator和operator*。也就是说首先将结果初始化为init然后针对[first1, last1)的每一个迭代器i由头至尾执行resultbinary_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和*(first1)的和赋值给*(result1),依次类推。注意result可以等于first这使得我们完成就地inplace计算。在这种情况下它是一个质变算法(mutating algorithm)。 运算中的总和首先初始化为*first,然后赋值给*result。对于[first,last)中每个迭代器i从头至尾依次执行sumsum*i或者sumbinary_op(sum, *i),然后将sum赋值给*(result (i-first))。 本算法返回输出区间的尾端result(last-first)。 如果加法和减法的定义一如常规定义那么partial_sum与先前介绍的adjacent_difference互为逆运算。具体含义参见adjacent_difference那节的介绍
power 这个算法是SGI专属并不在STL标准之列。它用来计算某数的n幂次方。这个所谓的n幂次是指自己对自己进行某种运算达到n次。运算类型可由外界指定如果指定为乘法那就是乘幂。
templateclass T, class Integer
inline T power(T x, Integer n) {return power(x, n, multipliesT());
}templateclass T, class Integer, class MonoidOperation
T power(T x, Integer n, MonoidOperation op) {if (n 0) {return identity_element(op);} else {while ((n1) 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值开始呈现递增状态。它改变了区间内容所以是质变算法。
templateclass ForwardIterator, class T
void itoa(ForwardIterator first, ForwardIterator last, T value) {while(first ! last) *first value;
} 参考文档《STL源码剖析》--侯捷
