时间戳

首页 > 解决方案 > 什么是最干净的方法来做一个 `std::partial_sum` 前面有一个 `0`？

c++ - 什么是最干净的方法来做一个 `std::partial_sum` 前面有一个 `0`？

问题描述

在 C++ 中，有一个std::partial_sum计算前缀和的函数。编码

#include <iostream>
#include <vector>
#include <iterator>
#include <numeric>

int main() {
    std::vector<int> a = {1, 2, 3, 4, 5};
    std::partial_sum(a.begin(), a.end(), a.begin());
    return 0;
}

将覆盖 a to 1 3 6 10 15，这是预期的。

但是，在大多数情况下，我想使用前缀总和，我希望0前面有一个表示“空总和”，以便我可以a[2] - a[0]用来查询前两个元素的总和。（这允许我使用一个简单的嵌套 for 循环来查找所有子数组的总和）。有没有办法用函数来实现它std::partial_sum？我不知道这是否可能，因为输出大小将是输入大小 + 1。

注意：我不是在寻找a预先改变内容或类型的方法。

如果大小a是一个问题：

#include <iostream>
#include <vector>
#include <iterator>
#include <numeric>

int main() {
    std::vector<int> a = {1, 2, 3, 4, 5, -1};
    std::partial_sum(a.begin(), a.end() - 1, a.begin());
    return 0;
}

像这样的东西也可以为我工作。

标签： c++stdstdvectorprefix-sum

解决方案

有没有办法用函数来实现它std::partial_sum？

只需在调用之前将 0 写入输出迭代器即可std::partial_sum。应该小心，因为输出比输入大一个，这不会就地工作，因为它在读取第一个输入之前写入第一个输出。

template<class InputIt, class OutputIt>
constexpr OutputIt my_partial_sum(InputIt first, InputIt last, OutputIt d_first)
{
    *d_first++ = typename std::iterator_traits<InputIt>::value_type{};
    return std::partial_sum(first, last, d_first);
}

如果您希望能够做到这一点，您可以调整进一步的可能实施std::partial_sum

template<class InputIt, class OutputIt>
constexpr OutputIt partial_sum(InputIt first, InputIt last, OutputIt d_first)
{
    using value_type = typename std::iterator_traits<InputIt>::value_type;

    if (first == last) {
        *d_first++ = value_type{};
        return d_first;
    }

    value_type sum{};
    value_type next = *first;

    *d_first++ = sum;
 
    while (++first != last) {
       next = *first;
       sum = std::move(sum) + next;
       *d_first++ = sum;
    }
    return d_first;
}

但我认为更简单的方法是将 0 添加到您的容器中。

template <typename Container>
void my_partial_sum(Container& c) {
    c.emplace(c.begin());
    std::partial_sum(c.begin(), std::prev(c.end()), c.begin());
}

推荐阅读