std::partial_sum() 算法

自 C++20 起

// (1)
template< class InputIt, class OutputIt >
constexpr OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first );

// (2)
template< class InputIt, class OutputIt, class BinaryOperation >
constexpr OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first, BinaryOperation op );

直到 C++20

// (1)
template< class InputIt, class OutputIt >
OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first );

// (2)
template< class InputIt, class OutputIt, class BinaryOperation >
OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first, BinaryOperation op );

如果 [first; last) 非空，则计算其子范围中元素的局部和，并将这些和写入从 d_first 开始的范围，两者都对左侧操作数应用 std::move (C++11 起)。

• (1) 使用 operator+ 对元素求和。等同于

std::iterator_traits<InputIt>::value_type acc = *first;
*d_first = acc;

acc = std::move(acc) + *(first + 1);
*(d_first + 1) = acc;

acc = std::move(acc) + *(first + 2);
*(d_first + 2) = acc;

acc = std::move(acc) + *(first + 3);
*(d_first + 3) = acc;
// ...

• (2) 使用给定的二元函数 op。等同于

std::iterator_traits<InputIt>::value_type acc = *first;
*d_first = acc;

acc = op(std::move(acc), *(first + 1));
*(d_first + 1) = acc;

acc = op(std::move(acc), *(first + 2));
*(d_first + 2) = acc;

acc = op(std::move(acc), *(first + 3));
*(d_first + 3) = acc;
// ...

未定义行为

如果 op 使任何迭代器（包括结束迭代器）失效或修改所涉及范围的任何元素，则行为未定义

.

参数

first last	要折叠的元素范围。
init	折叠的初始值。
op	将应用的二元操作函数对象。函数的签名应等同于以下内容 Ret fun(const Type1 &a, const Type2 &b); 签名不需要包含 const&。 类型 Type1 必须是这样，即 std::iterator_traits<InputIt>::value_type 类型的对象可以隐式转换为它。 类型 Type2 必须是这样，即 InputIt 类型的对象可以被解引用，然后隐式转换为它。 类型 Ret 必须是这样，即 InputIt 类型的对象可以被解引用并赋值其类型的值。

类型要求

InputIt	LegacyInputIterator
OutputIt	LegacyOutputIterator

• InputIt 的值类型必须可由 *first 构造。
• acc 必须可写入 d_first。

返回值

指向写入的最后一个元素之后的元素的迭代器，如果 [first; last) 为空，则为 d_first。

复杂度

给定 N 为 std::distance(first, last) - 1

• (1) 恰好 N 次 operator+ 的应用。
• (2) 恰好 N 次二元函数 op 的应用。

异常

(无)

可能的实现

partial_sum(1)

template<class InputIt, class OutputIt>
constexpr // since C++20
OutputIt partial_sum(InputIt first, InputIt last, OutputIt d_first)
{
    if (first == last)
        return d_first;

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

    while (++first != last)
    {
        sum = std::move(sum) + *first; // std::move since C++11
        *++d_first = sum;
    }

    return ++d_first;

    // or, since C++14:
    // return std::partial_sum(first, last, d_first, std::plus<>());
}

partial_sum(2)

template<class InputIt, class OutputIt, class BinaryOperation>
constexpr // since C++20
OutputIt partial_sum(InputIt first, InputIt last, OutputIt d_first, BinaryOperation op)
{
    if (first == last)
        return d_first;

    typename std::iterator_traits<InputIt>::value_type acc = *first;
    *d_first = acc;

    while (++first != last)
    {
        acc = op(std::move(acc), *first); // std::move since C++11
        *++d_first = acc;
    }

    return ++d_first;
}

备注

acc 是由于 LWG issue 539 的解决而引入的。

使用 acc 而不是直接计算差异的原因是，如果以下类型不匹配，后者的语义会令人困惑：

• InputIt 的值类型
• OutputIt 的可写类型
• operator- 或 op 参数的类型
• operator- 或 op 的返回类型

acc 作为中间对象，用于缓存迭代元素的值

• 其类型是 InputIt 的值类型
• 写入 d_first 的值（即 operator- 或 op 的返回值）被赋值给它
• 其值被传递给 operator- 或 op

enum not_int { x = 1, y = 2 };

char i_array[4] = {100, 100, 100, 100};
not_int e_array[4] = {x, x, y, y};
int  o_array[4];

// OK: uses operator+(char, char) and assigns char values to int array
std::partial_sum(i_array, i_array + 4, o_array);

// Error: cannot assign not_int values to int array
std::partial_sum(e_array, e_array + 4, o_array);

// OK: performs conversions when needed
// 1. creates `acc` of type char (the value type)
// 2. the char arguments are used for long multiplication (char -> long)
// 3. the long product is assigned to `acc` (long -> char)
// 4. `acc` is assigned to an element of `o_array` (char -> int)
// 5. go back to step 2 to process the remaining elements in the input range
std::partial_sum(i_array, i_array + 4, o_array, std::multiplies<long>{});

示例

Main.cpp

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

int main()
{
    std::vector<int> v(10, 2); // v = {2, 2, 2, 2, 2, 2, 2, 2, 2, 2}

    std::cout << "The first " << v.size() << " even numbers are: ";
    // write the result to the cout stream
    std::partial_sum(v.cbegin(), v.cend(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';

    // write the result back to the vector v
    std::partial_sum(v.cbegin(), v.cend(),
                     v.begin(), std::multiplies<int>());

    std::cout << "The first " << v.size() << " powers of 2 are: ";
    for (int n : v)
        std::cout << n << ' ';
    std::cout << '\n';
}

输出

The first 10 even numbers are: 2 4 6 8 10 12 14 16 18 20 
The first 10 powers of 2 are: 2 4 8 16 32 64 128 256 512 1024