std::inclusive_scan 算法详解

在 C++17 中，std::inclusive_scan 是一个非常有用的算法，它属于 C++ 标准库中的 <numeric> 头文件。std::inclusive_scan 是一个并行算法，用于计算前缀和（或前缀操作），并将结果存储在输出迭代器中。它类似于 std::partial_sum，但有一些重要的区别。

1. std::inclusive_scan 的定义

std::inclusive_scan 是 C++17 引入的算法，用于计算前缀和（或前缀操作）。它的名字来源于“inclusive”（包含），表示每个结果元素都包含当前元素在内的所有前面元素的累积操作结果。

2. 函数原型

std::inclusive_scan 的函数原型如下：

#include <numeric>

template <class InputIt, class OutputIt>
OutputIt inclusive_scan(InputIt first, InputIt last, OutputIt d_first);

template <class InputIt, class OutputIt, class BinaryOperation>
OutputIt inclusive_scan(InputIt first, InputIt last, OutputIt d_first, BinaryOperation binary_op);

template <class InputIt, class OutputIt, class BinaryOperation, class T>
OutputIt inclusive_scan(InputIt first, InputIt last, OutputIt d_first, BinaryOperation binary_op, T init);

3. 参数说明

• first 和 last：输入范围的起始和结束迭代器。
• d_first：输出迭代器，用于存储结果。
• binary_op：可选的二元操作函数，默认为加法操作。
• init：可选的初始值，用于累积操作的起始值。

4. 行为

• 无初始值版本：如果未提供初始值，std::inclusive_scan 会从范围的第一个元素开始计算累积操作。
• 有初始值版本：如果提供了初始值，累积操作会从初始值开始，并将初始值作为第一个输出结果。

5. 与 std::partial_sum 的区别

• std::partial_sum：计算前缀和，但不包含初始值（如果提供了初始值）。它从范围的第一个元素开始计算累积操作。
• std::inclusive_scan：计算前缀和，但始终包含初始值（如果提供了初始值）。它从初始值开始计算累积操作。

6. 示例代码

以下是一些使用 std::inclusive_scan 的示例代码。

示例 1：默认加法操作

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int> input = {1, 2, 3, 4, 5};
    std::vector<int> result(input.size());

    std::inclusive_scan(input.begin(), input.end(), result.begin());

    for (int val : result) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出：

1 3 6 10 15

解释：

result[0] = input[0] = 1
result[1] = input[0] + input[1] = 1 + 2 = 3
result[2] = input[0] + input[1] + input[2] = 1 + 2 + 3 = 6
以此类推。

示例 2：自定义二元操作

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int> input = {1, 2, 3, 4, 5};
    std::vector<int> result(input.size());

    std::inclusive_scan(input.begin(), input.end(), result.begin(), std::multiplies<int>());

    for (int val : result) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出：

1 2 6 24 120

解释：

result[0] = input[0] = 1
result[1] = input[0] * input[1] = 1 * 2 = 2
result[2] = input[0] * input[1] * input[2] = 1 * 2 * 3 = 6
以此类推。

示例 3：带有初始值

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int> input = {1, 2, 3, 4, 5};
    std::vector<int> result(input.size() + 1); // 输出结果多一个位置用于初始值

    std::inclusive_scan(input.begin(), input.end(), result.begin() + 1, std::plus<int>(), 10);

    for (int val : result) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出：

10 11 13 16 20 25

解释：

result[0] = 10（初始值）
result[1] = 10 + input[0] = 10 + 1 = 11
result[2] = 10 + input[0] + input[1] = 10 + 1 + 2 = 13
以此类推。

7. 总结

std::inclusive_scan 是一个非常强大的算法，适用于需要计算前缀和或前缀操作的场景。它与 std::partial_sum 的主要区别在于是否包含初始值。通过灵活使用 std::inclusive_scan，可以实现高效的前缀操作计算。