マルチメソッド4 対数時間編

basic_dispatcher

flat_mapを使う

RTTI(実行時型情報)と、type_index(typeinfoを比較できるようにラップした型)の2つがあることにより、全ての型に対して(もちろん動的な型も含みます)、順序関係を持つことが出来ます。つまり、全ての型をキーとして二分木探索ができるということです。
type_indexをキーとし、mapped_typeをディスパッチしたい関数へのポインタにすることで、対数時間で関数をディスパッチすることが出来ます。std::mapを使いたいところですが、std::mapは時間的にも空間的にもオーバーヘッドが大きいです。ソート済みvectorを使うことで効率よく二分探索を行うことが出来ます。mapよりもソート済みvectorのほうが効率が良くなるかどうかは、挿入頻度よりアクセス頻度が多い場合有効になります。今回は最初だけ要素の挿入を行い、後は関数を呼び出すだけですので該当します。
ソート済みvectorとしてmapと同じインターフェイスになっているコンテナがboostにあります。boost::container::flat_mapです。これを使っていきます。このディスパッチャを基本として、今後のディスパッチャを考えていくのでbasic_dispatcherと呼ぶことにします。

template
<
    class BaseLhs,
    class BaseRhs = BaseLhs,
    class Result = void,
    class CallBack = Result(*)(BaseLhs&, BaseRhs&)
>
class basic_dispatcher
{
#ifdef _MSC_VER
    using map_type = std::map<std::pair<std::type_index, std::type_index>, CallBack>;
#else
    using map_type = boost::container::flat_map<std::type_index, std::type_index>, CallBack>;
#endif
    using key_type = typename map_type::key_type;
    using mapped_type = typename map_type::mapped_type;
    map_type callback_;
...

Visual C++ 12.0ではなぜかflat_mapを使うとコンパイルエラーが出るのでVC++だけはstd::mapを使用しています。(gcc, clangでは無問題)
std::pairは要素の型が比較可能なとき、比較することが出来ます。よってキーの型のstd::pair<std::type_index, std::type_index>は比較可能な型となっています。pairのfirstはディスパッチする関数の左辺の型で、secondはディスパッチする右辺の型となります。*1
登録するadd関数と呼び出しをするgo関数は以下のようになります。

...
public:
    template <class SomeLhs, class SomeRhs>
    void add(CallBack func)
    {
        key_type const key(typeid(SomeLhs), typeid(SomeRhs));
        callback_[key] = func;
    }

    Result go(BaseLhs& lhs, BaseRhs& rhs)
    {
        auto i = callback_.find(key_type(typeid(lhs), typeid(rhs)));
        if (i == callback_.end())
        {
            throw std::runtime_error("関数が見つかりません");
        }
        return (i->second)(lhs, rhs);
    }
};

add関数を呼び出す時はテンプレート引数に具体的なディスパッチしたい関数の引数の型2つを渡します。static_dispatcherの時はディスパッチしたい関数のシグネチャは具体的な型で異なっていましたが、mapped_typeは1通りなので、全てのディスパッチ関数が同じシグネチャでなければなりません。*2よってbasic_dispatcherに渡す関数ポインタは、引数が基底クラスの参照を取る関数でなければなりません。具体的な(動的な)型は、関数内部で適切にdynamic_castをすることで得ます。

basic_dispatcherを使用するコードです。

struct shape
{
    virtual ~shape() {}
};

struct rectangle : shape {};
struct ellipse : shape {};
struct polygon : shape {};
struct round_rectangle : rectangle {};

void is_hit_rectangle_and_rectangle_(shape&, shape&)
{
    std::cout << "rectangle and rectangle" << std::endl;
}

void is_hit_rectangle_and_ellipse_(shape&, shape&)
{
    std::cout << "rectangle and ellipse" << std::endl;
}

void is_hit_rectangle_and_polygon_(shape&, shape&)
{
    std::cout << "rectangle and polygon" << std::endl;
}

void is_hit_rectangle_and_round_rectangle_(shape&, shape&)
{
    std::cout << "rectangle and round_rect" << std::endl;
}

// 中略...

void is_hit_round_rectangle_and_rectangle_(shape&, shape&)
{
    std::cout << "round_rect and rectangle" << std::endl;
}

void is_hit_round_rectangle_and_ellipse_(shape&, shape&)
{
    std::cout << "round_rect and ellipse" << std::endl;
}

void is_hit_round_rectangle_and_polygon_(shape&, shape&)
{
    std::cout << "round_rect and polygon" << std::endl;
}

void is_hit_round_rectangle_and_round_rectangle_(shape&, shape&)
{
    std::cout << "round_rect and round_rect" << std::endl;
}

