Previous Entry Add to Memories Share
Двойная диспетчеризация (C++)
[info]topright wrote in [info]code_review
Логарифмический двойной диспетчер. См. http://en.wikipedia.org/wiki/Multiple_dispatch и http://research.att.com/~bs/multimethods.pdf (пока не попало в стандарт C++). Реализация основана на идее из книги Александреску "Modern C++ Design", глава 11.6. Для хранения/поиска вызовов используется std::map. Из недостатков: диспетчер неправильно работает с механизмом наследования. Александреску загадочно намекает, что решение существует, но не сообщает его.


#ifndef MULTIDISPATCHER2_H_INCLUDED
#define MULTIDISPATCHER2_H_INCLUDED

#include <map>
#include <typeinfo>

/**
    @param ReturnType - type of the return value of handler functions
    @param T1, T2 - base types for dispatching types
    @param default_callback_func - default handler if there is no dispatch for such types
*/
template<
    typename ReturnType,
    typename T1,
    typename T2,
    ReturnType(*default_callback_func)(T1&, T2&)
    >
class Dispatcher2
{
private:

    // Map key

    struct TypeInfo
    {
        const std::type_info& ti1;
        const std::type_info& ti2;

        TypeInfo(const std::type_info& _ti1, const std::type_info& _ti2):
            ti1(_ti1), ti2(_ti2)
        {
        }

        bool operator == (const TypeInfo& typeinfo) const
        {
            return (ti1==typeinfo.ti1 && ti2==typeinfo.ti2);
        }

    };

    struct TypeInfoComp : public std::binary_function<const TypeInfo&, const TypeInfo&, bool>
    {
        bool operator () (const TypeInfo& t1, const TypeInfo& t2) const
        {
            return t1.ti1.before(t2.ti1) || (!(t2.ti1.before(t1.ti1)) && t2.ti2.before(t1.ti2));
        }
    };

    typedef TypeInfo KeyType;

    // Map value

    typedef ReturnType(*CallbackType)(T1&, T2&);

    // Map itself

    typedef std::map<KeyType, CallbackType, TypeInfoComp> MapType;
    MapType callbacks;

public:

    Dispatcher2()
    {
    }

    /**
        add dispatch callback
        @param CT1, CT2 - concrete types (dispatching pair)
    */
    template<typename CT1, typename CT2, ReturnType(*callback)(CT1&, CT2&)>
    void add()
    {
        const KeyType key(typeid(CT1), typeid(CT2));

        struct Local
        {
            static ReturnType trampoline(T1& t1, T2& t2)
            {
                return callback(
                    dynamic_cast<CT1&>(t1),
                    dynamic_cast<CT2&>(t2)
                );
            }
        };

        callbacks[key] = &Local::trampoline;
    }

    void clear()
    {
        callbacks.clear();
    }

    ReturnType run(T1 &t1, T2 &t2)
    {
        try
        {
            // check if dispatcher callback is registered
            const KeyType key(typeid(t1), typeid(t2));

            typename MapType::iterator i = callbacks.find(key);
            if (i != callbacks.end())
            {
                return (*i).second(t1,t2);
            }
        }
        catch (std::exception& e)
        {
        }

        return default_callback_func(t1, t2);
    }

    ReturnType run(T1 *t1, T2 *t2)
    {
        return run(*t1, *t2);
    }

};

#endif // MULTIDISPATCHER2_H_INCLUDED
_Winnie C++ Colorizer




