std::partial_sum

在标头 `<numeric>` 定义
	(1)
template< class InputIt, class OutputIt > OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first );			(C++20 前)
template< class InputIt, class OutputIt > constexpr OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first );			(C++20 起)
		(2)
template< class InputIt, class OutputIt, class BinaryOperation > OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first, BinaryOperation op );				(C++20 前)
template< class InputIt, class OutputIt, class BinaryOperation > constexpr OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first, BinaryOperation op );				(C++20 起)

计算范围 [first, last) 的子范围中元素的部分和，并写入到始于 d_first 的范围。第一版本用 operator+ ，第二版本用给定的二元函数 op 对元素求和，两个版本都会将 std::move 应用到它们的左侧运算数 (C++20 起)。

等价运算：

*(d_first)   = *first;
*(d_first+1) = *first + *(first+1);
*(d_first+2) = *first + *(first+1) + *(first+2);
*(d_first+3) = *first + *(first+1) + *(first+2) + *(first+3);
...

op 不能使涉及范围的任何迭代器（包含尾迭代器）失效，或修改该范围的任何元素。

参数

first, last	-	要求和的元素范围
d_first	-	目标范围起始；可以等于 first
op	-	被使用的二元函数对象。该函数的签名应当等价于： Ret fun(const Type1 &a, const Type2 &b); 签名中并不需要有 const &。类型 Type1 必须使得 iterator_traits<InputIt>::value_type 类型的对象能隐式转换到 Type1 。类型 Type2 必须使得 InputIt 类型的对象能在解引用后隐式转换到 Type2 。类型 Ret 必须使得 iterator_traits<InputIt>::value_type 类型对象能被赋 Ret 类型值。
类型要求
- `InputIt` 必须符合老式输入迭代器 (LegacyInputIterator) 的要求。
- `OutputIt` 必须符合老式输出迭代器 (LegacyOutputIterator) 的要求。

返回值

指向最后被写入元素后一元素的迭代器。

复杂度

恰好应用 (last - first) - 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;
 
    typename std::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<>());
}

版本二

template<class InputIt, class OutputIt, class BinaryOperation>
constexpr // 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 sum = *first;
    *d_first = sum;
 
    while (++first != last)
    {
        sum = op(std::move(sum), *first); // C++20 起有 std::move
        *++d_first = sum;
    }
 
    return ++d_first;
}

示例

运行此代码

#include <numeric>
#include <vector>
#include <iostream>
#include <iterator>
#include <functional>
 
int main()
{
    std::vector<int> v = {2, 2, 2, 2, 2, 2, 2, 2, 2, 2}; // 或 std::vector<int>v(10, 2);
 
    std::cout << "前 10 个偶数是：";
    std::partial_sum(v.begin(), v.end(), 
                     std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
 
    std::partial_sum(v.begin(), v.end(), v.begin(), std::multiplies<int>());
 
    std::cout << "2 的前 10 个幂是：";
    for (auto 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 不能有任何副作用	它不能修改涉及到的范围

参阅

adjacent_difference	计算范围内各相邻元素之间的差 (函数模板)
accumulate	对一个范围内的元素求和 (函数模板)
inclusive_scan (C++17)	类似 std::partial_sum，第 i 个和中包含第 i 个输入 (函数模板)
exclusive_scan (C++17)	类似 std::partial_sum，第 i 个和中排除第 i 个输入 (函数模板)

语言
标准库
标准库头文件
自立与有宿主
具名要求
语言支持库
概念库 (C++20)
诊断库
工具库
字符串库
容器库
迭代器库
范围库 (C++20)
算法库
数值库
本地化库
输入/输出库
文件系统库 (C++17)
正则表达式库 (C++11)
并发支持库 (C++11)
技术规范
符号索引
外部库

std::partial_sum

参数

返回值

复杂度

可能的实现

示例

缺陷报告

参阅

导航