void basic_dispatch_test(std::vector<shape*>& v)
{
    using dispatcher = basic_dispatcher<shape>;
    dispatcher disp;
    disp.add<rectangle, rectangle>(is_hit_rectangle_and_rectangle_);
    disp.add<rectangle, ellipse>(is_hit_rectangle_and_ellipse_);
    disp.add<rectangle, polygon>(is_hit_rectangle_and_polygon_);
    disp.add<rectangle, round_rectangle>(is_hit_rectangle_and_round_rectangle_);
    disp.add<ellipse, rectangle>(is_hit_ellipse_and_rectangle_);
    disp.add<ellipse, ellipse>(is_hit_ellipse_and_ellipse_);
    disp.add<ellipse, polygon>(is_hit_ellipse_and_polygon_);
    disp.add<ellipse, round_rectangle>(is_hit_ellipse_and_round_rectangle_);
    disp.add<polygon, rectangle>(is_hit_polygon_and_rectangle_);
    disp.add<polygon, ellipse>(is_hit_polygon_and_ellipse_);
    disp.add<polygon, polygon>(is_hit_polygon_and_polygon_);
    disp.add<polygon, round_rectangle>(is_hit_polygon_and_round_rectangle_);
    disp.add<round_rectangle, rectangle>(is_hit_round_rectangle_and_rectangle_);
    disp.add<round_rectangle, ellipse>(is_hit_round_rectangle_and_ellipse_);
    disp.add<round_rectangle, polygon>(is_hit_round_rectangle_and_polygon_);
    disp.add<round_rectangle, round_rectangle>(is_hit_round_rectangle_and_round_rectangle_);
    for (auto& i : v)
    {
        for (auto& j : v)
        {
            disp.go(*i, *j);
        }
    }
}

実行結果

round_rect and round_rect
round_rect and rectangle
round_rect and ellipse
round_rect and polygon
rectangle and round_rect
rectangle and rectangle
rectangle and ellipse
rectangle and polygon
ellipse and round_rect
ellipse and rectangle
ellipse and ellipse
ellipse and polygon
polygon and round_rect
polygon and rectangle
polygon and ellipse
polygon and polygon
-------------------------
-------------------------
続行するには何かキーを押してください . . .

add関数の呼び出し量が恐ろしいことになっていますが、これはまだbasic_dispatcherに対称性を実装していないからで、後に改善されます。
今回たまたまadd関数を1箇所で呼び出していますが、実際にはbasic_dispatcherをシングルトンなどにして、ディスパッチ関数を定義したところで適宜登録することができます。つまり、static_dispatcherではすべての階層が1箇所で見えていなければならなかった依存性が解消されています。
この時点でもstatic_dispatcherと比べて優れている点が3つあります。

階層のクラスが増えても速い
階層のクラスに対する依存度が低い
static_dispatcherよりもコンパイル時間、実行時間が短く、コードサイズも小さい

ですが、デメリットもたくさんあります。

対称性がない
ファンクタに対応していない
関数の引数の型が基底クラスに固定されてしまう

あともう一つ大きな問題があります。basic_dispatcherはリスコフの置換原則を守っていません。
例を出すと通常のshape&を引数に取る関数はshapeから派生したクラスrectangle型のオブジェクトを受け取ることができ、仮想関数をオーバーライドしない限りshapeと同じ振る舞いをします。sttatic_dispatcherはそのとおりに振る舞います。例え(rectangle&, rectangle&)を引数に取る関数を登録しなくても(shape&, rectangle&)を取る関数があればこちらにディスパッチされ、処理されます。しかしbasic_dispatcherでは厳密に登録した時のキーのtype_index型のペアと一致する関数しか呼び出してくれません。Andrei氏はModern C++ Design執筆時点でこれの有効な解決方法を見つけていません。現時点では全ての方の組み合わせを注意深く登録していかなければなりません。
最後に、3つの問題のうち、「 * 関数の引数の型が基底クラスに固定されてしまう」という問題を解決して終わりにします。残り2つは、次回の対数時間改良編でやりたいと思います。

function_dispatcher

トランポリン関数

やることは単純で、ディスパッチャー内部で具体的な型へキャストする処理をやれば良いです。実際の処理の前にちょっとした処理をしてメインの関数を呼び出す関数をトランポリン関数またはサンクと言うそうです。また、テンプレートは非型テンプレート引数として関数ポインタを渡すことができます。basic_dispatcherをバックエンドとして、関数ポインタをディスパッチするfunction_dispatcherを定義してみます。関数ポインタに絞っているのでファンクタは対象外です。ファンクタを考慮したディスパッチャーは次回やります。
function_dispatcherのソースコードです。

template
<
    class BaseLhs,
    class BaseRhs = BaseLhs,
    class Result = void