Usage:

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

        struct Rock : Thing {};
        struct Paper : Thing {};
        struct Scissors : Thing {};

        bool Thing_Thing(Thing&, Thing&) { cout << " (T:T) "; return false; }
        bool Paper_Rock(Paper&, Rock&) { cout << " (P:R) "; return true; }
        bool Rock_Scissors(Rock&, Scissors&) { cout << " (R:S) "; return true; }
        bool Sciccors_Paper(Scissors&, Paper&) { cout << " (S:P) "; return true; }

        int main(int, char **)
        {
          Dispatcher2<bool, Thing, Thing, Thing_Thing> compare;

          compare.add<Paper, Rock, Paper_Rock>();
          compare.add<Rock, Scissors, Rock_Scissors>();
          compare.add<Scissors, Paper, Sciccors_Paper>();

          Thing* paper = new Paper();
          Thing* rock = new Rock();

          std::cout << std::boolalpha;
          std::cout << "Paper : Rock " << compare.run(paper, rock) << std::endl;
          std::cout << "Rock : Paper " << compare.run(rock, paper) << std::endl;
_Winnie C++ Colorizer


Есть и такая реализация: http://blog.emptycrate.com/node/288. Её основной минус? В operator() в цикле используются виртуальные вызовы, dynamic_cast и (sic!) для перехода к следующей итерации бросаются исключения. :) Всё это медленно по отдельности, а вместе - совсем не санки. Зато плюс: благодаря dynamic_cast начинает работать механизм наследования.
Tags:

Код на emptycrate тоже не работает. Ищет первый попавшийся обработчик, а надо наилучший. А наилучшего, кстати, может и не быть. Представьте себе, что у вас есть функции для (T, T), (T, R), (S, T), и все, а пришло (S, R). Все три функции подходят по сигнатуре, но первая хуже двух других, из этих двух ни одна не лучше другой, а (S,R) лучше их обеих, но ее нет. Та реализация никак не пытается это учесть, поэтому работающий диспетчер надо искать в другом месте.

Насколько я понял, Вы предлагаете ввести понятие расстояния между наборами (кортежами, tuple) типов и выбирать обработчик наиболее близкого ("наилучшего") кортежа. Как Вы предлагаете вычислять расстояние - в пространстве наследования? По-моему, неявные замены кортежей чреваты неопределенным поведением.

В моей реализации шаблон Dispatcher2 ищет тот и только тот обработчик, который соответствует запрошенному кортежу типов. Если не найден подходящий кортеж, вызывается default callback (см. 4-й параметр шаблона Dispatcher2).

Классы частично упорядочены по наследованию (А больше Б, если А прямо или косвенно выведен из Б). Кортежи классов тоже частично упорядочены (кортеж А больше или равен Б, если все элементы А больше или равны Б). Из всех подходящих функций выбирается наибольшая; если такой нет, то это ошибка. (Можно реализовать альтернативную стратегию: если наибольшей нет, выбирается произвольная такая, что большей, чем она, нет; в примере выше — любая из (T,R), (S,T)). Расстояние в явном виде вводить не нужно.

В качестве примера можно рассмотреть пересечение геометрических фигур: Rectangle>Polygon>Shape, Circle>Curve>Shape. Имеют смысл все функции вида Intersect(X,Y), но Intersect(Rectangle,Rectangle), скажем, значительно эффективнее, чем Intersect(Shape,Shape). Поэтому стоит выбрать самую специализированную функцию.

Никакого другого способа, подходящего под характеристику «правильно работает с наследованием», я вообразить не могу.

Как это все реализовать за логарифмическое время — вопрос отдельный.

Примерно аналогичная ситуация имеется при выборе функции из набора перегруженных функций. Там отношение порядка другое, но функция выбирается по такому же принципу (наилучшее совпадение по всем параметрам).

Например, нет набора (T, S), а есть (BaseOfT, S) и (T, BaseOfS). Какой выбрать? Коллизия. Тем более, если диспетчер симметричный ((T, S) == (S, T)).

Ну так я о чем толкую все это время?

О том, чтобы разруливать коллизии так или иначе. В приведенном Вами примере с фигурами (симметричный диспетчер) коллизии не решить.

Ну конечно, не решить, о том и речь. Коллизии нужно пытаться решать, когда они решаются, а когда не решаются — сообщать об ошибке (а не надеяться на то, что они решатся сями). Построить же систему, в которой коллизий нет, невозможно.

В моей реализации нет коллизий. :)
Если у Вас есть готовое решение, чтоб работало наследование, поделитесь ссылкой или кодом.
У меня есть идеи, как это сделать и как это сделать эффективно, интересно посмотреть, что из этого получится.

Но она же и не работает с наследованием.

Нет, готового решения нет, надо сидеть писать.

topright; прикольно...

стану твоим другом - [info]topright

You are viewing the community [info]code_review