Double Dispatch und template class



  • Hallo Leute!
    Folgende situation ist mir letzte Woche begegnet:
    Gegeben seien Klassen die als Parameter des Funktionstemplates Eval übergeben werden können; Nun versuche ich diese Funktion(en) in einen laufzeit-polymorphen Kontext zu bringen:

    template<class T, class U>
    Result<T,U> Eval(T,U);
    
    struct iModel
    {
     virtual void DoSth()=0;
     virtual iModel* Eval(iModel*)=0;
    }
    
    /*...*/
    Vector<shared_ptr<iModel>> Models;
    /*...*/
    
    template<class T> struct Model : public iModel
    { 
      T M; 
      virtual void DoSth(){ M.DoSth(); }
      template<class U> iModel* Eval( U RHS){ return new Model<Result<T,U>>(Eval(M,RHS)); }
      virtual iModel* Eval(iModel*){
       return /*Dispatch an Eval-Template*/
      }
    };
    

    Wenn die iModel derivate bekannt wären liese sich der klassische Visitor Pattern anwenden.
    Im Notfall kann man ein Variadic Template nehmen um alle Typen zu registrieren und damit einen Visitor( oder iModel) rekursiv basteln.
    Aber ich frage mich, kann man das nicht eleganter lößen?

    Gruß



  • Sieht jetzt schon over-designed aus. Was willst du erreichen?



  • Ich bin Visitoren grundsätzlich kritisch gegenüber gestellt, das geht meiner Erfahrung nach nur mit starren Hierarchien gut (dann ist eine Liste mit den variadischen Templates geeignet). Und dann gibt es Wege, den double dispatch durch einen single dispatch zu ersetzen, was etwas unschön in der Implementierung wird, sich aber aufgrund der Geschwindigkeit lohnt.



  • @Ad aCta:

    class shape1;
    class shape2;
    struct iShape
    {
     virtual double intersect(iShape * s)=0;
     virtual double intersect(shape1 s1)=0;
     virtual double intersect(shape2 s2)=0;
    };
    
    struct shape1/* zB. kreis*/ : public shape
    {
     virtual double intersect(shape * s){ return c->intersect(*this); }
     virtual double intersect(shape1 s1){;}
     virtual double intersect(shape2 s2){;}
    };
    
    struct shape2/*zB. rechteck*/ : public shape
    {
     virtual double intersect(shape * s){ return c->intersect(*this); }
     virtual double intersect(shape1 s1){;}
     virtual double intersect(shape2 s2){;}
    };
    
    double intersector(shape*s1,shape*s2){ returns1->intersect(s2); }
    

    in meinem problem sind nun aber shape1,shape2 templates und stellen Mathematische Objekte dar, welche von einer anderen Lib stammen.

    @oopattern:
    Die variadic template variante würde leider andere probleme mit sich bringen, da man die Typen erstmal regestrieren muss;
    Im idealfall sollte der benutzer der lib sich um das regestrieren nicht kümmern müßen, da die ermitllung der zu regestrierenden Typen zwar möglich ist, aber sehr aufwendig ist.
    Die potentiellen Typen haben viele templates und man müßte alle möglichen parameter erstmal ermitteln; zwar kann man auch dies automatisieren würde aber zu meheren
    varadic-template-(index/type)-listen führen die sehr groß sind und damit die Kompilierungszeit um mehere Minuten erhöhen würde.
    Der Benutzer müßte, wärend er programmiert alle verwendeten Typen sich merken und durch ein template jagen um alle Ergebnisstypen aller möglichen Typpaarungen und Operationen zu ermitteln und der Paarungen der Ergebnisse mit den restlichen Typen usw...
    Dies ist glücklicherweise möglich da es sich um eine endliche Menge von Typen und Operationen handelt und rekursionen leicht erkannt werden können.



  • Manchmal lohnen sich auch etwas unkonventionelle Ansätze. Du könntest dir beispielsweise das mal anschauen.



  • @Unkonventioneller:
    schöner Dispatcher, leider müßen auch damit alle typen registriert werden.

    In meinem Fall liegt ja ein:

    template<class T, class U> Result<T,U> Eval(T,U);
    // und damit müßte ich für jeden typ:
    dispatch.bind( Type<Model<T>>(), Type<Model<U>>() , &Eval<T,U> );
    

    nun habe ich folgende ideen/fragen :

    1. läßt es sich das für Klassentemplates erweitern?

    2. kann man das dynamischer gestallten? :

    struct ModelManager
    {
     dispatcher D;
    
     Vector<shared_ptr<iModel>> Models;
    
     template<class T>
     void push_back(T M) {
      Models.push_back( shared_ptr<Model<T>>(new Model<T>(M) ));
      D.bindAllTypeCombinations( Type<Model<T>>() ); // sprich für alle registrierten typen U rufe D.bind( Type<Model<T>>(), Type<Model<U>>() , &Eval<T,U> ); auf
     }
    }
    


  • Zuerst mal, wenn dich die Syntax stört, kannst du den Aufruf vereinfachen:

    template <typename T, typename U, typename Fn>
    void bind(DoubleDispatcher<...>& disp)
    {
        disp.bind(Type<T>(), Type<U>(), &Eval<T, U>);
    }
    
    // angewandt:
    bindEval<A, B>(disp);
    

    Jetzt musst du "nur" noch bindEval für alle Kombinationen von A, B aufrufen. Da du hier die statische Typinformation beider Komponenten brauchst, musst du wahrscheinlich mit Template-Metaprogrammierung (Variadic Templates und Typlisten) arbeiten. Sollte nicht allzu schwierig sein, sowas hinzubekommen:

    Typelist<Circle, Rectangle, Triangle>::bindAll(disp);
    

    Der DoubleDispatcher erlaubt zwar auch andere Designs, für Klassen die nicht in einer Vererbungshierarchie stehen. Aber schlussendlich musst du zu irgendeinem Zeitpunkt die Funktion binden können, die zwei konkrete abgeleitete Objekte entgegen nimmt, also musst du gleichzeitig beide Typen kennen.



  • Unkonventioneller schrieb:

    Aber schlussendlich musst du zu irgendeinem Zeitpunkt die Funktion binden können, die zwei konkrete abgeleitete Objekte entgegen nimmt, also musst du gleichzeitig beide Typen kennen.

    Das ist im grunde das problem das ich habe.
    Eine lösung wäre die man definiert im vorfeld eine template-liste was wie zuvor von mir als problematisch beschrieben worden ist.

    Der von dir beschribene bindall funktion ist konzeptionell anderst als das woran ich gedacht habe...

    Meine idee war, da der dispatcher vermutlich eine Map die mit type_index, wird das man daraus irgendwie die bereits eingespeisten Typen rauszieht und mit dem neuen Typ neue funktionen bind'ed. Leider befürchte ich das dies unmöglich ist da die keys gehasht werden müßen und typeid ja sowieso nur in die eine richtung funktioniert...

    Also konkretisiere ich meine Frage nochmal um:

    struct iModel
    {};
    
    template<class T> struct Model : public iModel
    {};
    
    template<class T,class U> void Eval(Model<T>,Model<U>){;}
    
    void Evaluator(iModel* lhs, iModel* rhs)
    {}
    

    kann die Klassenhierarchie und Evaluator derart ergänzt werden, sodass Evaluator direkt oder indirekt die Eval-funktion aufruft?



  • Vielleicht eine allgemeine Frage: Du willst ja die Typregistrierung automatisieren. Das setzt aber voraus, dass Eval<T, U> generisch funktioniert. Musst du hier nicht verschiedene Implementierungen je nach Shape-Kombination bereitstellen? Also manuell verschiedene Fälle abdecken?

    Weil wenn du das tust, kannst du ja auch gerade die zwei Typen beim Dispatcher registrieren. Und sonst würde ich echt eine Typliste nehmen, ist wohl die effizienteste (da 100% zur Kompilierzeit) und am besten erweiterbare Methode.

    Dass Evaluator "von sich aus" die richtige Eval-Funktion aufruft, geht wegen fehlender statischer Typinformation nicht, zumindest nicht ohne Type Erasure. Du müsstest einen gemeinsamen Typ für die verschiedenen Eval-Funktionen finden, diesen aufrufen und dann hinter den Kulission den Aufruf an Eval<T, U> weiterleiten. Aber das ist genau das, was der DoubleDispatcher für dich tut.



  • Unkonventioneller schrieb:

    Vielleicht eine allgemeine Frage: Du willst ja die Typregistrierung automatisieren. Das setzt aber voraus, dass Eval<T, U> generisch funktioniert. Musst du hier nicht verschiedene Implementierungen je nach Shape-Kombination bereitstellen? Also manuell verschiedene Fälle abdecken?

    Ne manuell muss ich nichts machen, das regelt TMP. Ein sehr vereinfachtes beispiel:

    template<size_t i> struct Num{}
    constexpr size_t calc(size_t i, size_t j){ return i*j%101;} // belibige funktion aber bekannt
    template<size_t i, size_t j> auto Eval( Num<i>, Num<j> ){ return Num<calc(i,j)>(); }
    


  • Unkonventioneller schrieb:

    Dass Evaluator "von sich aus" die richtige Eval-Funktion aufruft, geht wegen fehlender statischer Typinformation nicht, zumindest nicht ohne Type Erasure.

    Über double dispach bekomme ich immerhin 1-2 Typangaben, deswegen hoffe ich das man irgendwie noch den zweiten typ herausfinden könnte ohne den ersten zu "vergessen"...
    hier nochmal der beispielcode von vorhin:

    struct iModel
    {
     virtual double dispatch(iShape * s)=0;
    };
    
    template<class T>
    struct Model: public iModel
    {
     typedef Model<T> myType;
     virtual double dispatch(iModel * rhs){ 
      //hier habe ich die Typinfo(myType) von m1 aber wie erhalte ich die typinfo von rhs(m2) 
      //ohne den zugriff auf m1::myType zu verlieren?
     }
    
    };
     .....
    m1->dispatch(m2);
    

    Unkonventioneller schrieb:

    Du müsstest einen gemeinsamen Typ für die verschiedenen Eval-Funktionen finden, diesen aufrufen und dann hinter den Kulission den Aufruf an Eval<T, U> weiterleite

    Gut, lass uns das mal bauen:

    struct Evaluator
    {
    private:
    
    struct iEval
    {
     virtual void Eval(iModel*,iModel*)=0;
    };
    
    template<class T,class U> struct Eval
    {
     virtual void Eval(iModel* lhs, iModel* rhs){ Eval<T,U>( *dynamic_cast<T*>(lhs), *dynamic_cast<U*>(rhs) ); }
    };
    
    iEval* myEval;
    public:
     template<class T, class U>
     void CreateEval(T,U){ myEval = new Eval<T,U>(); }
    };
    

    Nun müßte Model<T>::dispatch( iModel* RHS) irgendwie den CreateEval ordnungsgemäß aufzurufen, aber dazu braucht es noch die TypeInfo von RHS.
    Man müßte es irgendwie schaffen den CreateEval in mehere einzelne schritte aufzuspallten zb in template<class T> BindArg1(T) und template<class U> BindArg2(U), dann könte man nämlich:

    struct iModel
    {
     virtual double dispatch(iShape * s)=0;
     virtual double dispatch(Evaluator E)=0;
    };
    
    template<class T>
    struct Model: public iModel
    {
     typedef Model<T> myType;
    virtual double dispatch(iModel * rhs){ 
      Evaluator E;
      E.bindArg1(myType());
      rhs->dispatch(E);
     }
    virtual double dispatch(Evaluator E){
     E.bindArg2(myType());
     E.Eval();
    }
    
    };
    

    Das wäre eigentlich perfekt wenn man auf die idee käme, wie man die Evaluator::BindArg funktionen basteln könnte; dann bräuchte man weder vordefinierten typlisten noch eine Map zum speichern aller funktionen und typzuordnungen...



  • Das, was du willst - statische Typinformationen über polymorphe Interfaces zu übertragen - ist prinzipbedingt nicht möglich. Man bräuchte dazu virtuelle Funktionstemplates, was technisch nicht realisierbar ist.

    Kleine Überlegung: Damit du statische Typinformation zweier Typen gleichzeitig nutzen kannst, muss diese zur Kompilierzeit zur Verfügung stehen. Wenn sie das aber täte, könntest du die Entscheidung nicht mehr zur Laufzeit treffen - also könnte der Benutzer nicht von iModel erben und die Klasse ohne irgendwo zu registrieren mit den anderen Models kombinieren.


Log in to reply