>
class function_dispatcher
{
    basic_dispatcher<BaseLhs, BaseRhs, Result> backend_;
public:
    template <class SomeLhs, class SomeRhs, Result (*CallBack)(SomeLhs&, SomeRhs&)>
    void add()
    {
        struct local
        {
            static Result trampoline(BaseLhs& lhs, BaseRhs& rhs)
            {
                return CallBack(dynamic_cast<SomeLhs&>(lhs), dynamic_cast<SomeRhs&>(rhs));
            }
        };
        backend_.add<SomeLhs, SomeRhs>(&local::trampoline);
    }

    Result go(BaseLhs& lhs, BaseRhs& rhs)
    {
        return backend_.go(lhs, rhs);
    }
};

内部に実装としてbasic_dispatcherを持っています。add関数内で、引数を基底クラスから正しい型へキャストし、関数へ転送するトランポリン関数が定義されています。関数内にstaticオブジェクトとして作ってしまうと、同一のオブジェクトとなってしまうため、addの度に異なるトランポリン関数が作成されるよう、ローカルクラスを使用しています。CallBackの呼び出しは間接参照のように見えますが、トランポリン関数のアドレスはコンパイル時に解決されるので、コンパイラが最適化を行う設定になっていれば恐らくインライン展開されますので、トランポリン関数によるオーバーヘッドありません。
相変わらず対称性が未対応のせいでadd関数の量が多いですが、登録・呼び出しは以下のようになりました。

void function_dispatcher_test(std::vector<shape*>& v)
{
    using dispatcher = function_dispatcher<shape>;
    dispatcher disp;
    disp.add<rectangle, rectangle, is_hit_rectangle_and_rectangle>();
    disp.add<rectangle, ellipse, is_hit_rectangle_and_ellipse>();
    disp.add<rectangle, polygon, is_hit_rectangle_and_polygon>();
    disp.add<rectangle, round_rectangle, is_hit_rectangle_and_round_rectangle>();
    disp.add<ellipse, rectangle, is_hit_ellipse_and_rectangle>();
    disp.add<ellipse, ellipse, is_hit_ellipse_and_ellipse>();
    disp.add<ellipse, polygon, is_hit_ellipse_and_polygon>();
    disp.add<ellipse, round_rectangle, is_hit_ellipse_and_round_rectangle>();
    disp.add<polygon, rectangle, is_hit_polygon_and_rectangle>();
    disp.add<polygon, ellipse, is_hit_polygon_and_ellipse>();
    disp.add<polygon, polygon, is_hit_polygon_and_polygon>();
    disp.add<polygon, round_rectangle, is_hit_polygon_and_round_rectangle>();
    disp.add<round_rectangle, rectangle, is_hit_round_rectangle_and_rectangle>();
    disp.add<round_rectangle, ellipse, is_hit_round_rectangle_and_ellipse>();
    disp.add<round_rectangle, polygon, is_hit_round_rectangle_and_polygon>();
    disp.add<round_rectangle, round_rectangle, is_hit_round_rectangle_and_round_rectangle>();
    for (auto& i : v)
    {
        for (auto& j : v)
        {
            disp.go(*i, *j);
        }
    }
}

int main()
{
    std::vector<shape*> v = {new round_rectangle(), new rectangle(), new ellipse(), new polygon()};

    function_dispatcher_test(v);
    std::cout << "-------------------------" << std::endl;

    for (auto& it : v)
    {
        delete it;
    }
}

実行結果

round_rect and round_rect
round_rect and rectangle
round_rect and ellipse
round_rect and polygon
rectangle and round_rect
rectangle and rectangle
rectangle and ellipse
rectangle and polygon
ellipse and round_rect
ellipse and rectangle
ellipse and ellipse
ellipse and polygon
polygon and round_rect
polygon and rectangle
polygon and ellipse
polygon and polygon
-------------------------
続行するには何かキーを押してください . . .

static_dispatcherと同様に、具体的な型のシグネチャの関数が使えるようになりました。関数の引数ではなく、非型テンプレート引数として渡しています。あとはbasic_dispatcherと同じように使用できます。これでbasic_dispatcherに渡す関数の引数の方の問題が解決しました。残2つの問題(対称性と、ファンクタへの対応)は次回やりたいと思います。

*1:ちなみにstd::pair<std::type_index, std::type_index>に対するstd::hashの特殊化を定義すれば、unordered_mapでもキーとして使用することができ、O(1)の探索が可能になると思われます。しかし書籍でハッシュマップについては言及されていませんので、今回は特に触れずに進めていきます

*2:ここでいう関数のシグネチャは、戻り値の型と引数の型と引数の数と考えて下さい

C++と色々

主にC++やプログラムに関する記事を投稿します。

マルチメソッド4 対数時間編

basic_dispatcher

flat_mapを使う

function_dispatcher

トランポリン関数