reduce 与 transform_reduce（概览）

通常用于并行执行的六个新算法中，扫描类算法属于前缀和操作。如果所提供的二元可调用对象不满足结合律和交换律，则这些算法的行为是未定义的。

reduce

对该范围内的元素进行归约操作，init 为初始值。

• 行为与 std::accumulate 类似，但允许对范围内的元素重新排列。

1ValType reduce(InpIt first, InpIt last)
2ValType reduce(ExePol pol, InpIt first, InpIt last)
3
4T reduce(InpIt first, InpIt last, T init)
5T reduce(ExePol pol, InpIt first, InpIt last, T init)
6
7T reduce(InpIt first, InpIt last, T init, BiFun fun)
8T reduce(ExePol pol, InpIt first, InpIt last, T init, BiFun fun)

transform_reduce

对一个或两个范围内的元素先进行变换再进行归约，init 为初始值。

• 行为类似于 std::inner_product，但允许对范围内的元素重新排列。
• 若作用于两个范围：
  • 若未提供函数，则使用乘法将两个范围合并为一个中间序列，并使用加法将该中间序列归约为最终结果；
  • 若提供了函数，则 fun1 用于归约步骤，fun2 用于变换步骤（即两两组合）。
• 若作用于单个范围：
  • 使用 fun2 对给定范围中的每个元素进行变换，再使用 fun1 将变换后的结果归约为最终值

1T transform_reduce(InpIt first, InpIt last, InpIt first2, T init)
2T transform_reduce(InpIt first, InpIt last, InpIt first2, T init, BiFun fun1, BiFun fun2)              
3
4T transform_reduce(FwdIt first, FwdIt last, FwdIt first2, T init)
5T transform_reduce(ExePol pol, FwdIt first, FwdIt last, FwdIt first2, T init, BiFun fun1, BiFun fun2)
6
7T transform_reduce(InpIt first, InpIt last, T init, BiFun fun1, UnFun fun2)
8T transform_reduce(ExePol pol, FwdIt first, FwdIt last, T init, BiFun fun1, UnFun fun2)

ℹ️ C++17 中的 MapReduce
Haskell 语言中的 map 函数在 C++ 中对应的是 std::transform。若将 std::transform_reduce 中的 "transform" 替换为 "map"，即可得到类似 map-reduce 的模式（标准库中并没有 std::map_reduce）。MapReduce 是著名的并行计算框架，其分为两个阶段：第一阶段将每个输入值映射为新的值（map），第二阶段将所有中间结果归约为最终结果（reduce）。

该算法在 C++17 中可直接实现。以下示例中，在 map 阶段将每个单词映射为其长度，在 reduce 阶段将所有长度累加求和，最终结果即为所有单词长度之和。

1std::vector<std::string> str{"Only", "for", "testing", "purpose"};
2
3std::size_t result = std::transform_reduce(
4                        std::execution::par, str.begin(), str.end(), 0, 
5                        [](std::size_t a, std::size_t b){ return a + b; },
6                        [](std::string s){ return s.length(); }
7                     ); 
8
9std::cout << result << std::endl;      //   21