std::transform_reduce

定义于头文件 `<numeric>`
template< class InputIt1, class InputIt2, class T > T transform_reduce( InputIt1 first1, InputIt1 last1, InputIt2 first2, T init );	(1)	(自 C++17 起) (constexpr 自 C++20 起)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T > T transform_reduce( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, T init );	(2)	(自 C++17 起)
template< class InputIt1, class InputIt2, class T, class BinaryOp1, class BinaryOp2 > T transform_reduce( InputIt1 first1, InputIt1 last1, InputIt2 first2, T init, BinaryOp1 reduce, BinaryOp2 transform );	(3)	(自 C++17 起) (constexpr 自 C++20 起)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T, class BinaryOp1, class BinaryOp2 > T transform_reduce( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, T init, BinaryOp1 reduce, BinaryOp2 transform );	(4)	(自 C++17 起)
template< class InputIt, class T, class BinaryOp, class UnaryOp > T transform_reduce( InputIt first, InputIt last, T init, BinaryOp reduce, UnaryOp transform );	(5)	(自 C++17 起) (constexpr 自 C++20 起)
template< class ExecutionPolicy, class ForwardIt, class T, class BinaryOp, class UnaryOp > T transform_reduce( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, T init, BinaryOp reduce, UnaryOp transform );	(6)	(自 C++17 起)

1) 等价于 transform_reduce(first1, last1, first2, init,
std::plus<>(), std::multiplies<>())，有效地并行化版本的默认 std::inner_product。

3) 将 transform 应用于范围 [first1, last1) 和从 first2 开始的 std::distance(first1, last1) 个元素的范围中的每对元素，并使用 reduce 将结果（可能经过置换和以未指定方式聚合）与初始值 init 一起归约。

如果 reduce 不满足结合律或交换律（例如浮点加法），则结果是不确定的。

如果以下任何值无法转换为 T，则程序是非良构的

reduce(init, init)
reduce(init, transform(*first1, *first2))
reduce(transform(*first1, *first2), init)
reduce(transform(*first1, *first2), transform(*first1, *first2))

给定 last2 作为 std::distance(first1, last1) 的第 th 个后继迭代器 first2，如果满足以下任何条件，则行为未定义

T 不是 MoveConstructible。
transform 或 reduce 修改范围 [first1, last1) 或 [first2, last2) 中的任何元素。
transform 或 reduce 使范围 [first1, last1] 或 [first2, last2] 中的任何迭代器或子范围失效。

5) 将 transform 应用于范围 [first, last) 中的每个元素，并使用 reduce 将结果（可能经过置换和以未指定方式聚合）与初始值 init 一起归约。

如果 reduce 不满足结合律或交换律（例如浮点加法），则结果是不确定的。

如果以下任何值无法转换为 T，则程序是非良构的

reduce(init, init)
reduce(init, transform(*first))
reduce(transform(*first), init)
reduce(transform(*first), transform(*first))

如果满足以下任何条件，则行为未定义

T 不是 MoveConstructible。
transform 或 reduce 修改范围 [first, last) 中的任何元素。
transform 或 reduce 使范围 [first, last] 中的任何迭代器或子范围失效。

2,4,6) 与 (1,3,5) 相同，但根据 policy 执行。

仅当满足以下所有条件时，这些重载才参与重载决议

std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> 为 true。	(C++20 之前)
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> 为 true。	(自 C++20 起)

[编辑] 参数

first1, last1	-	定义要作为 transform 的左操作数的范围的迭代器对
first2	-	要作为 transform 的右操作数的元素范围的起始
first, last	-	定义要作为 transform 的操作数的范围的迭代器对
init	-	广义和的初始值
policy	-	要使用的执行策略
reduce	-	二元函数对象，它将以未指定的顺序应用于 transform 的结果、其他 reduce 的结果和 init。
transform	-	一元或二元函数对象，它将应用于输入范围的每个元素。返回类型必须可接受作为 reduce 的输入。
类型要求
- `InputIt1, InputIt2, InputIt` 必须满足 LegacyInputIterator 的要求。
- `ForwardIt1, ForwardIt2, ForwardIt` 必须满足 LegacyForwardIterator 的要求。

[编辑] 返回值

1,2) init 和 values 在 std::plus<>() 上的广义和，其中 values 是由 std::multiplies<>() 变换的值，每个值都从两个输入范围中的一对元素变换而来。

