std:: partial_sum

给定 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 ] 中的任意迭代器或子范围失效。

1. ↑ 实际赋值的值应为前一步赋值操作的结果。此处我们假定赋值结果为 acc 。

参数

返回值

指向最后被写入元素之后位置的迭代器，若 [ first , last ) 为空范围则返回 d_first 。

复杂度

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

可能的实现

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 BinaryOp>
constexpr // 自 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); // 自 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];
// 正确：使用 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);
// 正确：在需要时执行类型转换
// 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';
    // 将结果写回向量 v
    std::partial_sum(v.cbegin(), v.cend(),
                     v.begin(), std::multiplies<int>());
    std::cout << "前 " << v.size() << " 个 2 的幂为: ";
    for (int n : v)
        std::cout << n << ' ';
    std::cout << '\n';
}

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

缺陷报告

下列行为变更缺陷报告被追溯应用于先前发布的 C++ 标准。

参见