C++のtransform_inclusive_scan()関数とは?使い方と実装例を解説

このチュートリアルでは、C++のtransform_inclusive_scan()関数の動作を理解するためのサンプルプログラムを紹介します。

transform_inclusive_scan()関数とは

transform_inclusive_scan()は、C++17で<numeric>ヘッダーに追加された数値計算アルゴリズムの一つです。範囲内の各要素に単項演算を適用したうえで、二項演算を使って先頭から現在位置までの累積計算(包含スキャン)を行い、その結果を順に出力先へ書き込みます。

本記事では、この関数と同等の処理を自前で実装したコードを見ながら、内部の動きを詳しく解説します。

サンプルコード

#include <iostream>
#include <vector>
using namespace std;
namespace point_input_iterator {
    template <class InputItrator, class OutputItrator, class BinaryOperation, class UnaryOperation>
    OutputItrator transform_inclusive_scan(InputItrator first, 
       InputItrator last,
       OutputItrator d_first,
       BinaryOperation binary_op,
       UnaryOperation unary_op){
       
       *d_first = unary_op(*first);
       first++;
       d_first++;
       for (auto it = first; it != last; it++) {
          //calculating the prefix sum
          *d_first = binary_op(unary_op(*it), *(d_first - 1));
          d_first++;
       }
       return d_first;
    }
}
int main(){
    //inputting elements using vector
    vector<int> InputVector{ 11, 22, 33, 44, 55, 66, 77, 88 };
    vector<int> OutputVector(8);
    point_input_iterator::transform_inclusive_scan(InputVector.begin(), InputVector.end(), OutputVector.begin(), [](auto xx, auto yy) {
       return xx + yy;
    },
    [](auto xx) {
       return xx * xx;
    });
    for (auto item : OutputVector) {
       //printing the output item
       cout << item << " ";
    }
    cout << std::endl;
    return 0;
}

コードの解説

このプログラムでは、transform_inclusive_scan()と同等の処理をテンプレート関数として自作しています。処理の流れは以下のとおりです。

• まず、先頭要素に単項演算(ラムダ式で定義した「2乗する」処理)を適用し、その結果を出力先の最初の要素に格納します。
• 続いて、2番目以降の要素に対して、「現在の要素に単項演算を適用した値」と「直前の累積結果」を二項演算(ラムダ式で定義した「加算」処理)で結合し、順次出力先に書き込みます。
• main()関数では、vectorに格納した整数 {11, 22, 33, 44, 55, 66, 77, 88} を入力とし、単項演算として「x × x」、二項演算として「x + y」を渡して呼び出しています。

実行結果

121 605 1694 3630 6655 11011 16940 24684

計算の流れ

出力値がどのように求められているかを順に追ってみましょう。

• 1番目: 11 × 11 = 121
• 2番目: 121 + (22 × 22) = 121 + 484 = 605
• 3番目: 605 + (33 × 33) = 605 + 1089 = 1694
• 4番目: 1694 + (44 × 44) = 1694 + 1936 = 3630
• 5番目: 3630 + (55 × 55) = 3630 + 3025 = 6655
• 6番目: 6655 + (66 × 66) = 6655 + 4356 = 11011
• 7番目: 11011 + (77 × 77) = 11011 + 5929 = 16940
• 8番目: 16940 + (88 × 88) = 16940 + 7744 = 24684

このように、transform_inclusive_scan()は「各要素を変換しながら、それまでの累積結果に含めて計算していく」処理を行う関数です。累積和の計算などに応用でき、C++17以降では標準の<numeric>ヘッダーから直接利用することも可能です。