• Class / Function / Type

      std::
    • Header file

      <>
    • Other / All

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

    履歴 編集

    function template
    <numeric>

    std::exclusive_scan

    namespace std {
      template <class InputIterator, class OutputIterator, class T>
      OutputIterator
        exclusive_scan(InputIterator first,
                       InputIterator last,
                       OutputIterator result,
                       T init);                    // (1) C++17
      template <class InputIterator, class OutputIterator, class T>
      constexpr OutputIterator
        exclusive_scan(InputIterator first,
                       InputIterator last,
                       OutputIterator result,
                       T init);                    // (1) C++20
    
      template <class InputIterator, class OutputIterator, class T, class BinaryOperation>
      OutputIterator
        exclusive_scan(InputIterator first,
                       InputIterator last,
                       OutputIterator result,
                       T init,
                       BinaryOperation binary_op); // (2) C++17
      template <class InputIterator, class OutputIterator, class T, class BinaryOperation>
      constexpr OutputIterator
        exclusive_scan(InputIterator first,
                       InputIterator last,
                       OutputIterator result,
                       T init,
                       BinaryOperation binary_op); // (2) C++20
    
      template <class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class T>
      ForwardIterator2
        exclusive_scan(ExecutionPolicy&& exec,
                       ForwardIterator1 first,
                       ForwardIterator1 last,
                       ForwardIterator2 result,
                       T init);                    // (3) C++17
    
      template <class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class T,
                class BinaryOperation>
      ForwardIterator2
        exclusive_scan(ExecutionPolicy&& exec,
                       ForwardIterator1 first,
                       ForwardIterator1 last,
                       ForwardIterator2 result,
                       T init,
                       BinaryOperation binary_op); // (4) C++17
    }
    

    概要

    イテレータ範囲[first, last)の部分和を計算する。この関数は、i番目の部分和を求める際にi番目の要素を含めず範囲[0, i)までの部分和を計算する。

    exclusive_scan()の引数として初期値0、およびシーケンス{1, 2, 3}が与えられた場合、以下のような結果が行われる:

    {
      0, // 0
      1, // 0 + 1
      3  // 0 + 1 + 2
    }
    

    • (1) : 初期値をinit、二項演算としてoperator+を使用して部分和を求める
    • (2) : 初期値をinit、二項演算として任意の関数オブジェクトbinary_opを使用して部分和を求める
    • (3) : (1)の並列アルゴリズム版。第1パラメータとして実行ポリシーをとる
    • (4) : (2)の並列アルゴリズム版。第1パラメータとして実行ポリシーをとる

    要件

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

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

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

    効果

    • (1) : 以下と等価

      return exclusive_scan(first, last, result, init, plus<>());
      

    • (2), (4) : 範囲[0, last - first)の各値をKとして、出力先のイテレータresult + Kに、{init, *first, *(first + 1), *(first + 2), ..., *(last - 1)}K番目までの要素の合計値を順不同に代入する

    • (3) : 以下と等価

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

    戻り値

    結果範囲の末尾イテレータを返す

    計算量

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

    備考

    • (1), (2) : resultfirstと同値になるだろう
    • (2), (4) : 関数オブジェクトbinary_opに数学的な結合性がない場合、この関数は非決定的な動作になる可能性がある

    #include <iostream>
    #include <vector>
    #include <numeric>
    
    int main()
    {
      // (1)
      {
        std::vector<int> v = {1, 2, 3, 4, 5};
        std::vector<int> result(v.size());
    
        // result[0] = 0
        // result[1] = 0 + 1
        // result[2] = 0 + 1 + 2
        // result[3] = 0 + 1 + 2 + 3
        // result[4] = 0 + 1 + 2 + 3 + 4
        std::exclusive_scan(v.begin(), v.end(), result.begin(), 0);
    
        for (int x : result) {
          std::cout << x << ' ';
        }
        std::cout << std::endl;
      }
    
      // (2)
      {
        std::vector<int> v = {1, 2, 3, 4, 5};
        std::vector<int> result(v.size());
    
        // result[0] = 0
        // result[1] = max(0, 1)
        // result[2] = max(max(0, 1), 2)
        // result[3] = max(max(max(0, 1), 2), 3)
        // result[4] = max(max(max(max(0, 1), 2), 3), 4)
        std::exclusive_scan(v.begin(), v.end(), result.begin(), 0,
                            [](int a, int b) { return std::max(a, b); });
    
        for (int x : result) {
          std::cout << x << ' ';
        }
        std::cout << std::endl;
      }
    }
    

    出力

    0 1 3 6 10 
    0 1 2 3 4 
    

    バージョン

    言語

    • C++17

    処理系

    関連項目

    参照