Expression Template

C++

operator+ - * / のような演算子の一般的な実装では一時オブジェクトのコストが発生します。

Vector operator+(const Vector& l, const Vector& r)
{
    const std::size_t n = l.size();
    Vector tmp(l);
    for (std::size_t i = 0; i < n; ++i)
        tmp[i] += r[i];
    return tmp;
}


そのため、以下のような式を書いた場合

Vector x, y, z, t;
t = x + y + z;

x + y + z
では 2 つの一時オブジェクトが生成されてしまうのです。


以下のように書けば一時オブジェクトは生成されませんが

const std::size_t n = x.size();
for (std::size_t i = 0; i < n; ++i)
    t[i] = x[i] + y[i] + z[i];

これを、 t = x + y + z といった自然な構文のまま一時オブジェクトを
生成させないようにするために Expression Template という手法を使います。


Expression Template は、式の構造をテンプレートで保存しておくことで
必要になったときに必要な分だけ計算することができます。
(上の例では即計算しようとするから一時オブジェクトが必要になる)



そのために必要なものは、 + - * / のような演算を行うための小さなクラスです。

template <class L, class R>
class Plus {
    const L& l_; // 左辺値
    const R& r_; // 右辺値
public:
    Plus(const L& l, const R& r)
        : l_(l), r_(r) {}

    float operator[](std::size_t i) const
    {
        return l_[i] + r_[i];
    }
};

operator + では、 Vector ではなく、この Plus クラスのオブジェクトを返すようにします。

template <class L, class R>
inline Plus<L, R> operator+(const L& l, const R& r)
{
    return Plus<L, R>(l, r);
}

そのため、x + y + z の時点では計算は行われなくなり、
以下の Vector::operator= が呼ばれたときに初めて x + y + z を評価するようにします。

class Vector {
public:
    ...

    template <class E>
    Vector& operator=(const E& r)
    {
        const std::size_t n = this->size();
        for (std::size_t i = 0; i < n; ++i)
            (*this)[i] = r[i];
        return *this;
    }

    ...
};

operator= には、 x + y + z の式の構造が渡されるので以下のように評価されます。

for (std::size_t i = 0; i < n; ++i)
    t[i] = Plus<Plus<Vector, Vector>, Vector>(Plus<Vector, Vector>(x, y), z)[i];

Plus::operator[] によって、さらに以下のように評価され

for (std::size_t i = 0; i < n; ++i)
    t[i] = Plus<Vector, Vector>(x, y)[i] + z[i];

最終的には以下のように評価されます。

for (std::size_t i = 0; i < n; ++i)
    t[i] = x[i] + y[i] + z[i];


これで、以下の式は自然な構文を保ったまま一時オブジェクトのコストをなくすことができました。

t = x + y + z;


Expression Template はこのように、一時オブジェクトのコストをなくし、計算を遅延評価するために使用されます。



ちなみに、演算用のクラスは以下のように書くことで、より簡潔に書けます。

template <class L, class Op, class R>
class Expression {
    const L& l_;
    const R& r_;
public:
    Expression(const L& l, const R& r)
        : l_(l), r_(r) {}

    float operator[](std::size_t i) const
    {
        return Op::Apply(l_[i], r_[i]);
    }
};

struct Plus {
    static float Apply(float l, float r)
    {
        return l + r;
    }
};

template <class L, class R>
inline Expression<L, Plus, R> operator+(const L& lhs, const R& rhs)
{
    return Expression<L, Plus, R>(lhs, rhs);
}


【参考書籍】
C++ Templates: The Complete Guide

C++ Template Metaprogramming: Concepts, Tools, And Techniques From Boost And Beyond


【参考サイト】
Cry's Diary - 日本で一番分かりやすく書いたつもりのExpression Templateの説明

本の虫 - Expression Template