c++ 将partial_sum()与long long值一起使用

7ivaypg9 于 2022-12-05 发布在其他

关注(0)|答案(1)|浏览(154)

I am solving a problem for which, I need to calculate the prefix and suffix sum values. When I do it this way:

class Solution {
public:
    int minimumAverageDifference(vector<int>& nums) {
        long n=size(nums);
        vector<long long> left(n,0ll), right(n,0ll);
        
        partial_sum(begin(nums), end(nums), begin(left));
        partial_sum(rbegin(nums), rend(nums), rbegin(right));
        
        return 0;
    }
};

This works fine for smaller input values, but when the input is very large, I get an error:
Line 258: Char 43: runtime error: signed integer overflow: 2147453785 + 36049 cannot be represented in type 'int' (stl_numeric.h) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_numeric.h:267:43
However, the traditional for-loop works just fine for all the inputs, including the very large ones:

class Solution {
public:
    int minimumAverageDifference(vector<int>& nums) {
        long n=size(nums);
        vector<long long> left(n,0ll), right(n,0ll);
        
        left[0]=nums[0];
        for(int i=1; i<n; i++) {
            left[i]=left[i-1]+nums[i];
        }
        
        right[n-1]=nums[n-1];
        for(int i=n-2; i>=0; i--) {
            right[i]=right[i+1]+nums[i];
        }

        return 0;
    }
};

What am I missing about the usage of partial_sum() ?

c++

来源：https://stackoverflow.com/questions/74671972/using-partial-sum-with-long-long-values

1条答案

按热度按时间

djmepvbi1#

std::partial_sum()是defined，使得累加器类型是作为输入范围元素的类型的：

typename std::iterator_traits<InputIt>::value_type sum = *first;
...

对于采用自定义二进制运算的重载也是如此。没有简单的方法来覆盖该类型--你必须以某种方式修改输入范围本身。
如果你真的想使用std::partial_sum()，你可以将输入范围复制到std::vector<long long>，或者使用boost::transform_iterator动态转换它：

std::vector<int> in(5, INT_MAX);
std::vector<long long> out(in.size());

auto cast_to_long_long = [](int v){ return static_cast<long long>(v); };
auto first = boost::make_transform_iterator(in.begin(), cast_to_long_long);
auto last  = boost::make_transform_iterator(in.end(),   cast_to_long_long);

std::partial_sum(first, last, out.begin());

Demo
但是，最简单的解决方案是使用std::inclusive_scan()，它接受确定累加器类型的初始值：

std::inclusive_scan(in.begin(), in.end(), out.begin(), std::plus(), 0LL);

Demo

赞(0）回复(0）举报 2022-12-05

我来回答

c++ 将partial_sum()与long long值一起使用

1条答案

相关问题

热门标签

最新问答