本节所分析的算法是在stl_numeric.h中, 本节以源码 + 例子的形式一起分析这些实现的操作.
要求传入两个InputIterator类型的迭代器和一个初始化值, 第二个版本还支持在传入一个仿函数或函数.
// 版本一
template <class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init) {
for ( ; first != last; ++first)
init = 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;
}实例:
// 函数
inline int binary(int a1, int a2)
{
return a1 - a2;
}
// 仿函数
struct mybinary
{
int operator() (const int a1, const int a2)
{
return a1 + a2;
}
}mybinary;
int main()
{
int a[4]= {1, 2, 3, 4};
int sum = 0;
sum = accumulate(a, a+4, sum); // 版本一
for(const auto &i : a)
cout << i << " "; // 1 2 3 4
cout << sum; // 10
sum = accumulate(a, a+4, sum, binary); // 版本二, 函数
cout << sum; // 0
sum = accumulate(a, a+4, sum, mybinary); // 版本二, 仿函数
cout << sum; // 10
exit(0);
}两个版本.
版本一 : 两个InputIterator类型的迭代器, 一个迭代器(所有的数据 * first2), 一个初始化值.
template <class InputIterator1, class InputIterator2, class T>
T inner_product(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, T init) {
for ( ; first1 != last1; ++first1, ++first2)
init = init + (*first1 * *first2);
return init;
}版本二 : 比版本一多接受两个函数或仿函数, 先执行binary_op2操作再执行binary_op1. 与上面的accumulate一样.
template <class InputIterator1, class InputIterator2, class T,
class BinaryOperation1, class BinaryOperation2>
T inner_product(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, T init, BinaryOperation1 binary_op1,
BinaryOperation2 binary_op2) {
for ( ; first1 != last1; ++first1, ++first2)
init = binary_op1(init, binary_op2(*first1, *first2));
return init;
}两个版本. 功能 : 将传入的InputIterator两个迭代器范围内的值进行局部求和. 即 y0 = x0; y1 = x0 + x1; ...
版本一 : 默认操作
template <class InputIterator, class OutputIterator, class T>
OutputIterator __partial_sum(InputIterator first, InputIterator last,
OutputIterator result, T*) {
T value = *first;
// 跳过x0, 从x1开始局部求和
while (++first != last) {
value = value + *first;
*++result = value;
}
return ++result;
}
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(first));
}版本二 : 比版本一多了一个二元操作.
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;
// 跳过x0, 从x1开始局部求和
while (++first != last) {
value = binary_op(value, *first);
*++result = value;
}
return ++result;
}
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(first), binary_op);
}实例:
inline int partial_inc(int a1, int a2)
{
return a2+2;
}
int main()
{
int a[4] = {1, 2, 3, 4 };
int a2[4];
partial_sum(a, a+sizeof(a)/sizeof(int), a2); // 版本一
for(const auto &i : a)
cout << i << " "; // 1 2 3 4
for(const auto &i : a2)
cout << i << " "; // 1 3 6 10
partial_sum(a, a+sizeof(a)/sizeof(int), a2, partial_inc); // 版本二
for(const auto &i : a2)
cout << i << " "; // 1 4 5 6
exit(0);
}两个版本. 功能 : 将传入的InputIterator两个迭代器范围内的值进行局部相减. 即 y0 = x0; y1 = x0 - x1 ...
版本一
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>
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, class BinaryOperation>
OutputIterator __adjacent_difference(InputIterator first, InputIterator last,
OutputIterator result, T*,
BinaryOperation binary_op) {
T value = *first;
while (++first != last) {
T tmp = *first;
*++result = binary_op(tmp, value);
value = tmp;
}
return ++result;
}
template <class InputIterator, class OutputIterator, class BinaryOperation>
OutputIterator adjacent_difference(InputIterator first, InputIterator last,
OutputIterator result,
BinaryOperation binary_op) {
if (first == last) return result;
*result = *first;
return __adjacent_difference(first, last, result, value_type(first),
binary_op);
}实例:
struct adjacent{
int operator() (const int tmp, const int a) { return tmp - a - a; }
}adjacent;
int main()
{
int a[4] = {1, 2, 3, 4};
int a2[4];
for(const auto &i : a)
cout << i << " "; // 1 2 3 4
adjacent_difference(a, a+4, a2);
for(const auto &i : a2)
cout << i << " "; // 1 1 1 1
partial_sum(a2, a2+4, a2);
for(const auto &i : a2)
cout << i << " "; // 1 2 3 4
adjacent_difference(a, a+4, a2, adjacent);
for(const auto &i : a2)
cout << i << " "; // 1 0 -1 -2
exit(0);
}从实例可以看出来adjacent_difference与partial_sum相结合可以恢复.
一个版本. 幂次方。如果指定为乘法运算，则当n >= 0 时传回 x^n
// Returns x ** n, where n >= 0. Note that "multiplication"
// is required to be associative, but not necessarily commutative.
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;
}
}
template <class T, class Integer>
inline T power(T x, Integer n) {
return power(x, n, multiplies<T>());
}设定某个区间的内容, 使其每个元素从指定值value开始, 呈现递增
template <class ForwardIterator, class T>
void iota(ForwardIterator first, ForwardIterator last, T value) {
while (first != last) *first++ = value++;
}实例:
int main()
{
int a[4] = {1, 2, 3, 4};
iota(a+1, a+4, 10);
for(const auto &i : a)
cout << i << ' '; // 1 10 11 12
return 0;
}本节对numeric.h中的算法进行了分析, 这些都是很简单的函数实现, 但是大都提供了两个版本, 可接受二元操作的函数, 这由用户定义, 也就提高了STL的灵活性.