std::partial_sum

来自cppreference.com
< cpp‎ | algorithm
 
C++
 
算法库
受约束算法及范围上的算法 (C++20)
受约束算法： std::ranges::copy, std::ranges::sort, ...
执行策略 (C++17)
不修改序列的操作
(C++11)(C++11)(C++11)
(C++17)
修改序列的操作
Partitioning operations
划分操作
排序操作
(C++11)
(C++11)
二分搜索操作
集合操作（在已排序范围上）
堆操作
(C++11)
(C++11)
最小/最大操作
(C++11)
(C++11)
(C++17)

排列
数值运算
partial_sum
(C++17)
(C++17)
未初始化存储上的操作
(C++17)
(C++17)
(C++17)
(C++20)
C 库
 
在标头 <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 开始的范围，两个重载都会将 std::move 应用到它们的左侧运算数 (C++11 起)。

在内部使用类型是 InputIt 的值类型的变量 acc 作为存储中间结果的累加器。

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 - 要求和的元素范围
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) 的要求。它的值类型必须能够从 *first 构造。
-
OutputIt 必须符合老式输出迭代器 (LegacyOutputIterator) 的要求。acc（在上文定义）必须可写入 d_first。

返回值

返回指向最后被写入元素后一元素的迭代器，或者在 [first, last) 为空时返回 d_first。

复杂度

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

1) 应用 N 次 operator+
2) 应用 N 次二元函数 op

可能的实现

版本一 
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++11 起有 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 acc = *first;
    *d_first = acc;
 
    while (++first != last)
    {
        acc = op(std::move(acc), *first); // C++11 起有 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 缺失了需要保证对结果的求值和赋值合法的条件要求 已补充
LWG 2055
(P0616R0) 		C++11 acc 在累加时不会被移动 它会被移动

参阅

 计算范围内各相邻元素之间的差
(函数模板)
对一个范围内的元素求和
(函数模板)
(C++17)
 类似 std::partial_sum，第 i 个和中包含第 i 个输入
(函数模板)
(C++17)
 类似 std::partial_sum，第 i 个和中排除第 i 个输入
(函数模板)
来自“https://zh.cppreference.com/mwiki/index.php?title=cpp/algorithm/partial_sum&oldid=76866”