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 个迭代器。

b) 将计算结果赋给 acc。

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

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) 应用

N-1

次 operator+。

2) 应用

N-1

次二元函数 op。

[编辑]可能的实现

partial_sum (1)

template<class InputIt, class OutputIt>constexpr// C++20 起 OutputIt partial_sum(InputIt first, InputIt last, OutputIt d_first){if(first == last)return d_first;   typenamestd::iterator_traits<InputIt>::value_type sum =*first;*d_first = sum;   while(++first != last){ sum = std::move(sum)+*first;// C++20 起有 std::move*++d_first = sum;}   return++d_first;   // 或 C++14 起：// return std::partial_sum(first, last, d_first, std::plus<>());}

partial_sum (2)

template<class InputIt, class OutputIt, class BinaryOp>constexpr// C++20 起 OutputIt partial_sum(InputIt first, InputIt last, OutputIt d_first, BinaryOp op){if(first == last)return d_first;   typenamestd::iterator_traits<InputIt>::value_type acc =*first;*d_first = acc;   while(++first != last){ acc = op(std::move(acc), *first);// C++20 起有 std::move*++d_first = acc;}   return++d_first;}

[编辑]注解

acc 是由 LWG 问题 539 的解决方案引入的。使用 acc 而不是直接将结果相加（即 *(d_first +2)=(*first +*(first +1))+*(first +2);）的原因是后者的语义在以下类型不匹配时难以理解：

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：使用 operator+(char, char) 并且会将 char 值赋给 int 数组 std::partial_sum(i_array, i_array +4, o_array);   // 错误：不能将 not_int 值赋给 int 数组 std::partial_sum(e_array, e_array +4, o_array);   // OK：在需要时进行转换// 1. 创建 char 类型的 “acc”（值类型）// 2. 将 char 实参用于 long 乘法（char -> long）// 3. 将 long 积赋给 “acc”（long -> char）// 4. 将 “acc” 赋给 “o_array” 的一个元素（char -> int）// 5. 回到第 2 步，处理输入序列的剩余元素 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<<"前 "<< v.size()<<" 个偶数是：";// 将结果写入流 cout std::partial_sum(v.cbegin(), v.cend(), std::ostream_iterator<int>(std::cout, " "));std::cout<<'\n';   // 将结果写回 vector v std::partial_sum(v.cbegin(), v.cend(), v.begin(), std::multiplies<int>());   std::cout<<"2 的前 "<< v.size()<<" 个幂是：";for(int n : v)std::cout<< n <<' ';std::cout<<'\n';}

输出：

前 10 个偶数是：2 4 6 8 10 12 14 16 18 20 2 的前 10 个幂是：2 4 8 16 32 64 128 256 512 1024

[编辑]缺陷报告

下列更改行为的缺陷报告追溯地应用于以前出版的 C++ 标准。

缺陷报告	应用于	出版时的行为	正确行为
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++26)
技术规范
符号索引
外部库

cppreference.com

名字空间

变换

查看

操作