Expression Template

式テンプレートについて(動機)


式テンプレート
式の情報を持たせたテンプレート(explassion template:略してET)のことです. 必要になるまで計算を保留させることや, 不要なコンストラクタを生成させないようすることができます.
ここでは式テンプレート入門ではなく, 至門(そんな言葉があるのか知らない. 門に入るにはそこにたどり着かねば...)って感じで書いてみます. タイムカプセル暗号の実装の一部を見て 「何やろうとしてるのか分かる」までいけたらなと思います.
上記ソースの先頭のコメントを読むだけで分かる人は以下を読むのは時間の無駄です(^^;
動機
ごく普通のベクトルクラス(et1.h)から始めます.
class Vect {
public:
    enum {
        N = 4
    };
    int& operator[](int i) { return p_[i]; }
    int operator[](int i) const { return p_[i]; }

    static void add(const Vect& rhs, const Vect& lhs, Vect& dest)
    {
        for (int i = 0; i < N; i++) {
            dest.p_[i] = rhs.p_[i] + lhs.p_[i];
        }
    }

    /* dest = rhs + lhs */
    static void add(const Vect& rhs, Vect& dest)
    {
        for (int i = 0; i < N; i++) {
            dest.p_[i] += rhs.p_[i];
        }
    }

    /* dest += rhs */
    Vect& operator+=(const Vect& rhs)
    {
        add(rhs, *this);
        return *this;
    }

    friend Vect operator+(const Vect& lhs, const Vect& rhs)
    {
        Vect tmp;
        add(lhs, rhs, tmp);
        return tmp;
    }

    Vect& operator=(const Vect& rhs)
    {
        std::copy(rhs.p_, rhs.p_ + N, p_);
        return *this;
    }
private:
    int p_[N];
};

このクラスについて

#define DEBUG

#ifdef DEBUG
const bool debug = true;
#else
const bool debug = false;
#endif

#include "et1.h" /* 普通の足し算 */

using namespace std;

int main()
{
    Vect w;
    {
        Vect x, y, z;
        for (int i = 0; i < Vect::N; i++) {
            x[i] = i;
            y[i] = Vect::N - i;
            z[i] = i * 2;
        }
        if (debug) puts("--- here ---");
        w = x + y + z;
    }
    cout << "w=" << w << endl;
    return 0;
}

と使うと(et.cpp)

...(snip)
--- here ---
cstr
cstr
copy
w={4,6,8,10}

と表示されます. w を求めるときに二度 operator+() を呼び出します. その実装の中で Vect tmp; という一時変数を確保して計算しているので, コンストラクタが二回呼ばれて最後の等号でコピーが行われるわけです. 全然問題ないです.

だがしかし,

    w = x;
    w += y;
    w += z;

と書けば一時変数は不要なのです. 今の場合は N が小さいのでたいした問題ではありませんが, もっと大きくてコンストラクタの生成コストやデータのコピーのが大きいときは無視できません. 常に後者のように記述すればよいですが, やはり一行で書きたい, けどコピーは嫌, という要望を満たすためにどうするか. 次のように考えてみましょう.

型情報を返す
w = x + y; について operator+(x, y) の中では計算せずに, 型情報のみを返し, 代入演算子のところで計算するようにします. 戻り値の型は引数が Vect と Vect なので VaddV としましょう. Vect 同士の足し算の結果が Vect とは違う型であるというのは, 初めての方にはかなり奇妙に見えるかもしれません. でも, これでうまくいくのです.

Vect から operator+() を削除し, 代入演算子を追加します. VaddV は型情報のみを持つとしても引数の情報は必要なので, それは参照で持ちます. コードを次のように書き換えます.

class VaddV;

class Vect {
    /* snip */
    Vect& operator=(const VaddV& rhs);
};

class VaddV {
    const Vect& lhs_;
    const Vect& rhs_;
public:
    VaddV(const Vect& lhs, const Vect& rhs)
        : lhs_(lhs)
        , rhs_(rhs)
    {
    }
    void eval(Vect& dest) const
    {
        Vect::add(lhs_, rhs_, dest);
    }
};

VaddV operator+(const Vect& lhs, const Vect& rhs)
{
    return VaddV(lhs, rhs);
}

Vect& Vect::operator=(const VaddV_addV& rhs)
{
    rhs.eval(*this); /* ここで*thisの値を計算する */
    return *this;
}

operator+() 自体は VaddV を生成するだけで何もせず, Vect 側の代入演算子の中で値を計算しています. 演算子の呼び出しと実際の演算が分離されたことに注意してください. w = x + y; における DEBUG 時のメッセージを見ると, 普通の Vect の実装で必要だったコンストラクタやコピーが無くなったのが分かります.

VaddVの生成は必要だがNが大きいときはこれは無視できる.
型情報を増やす
上記変更で w = x + y; はうまく行きましたが, w = x + y + z; はコンパイルエラーになります. これは operator+(x, y) と z の加算, つまり VaddV と Vect の加算が定義されていないので当然です. 更に追加してみましょう. その返り値を VaddV_addV とします. Vect の代入演算子も追加する必要があります(et2.h).
class VaddV;
class VaddV_addV;

class Vect {
    /* snip */
    Vect& operator=(const VaddV& rhs);
    Vect& operator=(const VaddV_addV& rhs);
};

class VaddV_addV {
    const VaddV& lhs_;
    const Vect& rhs_;
public:
    VaddV_addV(const VaddV& lhs, const Vect& rhs)
        : lhs_(lhs)
        , rhs_(rhs)
    {
    }
    void eval(Vect& dest) const
    {
        lhs_.eval(dest);
        Vect::add(rhs_, dest);
    }
};

VaddV_addV operator+(const VaddV& lhs, const Vect& rhs)
{
    return VaddV_addV(lhs, rhs);
}

Vect& Vect::operator=(const VaddV_addV& rhs)
{
    rhs.eval(*this);
    return *this;
}

この修正により, 余計なコンストラクタやコピーをせずに w = x + y + z; も計算できるようになりました. しかし今度は, w = x + y + z + w; だとエラーです.
さて, VaddV_addV_addV を作りますか?

これはあまりに馬鹿らしい. 要は, なんらかの型 E に対して

    E_addV operator+(E, Vect)

という形のものを作ることができればよいのですが, さて.


御意見は光成滋生<herumi@nifty.com>までお願いします