3,4) init 和 values 在 reduce 上的广义和，其中 values 是由 transform 变换的值，每个值都从两个输入范围中的一对元素变换而来。

5,6) init 和 values 在 reduce 上的广义和，其中 values 是由 transform 变换的值，每个值都从输入范围中的一个元素变换而来。

一组元素在二元操作 binary_op 上的广义和定义如下

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

从该组中取出任意两个元素 elem1 和 elem2。
计算 binary_op(elem1, elem2) 并将结果放回该组。
重复步骤 1 和 2，直到该组中只有一个元素。

[编辑] 复杂度

给定 $\scriptsize N$ $N$ 为 std::distance(first1, last1) (或对于重载 (5,6) 为 std::distance(first, last) )

1,2) 分别为

O(N)

次 std::plus<>() 和 std::multiplies<>() 的应用。

3-6) 分别为

O(N)

次 reduce 和 transform 的应用。

[编辑] 异常

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

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

[编辑] 注解

transform 永远不会应用于 init。

如果 first == last 或 first1 == last1，则返回 init，不修改。

[编辑] 示例

transform_reduce 可用于并行化 std::inner_product。某些系统可能需要额外的支持才能获得并行执行的优势。例如，在 GNU/Linux 上，需要安装 Intel TBB 并在 gcc/clang 编译器中提供 -ltbb 选项。

运行此代码

#if PARALLEL
#include <execution>
#define PAR std::execution::par,
#else
#define PAR
#endif
 
#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <locale>
#include <numeric>
#include <vector>
 
// to parallelize non-associate accumulative operation, you'd better choose
// transform_reduce instead of reduce; e.g., a + b * b != b + a * a
void print_sum_squared(long const num)
{
    std::cout.imbue(std::locale{"en_US.UTF8"});
    std::cout << "num = " << num << '\n';
 
    // create an immutable vector filled with pattern: 1,2,3,4, 1,2,3,4 ...
    const std::vector<long> v{[n = num * 4] {
        std::vector<long> v;
        v.reserve(n);
        std::generate_n(std::back_inserter(v), n,
            [i = 0]() mutable { return 1 + i++ % 4; });
        return v;
    }()};
 
    auto squared_sum = [](auto sum, auto val) { return sum + val * val; };
 
    auto sum1 = std::accumulate(v.cbegin(), v.cend(), 0L, squared_sum);
    std::cout << "accumulate(): " << sum1 << '\n';
 
    auto sum2 = std::reduce(PAR v.cbegin(), v.cend(), 0L, squared_sum);
    std::cout << "reduce(): " << sum2 << '\n';
 
    auto sum3 = std::transform_reduce(PAR v.cbegin(), v.cend(), 0L, std::plus{},
                                      [](auto val) { return val * val; });
    std::cout << "transform_reduce(): " << sum3 << "\n\n";
}
 
int main()
{
    print_sum_squared(1);
    print_sum_squared(1'000);
    print_sum_squared(1'000'000);
}

可能的输出

num = 1
accumulate(): 30
reduce(): 30
transform_reduce(): 30
 
num = 1,000
accumulate(): 30,000
reduce(): -7,025,681,278,312,630,348
transform_reduce(): 30,000
 
num = 1,000,000
accumulate(): 30,000,000
reduce(): -5,314,886,882,370,003,032
transform_reduce(): 30,000,000
 
// Compile-options for parallel execution on POSIX:
// g++ -O2 -std=c++17 -Wall -Wextra -pedantic -DPARALLEL ./example.cpp -ltbb -o tr; ./tr

[编辑] 参见

accumulate	对元素范围求和或折叠 (函数模板) [编辑]
transform	将函数应用于元素范围，并将结果存储在目标范围中 (函数模板) [编辑]
reduce (C++17)	类似于 std::accumulate，但顺序错乱 (函数模板) [编辑]

编译器支持
独立和宿主
语言
标准库
标准库头文件
具名要求
特性测试宏 (C++20)
语言支持库
概念库 (C++20)
诊断库
内存管理库
元编程库 (C++11)
通用工具库
容器库
迭代器库
范围库 (C++20)
算法库
字符串库
文本处理库
数值库
日期和时间库
输入/输出库
文件系统库 (C++17)
并发支持库 (C++11)
执行控制库 (C++26)
技术规范
符号索引
外部库

cppreference.cn

命名空间

变体

视图

操作