マルチメソッド1 自作編の続きです。
ここからはModern C++Design に載っている方法を1つずつ試したいと思います。
その際、Boost.Mplを使用しています。生ポインタ使っています。スマートポインタを使うべきですが、本のサンプルをなるべくそのまま使いたいので見逃して下さい…
実装についてはこちらを参考にしました。
マルチメソッドとは
今回は、引数の動的な型に依存して異なる関数にディスパッチするメカニズム、と定義します。動的な関数のディスパッチと言えば仮想関数ですが、仮想関数は呼び出したオブジェクトに依存しています。引数ではありません。 ちなみに静的なディスパッチはオーバーロードとテンプレート関数です。今回は引数が2つの関数に話を限定します。
マルチメソッドが有効な場面
ゲームを作っていて、異なる図形の交差判定を行う場合があります。図形の組み合わせによって最適なアルゴリズムは異なります。四角形同士、四角形と多角形、四角形と楕円、楕円同士、楕円と多角形、多角形同士などです。これらの図形はshapeという共通の基本クラスから派生しており、これらのコンテナをshape*型で保持しているとします。そうした場合2つのオブジェクトの動的な型に依存した関数のディスパッチが必要になります。
力任せの方法
恐らく最も愚直な方法です。dynamic_castで線形に調べていく方法です。各図形クラスと、最適なアルゴリズムで書かれた衝突判定関数があると仮定します。定義は問題でないので省略します。
#ifndef SHAPE_H #define SHAPE_H struct shape { virtual ~shape(){} }; struct rectangle : shape {}; struct ellipse : shape {}; struct polygon : shape {}; void is_hit_rectangle_and_rectangle(rectangle&, rectangle&); void is_hit_rectangle_and_ellipse(rectangle&, ellipse&); void is_hit_rectangle_and_polygon(rectangle&, polygon&); void is_hit_ellipse_and_polygon(ellipse&, polygon&); void is_hit_ellipse_and_ellipse(ellipse&, ellipse&); void is_hit_polygon_and_polygon(polygon&, polygon&); #endif
そしてディスパッチをする関数です
void double_dispatch(shape& lhs, shape& rhs) { if(rectangle* p1 = dynamic_cast<rectangle*>(&lhs)) { if(rectangle* p2 = dynamic_cast<rectangle*>(&rhs)) is_hit_rectangle_and_rectangle(*p1, *p2); else if(ellipse* p2 = dynamic_cast<ellipse*>(&rhs)) is_hit_rectangle_and_ellipse(*p1, *p2); else if(polygon* p2 = dynamic_cast<polygon*>(&rhs)) is_hit_rectangle_and_polygon(*p1, *p2); else std::runtime_error("未定義の型"); } else if(ellipse* p1 = dynamic_cast<ellipse*>(&lhs)) { if(rectangle* p2 = dynamic_cast<rectangle*>(&rhs)) is_hit_rectangle_and_ellipse(*p2, *p1); else if(ellipse* p2 = dynamic_cast<ellipse*>(&rhs)) is_hit_ellipse_and_ellipse(*p1, *p2); else if(polygon* p2 = dynamic_cast<polygon*>(&rhs)) is_hit_ellipse_and_polygon(*p1, *p2); else std::runtime_error("未定義の型"); } else if(polygon* p1 = dynamic_cast<polygon*>(&lhs)) { if(rectangle* p2 = dynamic_cast<rectangle*>(&rhs)) is_hit_rectangle_and_polygon(*p2, *p1); else if(ellipse* p2 = dynamic_cast<ellipse*>(&rhs)) is_hit_ellipse_and_polygon(*p2, *p1); else if(polygon* p2 = dynamic_cast<polygon*>(&rhs)) is_hit_polygon_and_polygon(*p1, *p2); else std::runtime_error("未定義の型"); } else { std::runtime_error("未定義の型"); } }
呼び出し側は以下のようになります。
std::vector<shape*> v; v.reserve(3); v.push_back(new rectangle()); v.push_back(new ellipse()); v.push_back(new polygon()); double_dispatch(*v[0], *v[0]); double_dispatch(*v[0], *v[1]); double_dispatch(*v[0], *v[2]); double_dispatch(*v[1], *v[0]); double_dispatch(*v[1], *v[1]); double_dispatch(*v[1], *v[2]); double_dispatch(*v[2], *v[0]); double_dispatch(*v[2], *v[1]); double_dispatch(*v[2], *v[2]); for(auto& it : v) { delete it; } v.clear();
この方法のメリットデメリットは以下になります。
メリット
- クラス数が少なければ高速
デメリット
- コードサイズがクラスが増える度に指数的に増える
- double_dispatchが全てのクラスの実体に依存している
- if文の順番に注意を払わなければならない
最後のデメリットについて。例えばrectangleを継承して新たにround_rectangle型(角を丸く面取りした四角形)を作ったとします。そしてround_rectangleに関するif文を追加したと考えて下さい。全てのround_rectangle型はrectangle型にキャストが成功してしまうので、rectangleのif文より後にround_rectangleのif文を追加してしまうと、決してround_rectangleのif文に処理が来ることがなくなってしまいます。
力任せの方法を少し改良する
前述した問題の解決策は、if文を継承関係順にソートして、最も基本のクラスを最後に来るようにします。しかしたった3つの型のdouble_dispatchでこの面倒くささです。プログラマーが注意して管理して保守するのは大変ですし、バグの温床になりかねません。double_dispatchはクラスの実体だけでなく、継承関係にも依存します。 力任せの方法の少し改良としてif文の列挙を自動化、どんな型でも動くよう汎用化したいと思います。継承順の型のソートや関数の対称性についてはまだ対応していません。 サンプルコードです
template < class Func, class BaseLhs, class TypesLhs, class BaseRhs = BaseLhs, class TypesRhs = TypesLhs, class Result = void > class static_dispatcher { template <class SomeLhs> struct rhs_dispatcher { template <class Head, class Tail> struct dispatcher { static Result dispatch(SomeLhs& lhs, BaseRhs& rhs, Func functor) { if(Head* p2 = dynamic_cast<Head*>(&rhs)) { return functor(lhs, *p2); } return Tail::dispatch(lhs, rhs, functor); } }; struct dispatcher_error { static Result dispatch(SomeLhs& lhs, BaseRhs& rhs, Func functor) { throw std::runtime_error("未定義の型"); } }; typedef typename mpl::reverse_fold<TypesRhs, dispatcher_error, dispatcher<mpl::_2, mpl::_1>>::type type; }; struct lhs_dispatcher { template <class Head, class Tail> struct dispatcher { static Result dispatch(BaseLhs& lhs, BaseRhs& rhs, Func functor) { if(Head* p1 = dynamic_cast<Head*>(&lhs)) { return rhs_dispatcher<Head>::type::dispatch(*p1, rhs, functor); } return Tail::dispatch(lhs, rhs, functor); } }; struct dispatcher_error { static Result dispatch(BaseLhs& lhs, BaseRhs& rhs, Func functor) { throw std::runtime_error("未定義の型"); } }; typedef typename mpl::reverse_fold<TypesLhs, dispatcher_error, dispatcher<mpl::_2, mpl::_1>>::type type; }; public: static Result go(BaseLhs& lhs, BaseRhs& rhs, Func functor) { return lhs_dispatcher::type::dispatch(lhs, rhs, functor); } };
テンプレート引数
Funcはファンクタで、今回の場合は力任せの方法のis_hit_xxx_and_xxx関数と同様のシグネチャを持つoperator()をオーバーロードします。static_dispatcherに対称な引数の対応がないので、Funcは(今回の場合は)void operator()(rectangle&, ellipse&);とvoid operator()(ellipse&, rectangle&);の2つ書かなければいけません。このことについては後述します。BaseLhsは、関数の左辺の基本クラスです。BaseRhsは関数の右辺の基本クラスです。このクラスの型で受け取り、dynamic_castで実際の型にキャストします。TypesLhsはBaseLhsを継承した具体的な型のリストです。難しく考えずに普通のリスト構造の型バージョンだと思って下さい。
TypesRhsも同様に右辺のBaseRhsから派生した具体的な型リストです。
lhs_dispatcher
lhs_dispatcher構造体はdouble_dispatch関数で言う、外側のif文相当の処理をします。HeadはTypesLhsの最初の型で、普通のリストの先頭ノードのようなものと思って下さい。dynamic_castに成功した場合、rhs_dispatcher構造体に転送します。失敗した場合、先頭の型を除いた型リストで再帰呼び出しをします。*1TailはHeadを除いた型リストで、TailのHeadは型リストの2番目の型を表します。このように、TypesLhsの型を1つづずらしながら再帰していきます。mpl::reverse_foldにより、型リストの型を1つずつ減らし、型リストの型がなくなった時、lhs_dispatcher::dispatcher_error::dispatchが呼ばれます。dispatcher_errorのdispatchまで達したということはTypesLhsにキャスト出来る型が存在しなかった、つまりディスパッチ不可能なので例外とします。
rhs_dispatcher
rhs_dispatcherはdouble_dispatch関数で言う内側のif文相当の処理をします。この関数に来たということは関数の左辺は具体的な方にキャストできたということなので、BaseLhs(今回はshape)に戻すようなことをせず、SomeLhsという形でそのままの型で受け取ります。やっていることはlhs_dispatcher構造体とほぼ同じで、左辺が右辺に変わっただけです。キャストに成功した場合、ディスパッチしたい関数の左辺と右辺の動的な型が解決したということなので、functorを呼んで、実際の処理を行います。失敗した場合はlhs_dispatcher関数と同様に型リストを1つずつ減らして再帰呼び出しをします。*2rhs_dispatcher
ファンクタ
Funcに適応したファンクタは今回の場合以下のようになります。*3
class is_hit { public: void operator()(rectangle&, rectangle&); void operator()(rectangle&, ellipse&); void operator()(rectangle&, polygon&); void operator()(ellipse&, rectangle&); void operator()(ellipse&, ellipse&); void operator()(ellipse&, polygon&); void operator()(polygon&, polygon&); void operator()(polygon&, rectangle&); void operator()(polygon&, ellipse&); };
呼び出し側は以下のようになります。
std::vector<shape*> v; v.reserve(3); v.push_back(new rectangle()); v.push_back(new ellipse()); v.push_back(new polygon()); typedef mpl::list<rectangle, ellipse, polygon> TypeList; typedef static_dispatcher<is_hit, shape, TypeList> dispatcher; is_hit is_hit_; dispatcher::go(*v[0], *v[0], is_hit_); dispatcher::go(*v[0], *v[1], is_hit_); dispatcher::go(*v[0], *v[2], is_hit_); dispatcher::go(*v[1], *v[0], is_hit_); dispatcher::go(*v[1], *v[1], is_hit_); dispatcher::go(*v[1], *v[2], is_hit_); dispatcher::go(*v[2], *v[0], is_hit_); dispatcher::go(*v[2], *v[1], is_hit_); dispatcher::go(*v[2], *v[2], is_hit_); for(auto& it : v) { delete it; } v.clear();
double_dispatchと違い、関数オブジェクトを渡す引数が増えています。テンプレート引数のTypesLhsにはmpl::list<rectangle, ellipse, polygon>を渡しています。これが型のリストです。mpl::listでなくてもmpl::vectorでも構いません。力任せの方法でも説明したとおり、より基本クラスが派生クラスを吸収してしまわないように、型リスト(今回はmpl::list)に書く型の順番には気をつける必要が依然あります。これに関しても自動化の方法を考慮していきます。
この少し改良版のメリットとデメリットです。
メリット
- クラス追加が容易(ファンクタにオーバーロード関数を追加するだけ(static_dispatcher自身は具体的な型に依存していない))
- クラス数が少なければ高速
デメリット
- 型リストの組み合わせだけstatic_dispatcherを生成するため、コンパイル時間が増え、実行コードのサイズが大きくなる
- static_dispatcherに対称の対応がないので、ファンクタのオーバーロードで引数が逆の関数も定義する必要がある。
- 型リストの型の順番に気をつけなければならない
長くなったので次に分割したいと思います。次は力任せの方法に引数の対称性と、型リストを継承関係によって自動ソートする機能をつけます。
