std:: transform_reduce

From cppreference.net

定义于头文件 `<numeric>`
template < class InputIt1, class InputIt2, class T > T transform_reduce ( InputIt1 first1, InputIt1 last1, InputIt2 first2, T init ) ;	(1)	(C++17 起) (C++20 起为 constexpr)
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 起) (C++20 起为 constexpr)
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 起) (C++20 起为 constexpr)
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) 对范围

first1

last1

中的每个元素对以及从 first2 开始的 std:: distance ( first1, last1 ) 个元素范围应用 transform ，并将结果（可能以未指定的方式重排和聚合）与初始值 init 通过 reduce 进行归约。

如果 reduce 操作不满足结合律或交换律（例如浮点数加法），则结果将具有不确定性。

若以下任一值无法转换为

，则程序非良构：

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 ) 第个 first2 的后继迭代器，若满足以下任意条件，则行为未定义：

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

5) 对范围

first

last

中的每个元素应用 transform ，并将转换结果（可能以未指定的方式重排和聚合）与初始值 init 通过 reduce 进行归约。

如果 reduce 操作不满足结合律或交换律（例如浮点数加法），则结果将具有不确定性。

若下列任一值无法转换为

，则程序非良构：

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 与经 transform 转换后的 values 在 reduce 上的广义和，其中每个转换后的值均来自输入范围的元素。

一组元素在二元运算 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
// 在 POSIX 系统上并行执行的编译选项：
// g++ -O2 -std=c++17 -Wall -Wextra -pedantic -DPARALLEL ./example.cpp -ltbb -o tr; ./tr

参见

accumulate	对范围内的元素进行求和或折叠操作 (函数模板)
transform	对范围内的元素应用函数，并将结果存储到目标范围 (函数模板)
reduce (C++17)	类似于 std::accumulate ，但支持乱序执行 (函数模板)

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

cppreference.net

Namespaces

Variants

std:: transform_reduce

目录

参数

返回值

复杂度

异常

注释

示例

参见