• Class / Function / Type

      std::
    • Header file

      <>
    • Other / All

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

    履歴 編集

    function template
    <numeric>

    std::accumulate

    namespace std {
      template <class InputIterator, class T>
      T accumulate(InputIterator first, InputIterator last, T init);           // (1) C++03
      template <class InputIterator, class T>
      constexpr T accumulate(InputIterator first, InputIterator last, T init); // (1) C++20
    
      template <class InputIterator, class T, class BinaryOperation>
      T accumulate(InputIterator first, InputIterator last, T init,
                   BinaryOperation binary_op);                                 // (2) C++03
      template <class InputIterator, class T, class BinaryOperation>
      constexpr T accumulate(InputIterator first, InputIterator last, T init,
                             BinaryOperation binary_op);                       // (2) C++20
    }
    

    概要

    accumulate()は、イテレータ範囲[first, last)を集計する関数である。

    初期値(init)に対して、イテレータ範囲[first, last)の各要素iを前から順番に、任意の二項演算関数binary_opinit = f(init, *i)のように適用していき、範囲の全ての要素を集計した結果を戻り値として返す。

    他の言語でこのような処理は、foldL (Haskell)、reduce (Common Lisp, Ruby)、aggregate (C#)などと呼ばれている。

    • (1) : 二項演算をデフォルトでoperator+とする。それによって、このオーバーロードは、範囲の合計値を求める処理となる
    • (2) : 任意の二項演算関数を受け取って集計処理を行う

    要件

    • C++03まで : binary_opは副作用を起こしてはならない
    • C++11から : binary_opは、イテレータ範囲[first, last]の要素変更およびイテレータの無効化をしてはならない

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

    効果

    • (1) : binary_opoperator+として (2) の効果を適用する
    • (2) :
      • C++03 : acc = init[first, last)の各イテレータをiとし、acc = binary_op(acc, *i)を範囲の全要素に対して適用し、その結果となるaccを返す
      • C++20 : acc = init[first, last)の各イテレータをiとし、acc = binary_op(std::move(acc), *i)を範囲の全要素に対して適用し、その結果となるaccを返す

    戻り値

    集計結果の値

    計算量

    イテレータ範囲[first, last)の要素数に対して線形時間

    備考

    • この関数は並列アルゴリズムに対応していない。計算順序を規程せず、並列アルゴリズムに対応したバージョンとしてstd::reduce()関数が定義されている

    基本的な使い方

    #include <iostream>
    #include <vector>
    #include <string>
    #include <numeric>
    
    int main()
    {
      const std::vector<int> v = {1, 2, 3, 4, 5};
      const std::vector<std::string> v2 = {"aaa", "bbb", "ccc"};
    
      // (1) : 合計値を求める
      int sum = std::accumulate(v.begin(), v.end(), 0);
      std::cout << "sum : " << sum << std::endl;
    
      // (1) : 合計値をlong long型として求める
      // accumulateの第3引数がlong long型のゼロを表す0LLになっていることに注意
      // accumulateの戻り値型は、第3引数の型となるため、変数sum_llの型はlong long
      auto sum_ll = std::accumulate(v.begin(), v.end(), 0LL);
      std::cout << "sum_ll : " << sum_ll << std::endl;
    
      // (1) : 文字列のリストを連結する
      std::string concatenate = std::accumulate(v2.begin(), v2.end(), std::string());
      std::cout << "concat : " << concatenate << std::endl;
    
      // (2) : 任意の二項演算を行う
      // ここでは、初期値を1として、全ての要素を掛け合わせている
      int product = std::accumulate(v.begin(), v.end(), 1, [](int acc, int i) {
        return acc * i;
      });
      std::cout << "product : " << product << std::endl;
    }
    

    出力

    sum : 15
    sum_ll : 15
    concat : aaabbbccc
    product : 120
    

    クラスの一部のメンバ変数を集計する

    #include <iostream>
    #include <numeric>
    #include <vector>
    #include <string>
    
    struct X {
      int value;
      std::string name;
    };
    
    int main() {
      std::vector<X> v = {
        {1, "AAA"},
        {2, "BBB"},
        {3, "CCC"}
      };
    
      int sum = std::accumulate(v.begin(), v.end(), 0, [](int acc, const X& x) {
        return acc + x.value;
      });
    
      std::cout << sum << std::endl;
    }
    

    出力

    6
    

    実装例

    // (1)
    template <class InputIterator, class T>
    T accumulate(InputIterator first, InputIterator last, T init) {
      while (first != last)
        init = init + *first++;
      return init;
    }
    
    // (2)
    template <class InputIterator, class T, class BinaryOperation>
    T accumulate(InputIterator first, InputIterator last, T init,
                 BinaryOperation binary_op) {
      while (first != last)
        init = binary_op(std::move(init), *first++);
      return init;
    }
    

    関連項目

    参照