c++ - 没有for循环的集合中n个连续项的总和

我正在寻找如何删除我的for循环以计算集合中n个连续项的总和。



要确定两个连续项的总和，我知道我可以这样做:

std::adjacent_difference(std::begin(collection),
                          std::end(collection),
                         std::begin(adjacent_sum),
[](const int x, const int y) { return std::abs(x - y); });

但是，要确定n个连续项的总和，我会被诸如std::transform之类的算法在需要索引时处理值的事实所困扰。我应该使用索引作为算法外部的变量来维持状态吗？

这是使用Visual Studio 2019编译的完整示例:

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

// Compute the sum of the n consecutive items
// Ex: {1,2,1,3,2} and n=3
// result: {0,0,4,6,6}
std::vector<int> adjacent_difference_n(const std::vector<int> collection, const size_t num_consecutive_items)
{
    std::vector<int> result {};
    const auto collection_size = collection.size();

    for (size_t idx = 0; idx < num_consecutive_items - 1; idx++)
    {
        result.emplace_back(0);
    }

    if (collection_size >= num_consecutive_items)
    {
        // For each element starting at num_consecutive_items
        for (auto idx = num_consecutive_items - 1; idx < collection_size; idx++)
        {
            // Compute the sum of the previous num_consecutive_item
            // Loop includes the current item
            auto sum = 0;
            auto prev_idx = idx - (num_consecutive_items - 1);
            while (prev_idx <= idx)
            {
                sum += collection[prev_idx++];
            }
            result.emplace_back(sum);
        }
    }

    return result;
}

int main()
{
    const std::vector<int> collection = { 1, 2, 1, 3, 2 };
    const auto result = adjacent_difference_n(collection, 3);
    for (auto& value : result) std::cout << value << " ";
    std::cout << std::endl;
    return 0;
}

最佳答案

您可以通过仅减去第一项并添加新项来避免内部循环更新部分和:

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

template <class T>
auto partial_sum_n(std::vector<T> const& src, size_t m)
{
    // Initialize the resulting vector with zeroes
    std::vector<T> result(src.size());
    if (m == 0  or  src.size() < m)
        return result;

    auto first = src.cbegin();
    auto it = std::next(first, m);

    // Sum the first elements and assign to the first non zero element
    auto sum = std::accumulate(first, it, T(0));
    auto dest = std::next(result.begin(), m - 1);
    *dest = sum;

    // Fill the rest of the vector
    std::transform(it, src.cend(),
                   ++dest,
                   [first, sum] (T const& x) mutable {
                       sum += x - *(first++);    // <-- Just update the sum
                       return sum;
                   });

    return result;
}

int main()
{
    const std::vector<int> collection{ 1, 2, 1, 3, 2 };
    const auto result = partial_sum_n(collection, 3);
    for (auto const value : result)
        std::cout << ' ' << value;
    std::cout << '\n';
}

关于c++ - 没有for循环的集合中n个连续项的总和，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57641005/