4. reduce

最終更新日時(UTC):
が更新

履歴 編集

function template
<numeric>

std::reduce(C++17)

namespace std{
  template <class InputIterator>
  typename iterator_traits<InputIterator>::value_type
    reduce(InputIterator first, InputIterator last);         // (1) C++17
  template <class InputIterator>
  constexpr typename iterator_traits<InputIterator>::value_type
    reduce(InputIterator first, InputIterator last);         // (1) C++20

  template <class InputIterator, class T>
  T reduce(InputIterator first, InputIterator last, T init); // (2) C++17
  template <class InputIterator, class T>
  constexpr T
    reduce(InputIterator first, InputIterator last, T init); // (2) C++20

  template <class InputIterator, class T, class BinaryOperation>
  T reduce(InputIterator first, InputIterator last, T init,
           BinaryOperation binary_op);                       // (3) C++17
  template <class InputIterator, class T, class BinaryOperation>
  constexpr T
    reduce(InputIterator first, InputIterator last, T init,
           BinaryOperation binary_op);                       // (3) C++20

  template <class ExecutionPolicy, class ForwardIterator>
  typename iterator_traits<ForwardIterator>::value_type
    reduce(ExecutionPolicy&& exec,
           ForwardIterator first,
           ForwardIterator last);                            // (4) C++17

  template <class ExecutionPolicy, class ForwardIterator, class T>
  T reduce(ExecutionPolicy&& exec,
           ForwardIterator first,
           ForwardIterator last,
           T init);                                          // (5) C++17

  template <class ExecutionPolicy, class ForwardIterator, class T, class BinaryOperation>
  T reduce(ExecutionPolicy&& exec,
           ForwardIterator first,
           ForwardIterator last,
           T init,
           BinaryOperation binary_op);                       // (6) C++17
}

概要

reduce()は、イテレータ範囲[first, last)を集計する関数である。accumulate()関数は範囲の先頭から順に要素を集計するが、この関数は並列計算のために集計順を規定しない。

初期値(init)とイテレータ範囲[first, last)を合算したリストの任意の組み合わせに、順不同でbinary_op(binary_op(a, b), binary_op(c, d))のように適用していき、集計値を計算する。

  • (1) : 集計の初期値をイテレータ範囲の要素型の値初期化値 (算術型なら0) とし、二項演算にoperator+を使用する。それによって、このオーバーロードは、範囲の合計値を求める処理となる
  • (2) : 初期値をパラメータinitとして受け取り、二項演算はoperator+を使用する
  • (3) : 初期値をパラメータinitとして受け取り、任意の二項演算binary_opを使用して集計を行う
  • (4) : (1)の並列アルゴリズム版。第1パラメータとして実行ポリシーをとる
  • (5) : (2)の並列アルゴリズム版。第1パラメータとして実行ポリシーをとる
  • (6) : (3)の並列アルゴリズム版。第1パラメータとして実行ポリシーをとる

要件

  • (3), (6) : 関数オブジェクトbinary_opの呼び出しは、イテレータ範囲[first, last]の要素変更およびイテレータの無効化をしてはならない

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

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

効果

  • (1) : 以下と等価 

    return reduce(first, last,
              typename iterator_traits<InputIterator>::value_type{});

  • (2) : 以下と等価 

    return reduce(first, last, init, plus<>());

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

  • (4) : 以下と等価 

    return reduce(std::forward<ExecutionPolicy>(exec), first, last,
              typename iterator_traits<ForwardIterator>::value_type{});

  • (5) : 以下と等価 

    return reduce(std::forward<ExecutionPolicy>(exec), first, last, init, plus<>());

計算量

関数オブジェクトbinary_opをO(last - first)回だけ適用する

例

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

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

  // (1) : 合計値を求める
  // イテレータの要素型で集計される
  int sum = std::reduce(v.begin(), v.end());
  std::cout << "sum : " << sum << std::endl;

  // (2) : 合計値をlong long型として求める
  // reduceの第3引数がlong long型のゼロを表す0LLになっていることに注意
  // reduceの戻り値型は、第3引数の型となるため、変数sum_llの型はlong long
  auto sum_ll = std::reduce(v.begin(), v.end(), 0LL);
  std::cout << "sum_ll : " << sum_ll << std::endl;

  // (3) : 任意の二項演算を行う
  // ここでは、初期値を1として、全ての要素を掛け合わせている
  int product = std::reduce(v.begin(), v.end(), 1, [](int acc, int i) {
    return acc * i;
  });
  std::cout << "product : " << product << std::endl;
}

出力

sum : 15
sum_ll : 15
product : 120

バージョン

言語

  • C++17

処理系

参照