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 起) (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 不具有結合性或不具有交換性（例如浮點加法），則結果是不確定的。

如果以下任何值不可轉換為 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) 對範圍 [first, last) 中的每個元素應用 transform，並與初始值 init 一起透過 reduce 歸約結果（可能以未指定的方式置換和聚合）。

如果 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 的要求。

[edit] 返回值

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，直到組中只剩下一個元素。

[edit] 複雜度

給定 $\scriptsize N$ $N$ 為 std::distance(first1, last1)（或 std::distance(first, last) 用於過載 (5,6)）

1,2) 分別應用 std::plus<>() 和 std::multiplies<>()

O(N)

次。

3-6) 分別應用 reduce 和 transform

O(N)

次。

[edit] 異常

帶有模板引數 ExecutionPolicy 的過載按如下方式報告錯誤

如果作為演算法一部分呼叫的函式執行丟擲異常，並且 ExecutionPolicy 是標準策略之一，則呼叫 std::terminate。對於任何其他 ExecutionPolicy，行為是實現定義的。
如果演算法未能分配記憶體，則丟擲 std::bad_alloc。

[edit] 注意

transform 從未應用於 init。

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

[edit] 示例

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

[edit] 另請參閱

accumulate	對一個範圍的元素進行求和或摺疊 (函式模板) [編輯]
transform	對一個範圍的元素應用函式，並將結果儲存在目標範圍中 (函式模板) [編輯]
reduce (C++17)	類似於 std::accumulate，但順序是亂序的 (函式模板) [編輯]

編譯器支援
自由（freestanding）與宿主（hosted）
語言
標準庫
標準庫標頭檔案
具名要求
特性測試宏 (C++20)
語言支援庫
概念庫 (C++20)
診斷庫
記憶體管理庫
超程式設計庫 (C++11)
通用工具庫
容器庫
迭代器庫
範圍庫 (C++20)
演算法庫
字串庫
文字處理庫
數值庫
日期和時間庫
輸入/輸出庫
檔案系統庫 (C++17)
併發支援庫 (C++11)
執行控制庫 (C++26)
技術規範
符號索引
外部庫

cppreference.com

名稱空間

變體

檢視

操作