跳到主要内容

std::transform_reduce() 算法

// (1)
template< class InputIt1, class InputIt2, class T >
constexpr T transform_reduce( InputIt1 first1, InputIt1 last1, InputIt2 first2, T init );

// (2)
template< class InputIt1, class InputIt2, class T, class BinaryReductionOp, class BinaryTransformOp >
constexpr T transform_reduce( InputIt1 first1, InputIt1 last1, InputIt2 first2, T init,
                              BinaryReductionOp reduce, BinaryTransformOp transform );

// (3)
template< class InputIt, class T, class BinaryReductionOp, class UnaryTransformOp >
constexpr T transform_reduce( InputIt first, InputIt last, T init, BinaryReductionOp reduce,
                              UnaryTransformOp transform );

// (4)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T >
constexpr T transform_reduce( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2,
                              T init );

// (5)
template< class ExecutionPolicy,
          class ForwardIt1,
          class ForwardIt2,
          class T,
          class BinaryReductionOp,
          class BinaryTransformOp >
T transform_reduce( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, T init,
                    BinaryReductionOp reduce, BinaryTransformOp transform );

// (6)
template< class ExecutionPolicy, class ForwardIt, class T, class BinaryReductionOp, class UnaryTransformOp >
T transform_reduce( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, T init,
                    BinaryReductionOp reduce, UnaryTransformOp transform );

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

  • (2) 将转换应用于范围 [first; last) 和从 first2 开始的范围中的每对元素，并通过 reduce 将结果（可能以未指定的方式排列和聚合）与初始值 init 一起归约。

  • (3) 将转换应用于范围 [first; last) 中的每个元素，并通过 reduce 将结果（可能以未指定的方式排列和聚合）与初始值 init 一起归约

  • (4 - 6) 与 (1 - 3) 相同，但根据策略执行。

    重载决议

    这些重载只有在 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 起)

如果 reduce 不具有结合性或不具有交换性，则行为是非确定性的。

未定义行为

行为未定义

如果 reduce 或 transform 修改了输入范围中的任何元素或使任何迭代器（包括其结束迭代器）失效。

参数​

first
last

要应用算法的元素范围。

init

广义和的初始值。

policy

要使用的执行策略。有关详细信息，请参阅执行策略。

reduce

将以未指定顺序应用于 transform 的结果、其他 reduce 的结果和 init 的二元 函数对象。

transform

将应用于输入范围中每个元素的二元 函数对象。

类型要求​

InputItLegacyInputIterator
ForwardItLegacyForwardIterator

  • (3, 6):

    TMoveConstructible

    以下表达式必须可转换为 T

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

  • (2, 5):

    TMoveConstructible

    以下表达式必须可转换为 T

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

返回值​

  • (2) init 和 transform(*first, *first2), transform(*(first + 1), *(first2 + 1)), ... 在 reduce 上的广义和。
  • (3) init 和 transform(*first), transform(*(first + 1)), ... transform(*(last - 1)) 在 reduce 上的广义和。

transform 或 reduce 的结果可以以任意顺序分组和排列。

正式地，广义和 GSUM(op, a1, ..., aN) 定义如下

  • 如果 N = 1，则为 a1
  • 如果 N > 1, op(GSUM(op, b 1, ..., b K), GSUM(op, b M, ..., b N)) 其中
    • b1, ..., bN 可以是 a1, ..., aN 的任何排列
    • 且 1 < K + 1 = M ≤ N
重要

如果 first == last 或 first1 == last1, 返回未修改的 init。

复杂度​

  • (1, 2, 4, 5) 每次 reduce 和 transform 的应用次数为 O(last1 - first1)。
  • (3, 6) 每次 transform 和 reduce 的应用次数为 O(last - first)。

异常​

带有模板参数 ExecutionPolicy 的重载报告错误如下

  • 如果在算法执行过程中调用的函数抛出异常且 ExecutionPolicy 是标准策略之一，则会调用std::terminate。对于任何其他 ExecutionPolicy，行为是实现定义的.
  • 如果算法未能分配内存，则抛出 std::bad_alloc。

备注​

在 unary-binary 重载 (3, 6) 中，transform 不应用于 init。

示例​

Main.cpp
#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
本文源自此 CppReference 页面。它可能为了改进或编辑者的偏好而进行了修改。点击“编辑此页面”以查看此文档的所有更改。
悬停查看原始许可证。

