前缀和是累积计算从首元素到当前元素的和;std::inclusive_scan包含当前元素,结果为[1,3,6,10];std::exclusive_scan不包含当前元素,结果为[0,1,3,6];两者均支持并行执行策略提升性能。

在C++17中,std::inclusive_scan 和 std::exclusive_scan 是标准库算法中用于计算前缀和的函数,定义在头文件 中。它们属于“并行算法”(Parallel Algorithms)的一部分,支持串行、并行和向量化执行策略,可用于提升大规模数据处理的性能。
什么是前缀和?
前缀和(Prefix Sum)是一种累积操作:对序列中的每个位置,计算从起始位置到该位置所有元素的累加结果。例如,对数组 [1, 2, 3, 4]:
-
包含自身(inclusive) 的前缀和是:
[1, 3, 6, 10] -
不包含自身(exclusive) 的前缀和是:
[0, 1, 3, 6],即当前位置之前所有元素的和
std::inclusive_scan 解释
该函数计算包含当前元素的前缀和。其基本形式如下:
std::inclusive_scan(first, last, d_first);它将区间 [first, last) 的元素进行累加,并将结果写入从 d_first 开始的目标区间。
立即学习“C++免费学习笔记(深入)”;
支持自定义二元操作符(如乘法、最大值等),默认使用加法。
示例:
#include#include
#include iostream>
std::vector
std::vector
std::inclusive_scan(data.begin(), data.end(), result.begin());
// result: [1, 3, 6, 10]
std::exclusive_scan 解释
该函数计算不包含当前元素的前缀和。第一个输出元素通常是初始值(默认为0)。
std::exclusive_scan(first, last, d_first, init);其中 init 是初始值,通常为0。如果未提供,则使用元素类型的默认值。
示例:
std::vectorstd::vector
std::exclusive_scan(data.begin(), data.end(), result.begin(), 0);
// result: [0, 1, 3, 6]
并行执行支持
C++17允许使用执行策略来控制这些算法的执行方式:
-
std::execution::seq:串行执行 -
std::execution::par:并行执行 -
std::execution::par_unseq:并行且允许向量化
例如,启用并行版本:
#includestd::inclusive_scan(std::execution::par, data.begin(), data.end(), result.begin());
这对大型数据集能显著提升性能,尤其在多核系统上。
基本上就这些。这两个函数提供了高效、安全且可并行的前缀和计算方式,适合替代手动编写的循环,尤其适用于数值计算、图像处理、并行归约等场景。理解它们的区别在于是否“包含当前元素”,就能正确选择使用哪一个。










