做一个前面有 0 的 std::partial_sum 最干净的方法是什么?
What is the cleanest way to do a `std::partial_sum` with a `0` in front?
在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 覆盖为 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;
}
像这样的东西也可以为我工作。
Is there a way to achieve it with the std::partial_sum
function?
在调用 std::partial_sum
之前,只需将 0 写入输出迭代器即可。应该小心,因为输出比输入大一个,这不会就地工作,因为它在读取第一个输入之前写入第一个输出。
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
的 possible implementation
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());
}
在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 覆盖为 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;
}
像这样的东西也可以为我工作。
Is there a way to achieve it with the
std::partial_sum
function?
在调用 std::partial_sum
之前,只需将 0 写入输出迭代器即可。应该小心,因为输出比输入大一个,这不会就地工作,因为它在读取第一个输入之前写入第一个输出。
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
的 possible implementation
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());
}