std::exclusive_scan 算法详解

std::exclusive_scan 是 C++17 引入的另一个强大的算法，与 std::inclusive_scan 类似，但它计算的是“排他性前缀操作”。它属于 <numeric> 头文件中的并行算法，用于计算前缀和（或前缀操作），并将结果存储在输出迭代器中。与 std::inclusive_scan 的主要区别在于，std::exclusive_scan 的每个结果元素不包含当前元素，而是包含当前元素之前的所有元素的累积操作结果。

1. std::exclusive_scan 的定义

std::exclusive_scan 是一个算法，用于计算前缀和（或前缀操作），但每个结果元素不包含当前元素。它的名字来源于“exclusive”（排他），表示每个结果元素不包含当前元素的值。

2. 函数原型

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

#include <numeric>

template <class InputIt, class OutputIt, class T>
OutputIt exclusive_scan(InputIt first, InputIt last, OutputIt d_first, T init);

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

3. 参数说明

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

4. 行为

• std::exclusive_scan 的结果中，每个元素是当前元素之前的所有元素的累积操作结果，加上初始值（如果提供了初始值）。
• 初始值：初始值是累积操作的起始值，也是输出范围的第一个元素。

5. 与 std::inclusive_scan 的区别

• std::inclusive_scan：每个结果元素包含当前元素的值。
• std::exclusive_scan：每个结果元素不包含当前元素的值，而是包含当前元素之前的所有元素的累积操作结果。

6. 示例代码

示例 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::exclusive_scan(input.begin(), input.end(), result.begin(), 0);

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

    return 0;
}

输出：

0 1 3 6 10

解释：

result[0] = 0（初始值）
result[1] = 0 + input[0] = 0 + 1 = 1
result[2] = 0 + input[0] + input[1] = 0 + 1 + 2 = 3
result[3] = 0 + input[0] + input[1] + input[2] = 0 + 1 + 2 + 3 = 6
result[4] = 0 + input[0] + input[1] + input[2] + input[3] = 0 + 1 + 2 + 3 + 4 = 10

示例 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::exclusive_scan(input.begin(), input.end(), result.begin(), 1, std::multiplies<int>());

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

    return 0;
}

输出：

1 1 2 6 24

解释：

result[0] = 1（初始值）
result[1] = 1 * input[0] = 1 * 1 = 1
result[2] = 1 * input[0] * input[1] = 1 * 1 * 2 = 2
result[3] = 1 * input[0] * input[1] * input[2] = 1 * 1 * 2 * 3 = 6
result[4] = 1 * input[0] * input[1] * input[2] * input[3] = 1 * 1 * 2 * 3 * 4 = 24

示例 3：带有初始值

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

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

    std::exclusive_scan(input.begin(), input.end(), result.begin(), 10);

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

    return 0;
}

输出：

10 11 13 16 20

解释：

result[0] = 10（初始值）
result[1] = 10 + input[0] = 10 + 1 = 11
result[2] = 10 + input[0] + input[1] = 10 + 1 + 2 = 13
result[3] = 10 + input[0] + input[1] + input[2] = 10 + 1 + 2 + 3 = 16
result[4] = 10 + input[0] + input[1] + input[2] + input[3] = 10 + 1 + 2 + 3 + 4 = 20

7. 总结

std::exclusive_scan 是一个非常强大的算法，适用于需要计算“排他性前缀操作”的场景。它与 std::inclusive_scan 的主要区别在于，std::exclusive_scan 的每个结果元素不包含当前元素的值。通过灵活使用 std::exclusive_scan，可以实现高效的前缀操作计算，特别是在需要处理初始值或自定义操作时。