Cry’s Diary

2004-06-05 CRTP(Curiously Reccursive Template Pattern)の使われ方

CRTPについてちまちま書いていたのをまとめてみました.

CRTP(Curiously Reccursive/Reccuring Template Pattern)とは以下のように基底クラステンプレート引数として自分自身を代入するテクニックのことを指します.

template<class Derived>
class Base{/*.....*/};

class C : public Base<C>{/*.....*/};

よく見かけるパターンなので,これがどういう使われ方をしているかを適当にまとめてみました.

仮想関数を用いずにコードの再利用を行う

あるクラスの機能の一部を変えてコードの再利用を行う場合,変えたい機能を提供するメンバ関数を仮想関数にしてそれを派生クラスでオーバーライドするのが通常の方法ですが,CRTPを使えば仮想関数を用いずに行うことができます.

自分で何か良さそうな例を書こうと思ったのですが,あんまり適切な例が思い浮かばないので,このCRTPの使い方の例を載せているページとしてOKA Toshiyuki氏のページをリンクしておきます.

http://www.fides.dti.ne.jp/~oka-t/cpplab-selfref-template.html

http://www.fides.dti.ne.jp/~oka-t/cpplab-selfref-template-2.html

このCRTPの使い方を変形したものとして以下のCRTPの利用法が挙げられると思います.

Template Methodパターンによる実装の半自動化を行う

加算を定義したクラスがあるとします.

class C{
public:
  C operator+(C const &rhs) const
  {
    // 実装
  }

  C &operator+=(C const &rhs)
  {
    // 実装
    return *this;
  }
};

『Effective C++』でのScott Meyersの名言「intのように振舞え」,あるいは『Exceptional C++』(第何項か番号は忘れましたが,ちゃっちいcomplexクラスの実装を引き合いに出して「このクラスの誤りをできる限り挙げよ」とかいう問題で,最初の回答が「std::complexがあるのに再発明するなヴォケ!」というあの項)に書いてあるように,通常,operator+は以下のようにほぼお決まりのパターンでoperator+=に委譲する形で書くのが原則になっています.

C C::operator+(C const &rhs) const
{
  C tmp(*this); // まぁ,コピーコンストラクタはあるとしましょう
  tmp += rhs;   // ここでoperator+=に委譲している
  return tmp;
}

こういう決まりきった形式をとるものは,できることなら自動化してしまおうと考えるのが再利用の基本ってものです.そこで,次のようなクラスを作ります.

template<class T>
struct addable{
  T operator+(T const &rhs) const
  {
    T tmp(static_cast<T const &>(*this));
    tmp += rhs;
    return tmp;
  }
};

このクラスを利用すると先ほどのclass Cは以下のように書けます.

class C 
  : public addable<C>
{
public:
  C &operator+=(C const &rhs){
    // 実装
    return *this;
  }
};

先ほどのCの定義との違いがお分かりいただけるでしょうか?たった1行addableから継承するというコードを書くだけで,Cにoperator+を定義することができてしまっています.もちろんCには最低限のコードとしてoperator+=は書かなければいけません.しかし,それさえ書いてしまえば後はaddableが自動でCに他の機能を提供してくれるわけです.別の言い方をすれば,addableはoperator+=の定義を色々取り替えられるようにしておいて,それに依存するoperator+の定義を自動で行ってしまうクラスとも言えます.これはまさに『デザインパターン』でいうところのTemplate Methodパターンと言えませんか?(なので,タイトルは上のようにしてみましたがどうでしょか?)特に,addableの部分がライブラリとして提供されていれば,class Cを定義しようとするユーザはこのようなライブラリを利用して低コストでCの実装を行うことができます.

boostでこのようなCRTPの使い方をしている例を挙げてみるとboost::operators(上の例はここから取らせてもらいました), boost::iterator_facade, boost::iterator_adaptorなどが挙げられると思います.こういうiteratorや演算子といった軽量になる傾向のあるオブジェクト関数に対しては(仮想関数を持ち出すことはほぼ論外になりますので),このようなCRTPの利用は非常に有効であると思われます.また,上記のライブラリとは若干文脈が違うとは思いますがboost::spiritのgrammarなどもこれに属するCRTPの使い方をしていると思われます.

静的多相性を構成する?

私がCRTPを最初に知ったころは「CRTPを使って静的多相性が出来る!」と思っていたのですが,どうもこの「CRTPによって静的多相性が実現できる」という言い方はおかしいのではないか,と思い直してきました.以下に例を示します.

#include <iostream>

template<class T>
class base{
public:
  void method(){ as_derived().method(); }

protected:
  T &as_derived(){ return static_cast<T&>(*this); }
  T const &as_derived() const{ return static_cast<T const &>(*this); }
};

class A : public base<A>{
public:
  void method(){ std::cout << "This is A::method()" << std::endl; }
};

class B : public base<B>{
public:
  void method(){ std::cout << "This is B::method()" << std::endl; }
};

template<class T>
void some_process(base<T> &r)
{
  r.method();
}

int main(int argc, char *argv[])
{
  A a;
  some_process(a);

  B b;
  some_process(b);

  return 0;
}