std::transform_reduce() 算法

// (1)
template< class InputIt1, class InputIt2, class T >
constexpr T transform_reduce( InputIt1 first1, InputIt1 last1, InputIt2 first2, T init );

// (2)
template< class InputIt1, class InputIt2, class T, class BinaryReductionOp, class BinaryTransformOp >
constexpr T transform_reduce( InputIt1 first1, InputIt1 last1, InputIt2 first2, T init,
                              BinaryReductionOp reduce, BinaryTransformOp transform );

// (3)
template< class InputIt, class T, class BinaryReductionOp, class UnaryTransformOp >
constexpr T transform_reduce( InputIt first, InputIt last, T init, BinaryReductionOp reduce,
                              UnaryTransformOp transform );

// (4)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T >
constexpr T transform_reduce( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2,
                              T init );

// (5)
template< class ExecutionPolicy,
          class ForwardIt1,
          class ForwardIt2,
          class T,
          class BinaryReductionOp,
          class BinaryTransformOp >
T transform_reduce( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, T init,
                    BinaryReductionOp reduce, BinaryTransformOp transform );

// (6)
template< class ExecutionPolicy, class ForwardIt, class T, class BinaryReductionOp, class UnaryTransformOp >
T transform_reduce( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, T init,
                    BinaryReductionOp reduce, UnaryTransformOp transform );

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

  • (2) 将转换应用于范围 [first; last) 和从 first2 开始的范围中的每对元素，并通过 reduce 将结果（可能以未指定的方式排列和聚合）与初始值 init 一起归约。

  • (3) 将转换应用于范围 [first; last) 中的每个元素，并通过 reduce 将结果（可能以未指定的方式排列和聚合）与初始值 init 一起归约

  • (4 - 6) 与 (1 - 3) 相同，但根据策略执行。

    重载决议

    这些重载只有在 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 起)

如果 reduce 不具有结合性或不具有交换性，则行为是非确定性的。

未定义行为

行为未定义

如果 reduce 或 transform 修改了输入范围中的任何元素或使任何迭代器（包括其结束迭代器）失效。

参数​

first
last

要应用算法的元素范围。

init

广义和的初始值。

policy

要使用的执行策略。有关详细信息，请参阅执行策略。

reduce

将以未指定顺序应用于 transform 的结果、其他 reduce 的结果和 init 的二元 函数对象。

transform

将应用于输入范围中每个元素的二元 函数对象。

类型要求​

InputItLegacyInputIterator
ForwardItLegacyForwardIterator

  • (3, 6):

    TMoveConstructible

    以下表达式必须可转换为 T

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

  • (2, 5):

    TMoveConstructible

    以下表达式必须可转换为 T

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

返回值​

  • (2) init 和 transform(*first, *first2), transform(*(first + 1), *(first2 + 1)), ... 在 reduce 上的广义和。
  • (3) init 和 transform(*first), transform(*(first + 1)), ... transform(*(last - 1)) 在 reduce 上的广义和。

transform 或 reduce 的结果可以以任意顺序分组和排列。

正式地，广义和 GSUM(op, a1, ..., aN) 定义如下

  • 如果 N = 1，则为 a1
  • 如果 N > 1, op(GSUM(op, b 1, ..., b K), GSUM(op, b M, ..., b N)) 其中
    • b1, ..., bN 可以是 a1, ..., aN 的任何排列
    • 且 1 < K + 1 = M ≤ N
重要

如果 first == last 或 first1 == last1, 返回未修改的 init。

复杂度​

  • (1, 2, 4, 5) 每次 reduce 和 transform 的应用次数为 O(last1 - first1)。
  • (3, 6) 每次 transform 和 reduce 的应用次数为 O(last - first)。

异常​

带有模板参数 ExecutionPolicy 的重载报告错误如下

  • 如果在算法执行过程中调用的函数抛出异常且 ExecutionPolicy 是标准策略之一，则会调用std::terminate。对于任何其他 ExecutionPolicy，行为是实现定义的.
  • 如果算法未能分配内存，则抛出 std::bad_alloc。

备注​

在 unary-binary 重载 (3, 6) 中，transform 不应用于 init。

示例​

Main.cpp
#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
本文源自此 CppReference 页面。它可能为了改进或编辑者的偏好而进行了修改。点击“编辑此页面”以查看此文档的所有更改。
悬停查看原始许可证。