std:: inclusive_scan

一个元素序列关于二元运算 binary_op 的 广义非交换和 定义如下：

• 如果序列只有一个元素，则总和为该元素的值。
• 否则，按顺序执行以下操作：

1. 从序列中选择任意两个相邻元素 elem1 和 elem2 。
2. 计算 binary_op ( elem1, elem2 ) 并将序列中的这两个元素替换为计算结果。
3. 重复步骤1和2，直到序列中仅剩一个元素。

给定 binary_op 作为实际的二元操作：

• 如果 binary_op 不具有结合性（例如浮点数加法），则结果将是非确定性的。

• 对于重载 (1-4) ，若 binary_op ( * first, * first ) 无法转换为 decltype ( first ) 的 值类型 ，则程序非良构。

• 对于重载 (5,6) ，若下列任一值无法转换为 T 类型，则程序非良构：

• binary_op ( init, * first )
• binary_op ( init, init )
• binary_op ( * first, * first )

• 若满足以下任一条件，则行为未定义：

• 对于重载 (1-4) ， decltype ( first ) 的值类型不满足 MoveConstructible 要求。
• 对于重载 (5,6) ， T 不满足 MoveConstructible 要求。
• binary_op 修改了 [ first , last ) 范围内的任何元素。
• binary_op 使 [ first , last ] 范围内的任何迭代器或子区间失效。

参数

返回值

指向已写入的最后一个元素之后位置的迭代器。

复杂度

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

异常

带有名为 ExecutionPolicy 模板参数的重载按如下方式报告错误：

• 如果作为算法一部分调用的函数执行抛出异常，且 ExecutionPolicy 是某个 标准策略 ，则调用 std::terminate 。对于其他任何 ExecutionPolicy ，行为由实现定义。
• 如果算法无法分配内存，则抛出 std::bad_alloc 。

示例

#include <functional>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>
int main()
{
    std::vector data{3, 1, 4, 1, 5, 9, 2, 6};
    std::cout << "Exclusive sum: ";
    std::exclusive_scan(data.begin(), data.end(),
                        std::ostream_iterator<int>(std::cout, " "),
                        0);
    std::cout << "\nInclusive sum: ";
    std::inclusive_scan(data.begin(), data.end(),
                        std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n\nExclusive product: ";
    std::exclusive_scan(data.begin(), data.end(),
                        std::ostream_iterator<int>(std::cout, " "),
                        1, std::multiplies<>{});
    std::cout << "\nInclusive product: ";
    std::inclusive_scan(data.begin(), data.end(),
                        std::ostream_iterator<int>(std::cout, " "),
                        std::multiplies<>{});
}

Exclusive sum: 0 3 4 8 9 14 23 25
Inclusive sum: 3 4 8 9 14 23 25 31
Exclusive product: 1 3 3 12 12 60 540 1080
Inclusive product: 3 3 12 12 60 540 1080 6480

参见