Skip to content

Latest commit

 

History

History
182 lines (149 loc) · 8.84 KB

transform_reduce.md

File metadata and controls

182 lines (149 loc) · 8.84 KB
Raw

transform_reduce

  • numeric[meta header]
  • std[meta namespace]
  • function template[meta id-type]
  • cpp17[meta cpp]
namespace std{
  template <class InputIterator1, class InputIterator2, class T>
  T transform_reduce(InputIterator1 first1,
                     InputIterator1 last1,
                     InputIterator2 first2,
                     T init);                      // (1)

  template <class InputIterator1, class InputIterator2, class T,
            class BinaryOperation1, class BinaryOperation2>
  T transform_reduce(InputIterator1 first1,
                     InputIterator1 last1,
                     InputIterator2 first2,
                     T init,
                     BinaryOperation1 binary_op1,
                     BinaryOperation2 binary_op2); // (2)

  template <class InputIterator, class T,
            class BinaryOperation, class UnaryOperation>
  T transform_reduce(InputIterator first,
                     InputIterator last,
                     T init,
                     BinaryOperation binary_op,
                     UnaryOperation unary_op);     // (3)

  template <class ExecutionPolicy,
            class ForwardIterator1, class ForwardIterator2, class T>
  T transform_reduce(ExecutionPolicy&& exec,
                     ForwardIterator1 first1,
                     ForwardIterator1 last1,
                     ForwardIterator2 first2,
                     T init);                      // (4)

  template <class ExecutionPolicy,
            class ForwardIterator1, class ForwardIterator2, class T,
            class BinaryOperation1, class BinaryOperation2>
  T transform_reduce(ExecutionPolicy&& exec,
                     ForwardIterator1 first1,
                     ForwardIterator1 last1,
                     ForwardIterator2 first2,
                     T init,
                     BinaryOperation1 binary_op1,
                     BinaryOperation2 binary_op2); // (5)

  template <class ExecutionPolicy,
            class ForwardIterator, class T,
            class BinaryOperation, class UnaryOperation>
  T transform_reduce(ExecutionPolicy&& exec,
                     ForwardIterator first,
                     ForwardIterator last,
                     T init,
                     BinaryOperation binary_op,
                     UnaryOperation unary_op);     // (6)
}

概要

transform_reduce()は、範囲の要素を変換しながら集計する関数である。

(1)、(2)、(4)、(5)は、範囲[first1, last1)の各要素をx、範囲[first2, first2+(last1 - first1))の各要素をyとして、初期値(init)とbinary_op2(x, y)した各要素を合算したリストの任意の組み合わせに、順不同でbinary_op1(binary_op1(a, b), binary_op1(c, d))のように適用していき、集計値を計算する。

(3)と(6)は、初期値(init)と、範囲[first, last)の各要素に関数オブジェクトunary_opを適用して合算したリストの任意の組み合わせに、順不同でbinary_op(binary_op(a, b), binary_op(c, d))のように適用していき、集計値を計算する。

  • (1) : リスト集計の二項演算にoperator+を使用し、2つの範囲の要素を掛け合わせる二項演算にoperator*を使用する
  • (2) : リスト集計の二項演算にbinary_op1を使用し、2つの範囲の要素を掛け合わせる二項演算にbinary_op2を使用する
  • (3) : リスト集計の二項演算にoperator+を使用し、各要素の変換にunary_opを使用する
  • (4) : (1)の並列アルゴリズム版。第1パラメータとして実行ポリシーをとる
  • (5) : (2)の並列アルゴリズム版。第1パラメータとして実行ポリシーをとる
  • (6) : (3)の並列アルゴリズム版。第1パラメータとして実行ポリシーをとる

要件

  • (1), (2), (4), (5) : 関数オブジェクトbinary_op1とbinary_op2の呼び出しは、範囲[first1, last1]と[first2, first2 + (last1 - first1)]の要素変更およびイテレータの無効化をしてはならない
  • (3), (6) : 関数オブジェクトunary_opとbinary_opの呼び出しは、範囲[first, last]の要素変更およびイテレータの無効化をしてはならない