上のコードでは,確かにsome_processにおいてrが多相的に扱えています.が,rが多相的に扱えていることとCRTPによってbaseとA, Bに階層が組まれていることは本質的にまったく関係ないと思われるのです.some_processにおいてrが多相的に扱えると言いたいだけなら,以下のコードで良いはずなのです.

class A{
public:
  void method(){ std::cout << "This is A::method()" << std::endl; }
};

class B{
public:
  void method(){ std::cout << "This is B::method()" << std::endl; }
}

template<class T>
void some_process(T &r)
{
  r.method();
}

some_processにおいてrが多相的に扱えるための最低限の要求は「"r.method()"というコードがコンパイルを通る(そしてsome_processが期待する意味を持つ)」であって,そこにCRTPが存在する理由は何一つないと思われるのです.

以上から,CRTPの効果という点でより厳密に述べるなら以下のほうが適切ではないか,と思うのですが・・・

汎用関数においてコンセプトの不整合に対するFirewallを構成する

template<class T>
void some_process(base<T> &r);

template<class T>
void some_process(T &r);

上の2つの最大の違いは,後者があらゆる型Tに対してsome_processが定義されているように見えるのに対して,前者はbase<T>(の派生型)に対してのみ定義されていることです.

後者の場合,想定していない型,たとえばintに対してもsome_processが定義されているように見えます.が,実際には後者に対してintで実体化するとintのオブジェクトにはr.method()なんていうコードは定義されていませんので,その部分でエラーを引き起こすことになります.上のようにsome_processが単純な場合ならまだしも,some_processが複雑な場合,コンパイル時に大量の意味不明のエラーが吐き出されエラーの特定が非常に困難になります.皆さんもSTLやboostを使っていてしばしばこのような経験をしていることと思います.

一方,前者はbase<T>(の派生型)に対してのみ定義されています.base<T>(の派生型)には,some_processにおいて要求されるmethodメンバ関数が必ず定義されているという制約があります.これはsome_processにおける,引数に対するコンセプトの要求が関数の宣言に明示されていると考えることができると思います.これによってsome_processが要求するコンセプトに合わない型,たとえばintなどに対してsome_processを適用しようとするとただ一言「intに対してsome_processは定義されていない」というエラー(もしくはsome_processに対するintのoverloadが解決しないという類のエラー)が吐き出されるだけで済みます.

このようなCRTPの作用も非常に重要であると思うのですが,実際にはコードの再利用のためのCRTPの利用に付随してくるだけの効果であることが多く,目立たないものだとは思います.

また,同等の機能を提供する他の機構,たとえばboost::concept_checkなどとの比較も色々考えて見ましたが,あまりまとまった答えは出せませんでした.この部分についてある程度考えがまとまったらまたこのことについて書くかもしれません.

名前空間に対して汎用関数名前の導入を制限する

上とかなり重複するCRTPの効果になると思いますが,タイトルのような効果も期待できます.上に書いたsome_processの二つの宣言

template<class T>
void some_process(base<T> &r);

template<class T>
void some_process(T &r);

では,前者の方がsome_processという関数名の導入を制限した形になっています.これによって,前者ではsome_processという関数名に対する他のoverloadが可能になってきます.

template<class T>
void some_process(hoge<T> &r);

template<class T>
void some_process(huga<T> &r);

もちろんこれらはsome_processの後者の宣言に対する特殊化でも可能ですが,後者の宣言では最も汎用な宣言を一度書いたが最後,あとはすべて特殊化で書かなければならず,結局同じことをしなければならなくなります.

このことはExpression Templateの実装においては特に重要です.というのも,演算子に対して最も汎用的な形を宣言するわけにはいかないからです.

template<class LHS, class RHS>
plus<LHS, RHS> operator+(LHS const &lhs, RHS const &rhs);
// plusは演算子が返す式オブジェクトです

このような演算子のoverloadは他のクラスに対しても定義されるでしょうから,この宣言を特定のクラスのために書くことは許されません.(id:Cryolite:20040507#p1で「議論は後回しにします」と書いておいて結局書いてなかった問題とはこのことです.)なので,ETの実装では演算子のoverloadを制限することがほぼ必須になります.

template<class LHS, class RHS>
plus<LHS, RHS> operator+(base<LHS> const &lhs, base<RHS> const &rhs);

boost::numeric::ublass, boost::lambda, boost::spiritなどExpression Templateを用いたboostのライブラリではCRTPによるこの効果を享受しています.が,実際にはこの効果もコードの再利用のためにCRTPを使った結果の副産物としての意味合いが強いかも知れません.(そもそもこの効果だけが必要ならCRTPでなくても実現可能です.)

ototoiototoi 2004/06/07 14:40 はじめまして。目から鱗が落ちました。

CryoliteCryolite 2004/06/07 16:23 あ,はじめまして.実は上の日記は最近churosさんやototoiさんがCRTPについて触れているのに刺激を受けて,以前からちょこちょこっと考えていたことをまとめて書いたものです.なので,本来ならきちんとtrackbackを送っておくべきでした.申し訳ないです.

ototoiototoi 2004/06/07 19:17 やはりそうでしたか。僕の語彙が足りないところ、よく説明されていで、感動しました。CRTPは静的多相性において必要条件ではないけれど十分条件なんだと思います。

Connection: close