首页 > 其他 > 详细

partial_sum

时间:2018-01-21 15:38:23      阅读:199      评论:0      收藏:0      [点我收藏+]

版本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(first));
}

template <class InputIterator, class OutputIterator, class T>
OutputIterator __parital_sum(InputIterator first, InputIterator last, OutputIterator result, T*)
{
    T value = *first;
    while ( ++first != last)
    {
        value = value + *first;//前n个元素的总和
        *++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(first), binary_op);
}

template <class InputIterator, class OutputIterator, class T, OutputIterator result, T*, BinaryOperation binary_op>
OutputIterator __parital_sum(InputIterator first, InputIterator last, OutputIterator result, T*)
{
    T value = *first;
    while ( ++first != last)
    {
        value = binary_op ( value, *first);
        *++result = value;
    }
    return ++result;
}

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

  

  运算中的总和首先初始为 *first,然后赋值给 *result 。对于[first,last) 中每个迭代器 i ,从头至尾依序执行sum = sum + *i  (第一版本)或 sum = binary_op(sum, *i)(第二版本),然后再将sum赋值给 *(result+( i - first))。此式所用之二元仿函数不必满足交换律和结合律。所有运算行为的顺序都有明确设定。

  

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

  

  如果加法与减法的定义一如常规定义,那么 partial_sum 与先前介绍过的 adjacent_difference 互为逆运算。这里的意思是,如果对区间值1,2,3,4,5执行parital_sum,获得的结果为1,3,6,10,15,再对此结果执行adjacent_difference,便会获得原始区间值1,2,3,4,5。

partial_sum

原文:https://www.cnblogs.com/Zhoier-Zxy/p/8324287.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!