テンプレートパラメータ制約

  • (1), (2), (3), (4), (5), (6) : 型Tがstd::move_constructible要件を満たすこと
  • (1), (2), (4), (5) : 以下の全ての演算結果の型が、型Tに変換可能であること
    • binary_op1(init, init)
    • binary_op1(init, binary_op2(*first1, *first2))
    • binary_op1(binary_op2(*first1, *first2), init)
    • binary_op1(binary_op2(*first1, *first2), binary_op2(*first1, *first2))
  • (3), (6) : 以下の全ての演算結果の型が、型Tに変換可能であること
    • binary_op(init, init)
    • binary_op(init, unary_op(*first))
    • binary_op(unary_op(*first), init)
    • binary_op(unary_op(*first), unary_op(*first))

効果

  • (1) : 以下と等価

    return transform_reduce(first1, last1, first2, init, plus<>(), multiplies<>);
    • plus[link /reference/functional/plus.md]
    • multiplies[link /reference/functional/multiplies.md]

  • (2), (5) : 範囲[first1, last1)と[first2, first2+(last1 - first1))について、リスト[init, binary_op2(*first1, *first2), binary_op2(*(first1 + 1), *(first2 + 1)), binary_op2(*(first1 + 2), *(first2 + 2)), ...]を任意の部分リストへ分割し、各部分リストの要素を順不同にbinary_op1(a, b)を実行していき、それを実行していった結果同士も順不同にbinary_op1(sum1, sum2)のように集計して返す

  • (3), (6) : 範囲[first, last)について、リスト[init, unary_op(*first), unary_op(*(first + 1)), unary_op(*(first + 2)), ... unary_op(*(first + (last - first - 1)))]を任意の部分リストへ分割し、各部分リストの要素を順不同にbinary_op(a, b)を実行していき、それを実行していった結果同士も順不同にbinary_op(sum1, sum2)のように集計して返す

  • (4) : 以下と等価

    return transform_reduce(std::forward<ExecutionPolicy>(exec),
                        first1, last1, first2, init, plus<>(), multiplies<>());
    • std::forward[link /reference/utility/forward.md]
    • plus[link /reference/functional/plus.md]
    • multiplies[link /reference/functional/multiplies.md]

計算量

  • (1), (2), (4), (5) : 関数オブジェクトbinary_op1とbinary_op2を、O(last1 - first1)計算量の回数だけ適用する
  • (3), (6) : 関数オブジェクトunary_opとbinary_opをO(last - first)計算量の回数だけ適用する

備考

  • (3), (6) : 関数オブジェクトunary_opは初期値initに対しては適用しない

例

#include <iostream>
#include <vector>
#include <numeric>

int main()
{
  const std::vector<int> v1 = {1, 2, 3, 4, 5};
  const std::vector<int> v2 = {2, 3, 4, 5, 6};

  // (1) : 2つのリストを集計する
  // sum1 = 1*2 + 2*3 + 3*4 + 4*5, 5*6
  int sum1 = std::transform_reduce(v1.begin(), v1.end(), v2.begin(), 0);
  std::cout << "sum1 : " << sum1 << std::endl;

  // (2) : 2つのリストを集計する。
  // リストを集計する2項演算と、2つのリストの要素を掛け合わせる2項演算を指定する
  int sum2 = std::transform_reduce(v1.begin(), v1.end(), v2.begin(), 0,
                                  [](int a, int b) { return a + b; },  // 集計関数
                                  [](int a, int b) { return a * b; }); // 2つの要素を合成する関数
  std::cout << "sum2 : " << sum2 << std::endl;

  // (3) : リストの各要素を変換しながら集計する
  // 1*2 + 2*2 + 3*2 + 4*2 + 5*2
  int sum3 = std::transform_reduce(v1.begin(), v1.end(), 0,
                                   [](int acc, int i) { return acc + i; }, // 集計関数
                                   [](int x) { return x * 2; });           // 変換関数
  std::cout << "sum3 : " << sum3 << std::endl;
}
  • std::transform_reduce[color ff0000]

出力

sum1 : 70
sum2 : 70
sum3 : 30

バージョン

言語

  • C++17

処理系

参照