std::partial_sum

定义在头文件 `<numeric>` 中
template< class InputIt, class OutputIt > OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first );	(1)	(从 C++20 开始为 constexpr)
template< class InputIt, class OutputIt, class BinaryOp > OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first, BinaryOp op );	(2)	(从 C++20 开始为 constexpr)

1) 如果 [first, last) 为空，则不执行任何操作。

否则，按顺序执行以下操作

创建一个名为 acc 的累加器，其类型为 InputIt 的值类型，并将其初始化为 *first.
将 acc 赋值给 *d_first.
对于 [1, std::distance(first, last)) 中的每个整数 i，按顺序执行以下操作

a) 计算 acc + *iter(直到 C++20)std::move(acc) + *iter(从 C++20 开始)，其中 iter 是 first 的下一个 i
th 迭代器。

b) 将结果赋值给 acc.

c) 将 acc^[1] 赋值给 *dest，其中 dest 是 d_first 的下一个 i
th 迭代器。

2) 与 (1) 相同，但计算 op(acc, *iter)(直到 C++20)op(std::move(acc), *iter)(从 C++20 开始)。

给定 binary_op 作为实际的二元运算

如果满足以下任何条件，则程序格式错误

InputIt 的值类型不能从 *first 构造。
acc 不可写入到 d_first。
binary_op(acc, *iter)(直到 C++20)binary_op(std::move(acc), *iter)(自 C++20 起) 的结果无法隐式转换为 InputIt 的值类型。

给定 d_last 作为要返回的迭代器，如果满足以下任何条件，则行为未定义

binary_op 修改了 [first, last) 或 [d_first, d_last) 中的任何元素。
binary_op 使 [first, last] 或 [d_first, d_last] 中的任何迭代器或子范围失效。

↑ 要分配的实际值是上一步赋值的结果。我们假设这里分配的结果是 acc。

[编辑] 参数

first, last	-	要相加的元素范围。
d_first	-	目标范围的开头；可以等于 `first`。
op	-	将要应用的二元操作函数对象。函数的签名应等效于以下内容 Ret fun(const Type1 &a, const Type2 &b); 签名不需要具有 `const &`。类型 `Type1` 必须是，使得类型 `std::iterator_traits<InputIt>::value_type` 的对象可以隐式转换为 `Type1`。类型 `Type2` 必须是，使得类型 `InputIt` 的对象可以被解引用，然后隐式转换为 `Type2`。类型 `Ret` 必须是，使得类型 `InputIt` 的对象可以被解引用，并赋值为类型 `Ret` 的值。
类型要求
- `InputIt` 必须满足 LegacyInputIterator 的要求。
- `OutputIt` 必须满足 LegacyOutputIterator 的要求。

[编辑] 返回值

指向写入的最后一个元素后的元素的迭代器，或者如果 [first, last) 为空，则返回 d_first。

[编辑] 复杂度

给定 $\scriptsize N$ $N$ 作为 std::distance(first, last)

1) 正好 $\scriptsize N-1$ $N-1$ 次 operator+ 应用。

2) 正好 $\scriptsize N-1$ $N-1$ 次二元函数 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++20
        *++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 BinaryOp>
constexpr // since C++20
OutputIt partial_sum(InputIt first, InputIt last, 
                     OutputIt d_first, BinaryOp 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++20
        *++d_first = acc;
    }
 
    return ++d_first;
}

[编辑] 备注

acc 是由于解决 LWG issue 539 而引入的。使用 acc 而不是直接将结果相加（即 *(d_first + 2) = (*first + *(first + 1)) + *(first + 2);）的原因是，如果以下类型不匹配，则后者的语义会令人困惑

InputIt 的值类型
OutputIt 的可写类型（s）
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>{});

[编辑] 示例

运行此代码

#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

[编辑] 缺陷报告

以下更改行为的缺陷报告已追溯应用于以前发布的 C++ 标准。

DR	应用于	已发布的行为	正确行为
LWG 242	C++98	`op` 不能有副作用	它不能修改所涉及的范围
LWG 539	C++98	结果所需的类型要求缺少评估和赋值有效性的要求	添加

[编辑] 另请参阅

adjacent_difference	计算范围中相邻元素之间的差异 (函数模板) [编辑]
accumulate	将范围中的元素相加或折叠 (函数模板) [编辑]
inclusive_scan (C++17)	类似于 `std::partial_sum`，在第 $i$ 个和中包含第 $i$ 个输入元素 (函数模板) [编辑]
exclusive_scan (C++17)	类似于 `std::partial_sum`，在第 $i$ 个和中不包含第 $i$ 个输入元素 (函数模板) [编辑]

[1] 要分配的实际值是上一步赋值的结果。我们假设这里分配的结果是 acc。

[1]

编译器支持
独立和托管
语言
标准库
标准库头文件
命名要求
功能测试宏 (C++20)
语言支持库
概念库 (C++20)
元编程库 (C++11)
诊断库
通用实用程序库
字符串库
容器库
迭代器库
范围库 (C++20)
算法库
数值库
本地化库
输入/输出库
文件系统库 (C++17)
正则表达式库 (C++11)
并发支持库 (C++11)
执行支持库 (C++26)
技术规范
符号索引
外部库

cppreference.com

命名空间

变体

视图

操作