[X] Multimethoden

[ness]

-predator- schrieb:

Ich bin jetzt mit der Korrektur soweit fertig, aber mir sind beim nochmaligen Lesen noch ein paar Dinge aufgefallen, die man zuerst klären sollte.

In Abschnitt 3.2, im ersten und zweiten Code:

typename TL::change_to_refernce_type<Bases>::result

Ist das refernce da Absicht, oder hast du dich vertippt und es sollte eigentlich reference heißen?

Ja, das sollte es heißen. Ich scheine das einmal falsch und dann dank autocompletion _im quelltext_ überall so zu haben. Hab das jetzt überall ersetzt und lade den quelltext nochmals hoch.

-predator- schrieb:

Dann wieder im Abschnitt 3.2, im letzten (längeren) Code:

typedef TYPELIST_3(objekt&,objekt&,objekt&) ml_3;
    typedef TYPELIST_5(spacecraft&,space_station&,satellite&) l_types;

Warum verwendest du hier TYPELIST_5? Tippfehler oder versteh ich da gerade etwas nicht?

Das ist etwas sinnlos, da hast du recht. Zumal ich dann scheinbar in einer oberflächlichen korrektur 2 Typen rausgelöscht habe. Es funktioniert (mit 5 Typen) aber, und zwar aus folgendem Grund: der multidispatcher löscht alle mehrfach vorkommenden typen. (Außerdem wechselt er alle Typen zu Referenzen). Ich denke, genau das wollte ich demonstrieren. Jetzt gibt es zwei Möglichkeiten, den Artikel auszubessern, und ich bin mir nicht sicher, welche die richtige ist:

• TYPELIST_5 mit 5 Typen stehenlassen und erklären
• TYPELIST_3 draus machen

Ich tendiere zu letzterem.

/edit: und genau das hab ich jetzt gemacht

-predator- schrieb:

Und im Abschnitt 3.3.2, im letzten Code:

template<class L>
struct at<L, 0>
{
  static T go (modern_ellipse<L>& mell)
  {
    return mell.head;
  }
};

Was ist hier T? Musst du das nicht noch als Template-Parameter angeben? Schau's dir bitte noch mal an, ob ich da nen Denkfehler hab.

Richtig. Das muss natürlich typename L::head heißen.

-predator- schrieb:

So, das war's erst mal von der fachlichen Seite.
Mir sind noch zwei (regelmäßige) Rechtschreibfehler aufgefallen, die dich vielleicht interessieren.
Es heißt "Das spar ich mir" und nicht "Das spahr ich mir", und "length" und nicht "lenght".

Vielen dank. Wann ein stummes 'h' muss und wann nich, damit hab ich so meine Probleme. Das 2. scheint ein konsistenter Tippfehler zu sein.

-predator- schrieb:

//edit: Ach, mir ist doch noch was eingefallen. Es ist noch kein Link zum Quelltext im Artikel, oder?

Der war drin, bevor ich ihn vor der rechtschreibkorrektur mit 0. rausgelöscht habe

[michba]

OK, dann verwende ich jetzt "Double-Dispatching".

@ness: ich ändere dann das refernce im Artikel auch zu reference, oder?

[ness]

ja, danke, hab ich vergessen.

[michba]

Link zum Quelltext

1 Multimethoden

1.1 Was sind Multimethoden?

• Als Multimethoden bezeichnet man die Möglichkeit, in Abhängigkeit vom dynamischen Typ mehrerer Objekte unterschiedliche Funktionen aufzurufen.

Ein Beispiel soll das verdeutlichen:
Angenommen man schreibt einen Ego-Shooter. Wenn der Gegner durchlöchert wird, soll natürlich schön Blut spritzen. Eine Hauswand dagegen sollte sich nur geringfügig beeindruckt zeigen. Nehmen wir weiter an, alle Objekte werden als object& oder object* gespeichert (polymorphe Basisklassen). Irgendwo im Kollisionserkennungsteil ~hab mir mal erlaubt, das einzudeutschen...~ könnte es solchen oder ähnlichen Code geben:

//objects ist ein sortierter Container
//for(alle o1 in objects)
//    for(alle o2 > o1 in objects)
        if(do_overlap(o1, o2))
            //was jetzt?

An dieser Stelle gibt es ein Problem. Der statische Typ der Objekte ist object*, wir interessieren uns aber für den dynamischen Typ, also wall*, enemy*, round*, ... (der Fantasie sind keine Grenzen gesetzt). Und je nach den dynamischen Typen wollen wir den Bildschirm rot färben oder nicht.

1.2 Multimethoden im C++-Sprachumfang

Der C++-Sprachumfang enthält technisch betrachtet nur eine "Vorstufe" der Multimethoden, die so genannten virtuellen Funktionen (die sollte eigentlich jeder kennen, der das hier liest). Mit etwas ('ner ganzen Menge) Arbeit kann man mit virtuellen Funktionen Multimethoden aber simulieren: in einem virtuellen Funktionsaufruf ist der dynamische Typ bekannt, und der kann "weitergereicht" werden. Man braucht also für jedes involvierte Objekt (in unserem Fall 2) einen virtuellen Funktionsaufruf, sowie eine große Menge überladener Funktionen, um die Typen "weiterzureichen". So könnte das im Code aussehen:

class wall;
class enemy;
//...

void do_handle(wall*, wall*);
void do_handle(wall*, enemy*);
void do_handle(enemy*, wall*);
void do_handle(enemy*, enemy*);

class object
{
public:
    virtual void overlap_helper1(object*) = 0;

    virtual void overlap_helper2(wall*) = 0;
    virtual void overlap_helper2(enemy*) = 0;
};

class enemy
    :public object
{
public:
    virtual void overlap_helper1(object* o)
    {
        o -> overlap_helper2(this);
    }

    virtual void overlap_helper2(wall* w)
    {
        do_handle(w, this);    //void do_handle(wall*, enemy*);
    }

    virtual void overlap_helper2(enemy* e)
    {
        do_handle(e, this);    //void do_handle(enemy*, enemy*);
    }
};

class wall
    :public object
{
public:
    virtual void overlap_helper1(object* o)
    {
        o -> overlap_helper2(this);
    }

    virtual void overlap_helper2(wall* w)
    {
        do_handle(w, this);    //void do_handle(wall*, wall*);
    }

    virtual void overlap_helper2(enemy* e)
    {
        do_handle(e, this);    //void do_handle(enemy*, wall*);
    }
};

Wie man sieht ist das eine ganze Menge aufwändiger und vor allem fehleranfälliger Tipparbeit, nicht zu vergessen der Arbeit, die nötig ist, um eine neue Art von Objekten hinzuzufügen.
Um noch mal auf das Ausgangssnippet zurückzukommen: mit dieser Implementierung des Double-Dispatching (so bezeichnet man den Spezialfall des Multi-Dispatching mit 2 Objekten) sieht es so aus:

//objects ist ein sortierter Container
//for(alle o1 in objects)
//    for(alle o2 > o1 in objects)
        if(do_overlap(o1, o2))
            o1 -> overlap_helper1(o2);

1.3 Statische Implementierungen des Double-Dispatching

Hier will ich typische Implementierungen des Double-Dispatching zeigen. Das "Statische" in der Überschrift heißt, dass alles von Hand gecoded wird. Das bringt natürlich sehr viel stupide Arbeit mit sich, aber hier geht es eher darum, Ansätze zu zeigen.

1.3.1 Die "Rohvariante"

Die wohl häufigste Stehgreifimplementierung benutzt dynamic_cast. Dynamic_cast erlaubt sichere Downcasts - entweder das Objekt ist wirklich von dem Typ, zu dem man casten will oder der Cast gibt 0 zurück. Mittels dieses Wissens können wir einen einfachen Double-Dispatcher von Hand schreiben:

void double_dispatch(object* o1, object* o2)
{
    if(wall* w = dynamic_cast<wall*>(o1))
        if(wall* w2 = dynamic_cast<wall*>(o2))
            do_handle(w, w2);
        else if(enemy* e = dynamic_cast<enemy*>(o2))
            do_handle(w,e);
        else
            //ERROR
    else if(enemy* e = dynamic_cast<enemy*>(o1))
        if(wall* w = dynamic_cast<wall*>(o2))
            do_handle(e, w);
        else if(enemy* e2 = dynamic_cast<enemy*>(o2))
            do_handle(e,e2);
        else
            //ERROR
    else
        //ERROR
}

Wenn es m Typen gibt, die o1 sein kann und n Typen, die o2 sein kann, und jeder Typ mit derselben Wahrscheinlichkeit auftritt, werden im Durchschnitt (m + n) / 2 Casts benötigt, um zu einem Ergebnis zu kommen, im Worst-Case sind es m + n Casts. Die Laufzeit ist also linear.
Das Ausgangssnippet spare ich mir hier, ich denke der Aufruf ist klar.

1.3.2 Der logarithmische Double-Dispatcher

Trotz oder gerade aufgrund der Einfachheit der Rohvariante bringt sie eine ganze Menge Nachteile mit sich: auf der einen Seite bedeutet lineare Laufzeit natürlich genau das, und sicher jeder kann sich vorstellen, dass er es nicht soo toll fände, wenn sich die Programmlaufzeit linear zur Anzahl der dispatchten Klassen verhält. Andererseits müssen dem O(n)-Dispatcher bei der Deklaration alle zu dispatchenden Typen übergeben werden, was ihn faktisch von allen Typen abhängen lässt. Und derart weitreichende Abhängigkeiten will man natürlich vermeiden.
Eine Möglichkeit, das Dispatching zur Laufzeit vorzunehmen (und damit die Abhängigkeiten loszuwerden) bietet das typeid-Schlüsselwort; der Rückgabetyp, std::type_info, implementiert den op==. Aber es kommt noch besser: mittels der Memberfunktion type_info::before kann man type_info-Objekte sogar sortieren! Das heißt, dass wir auch das Laufzeitverhalten entscheidend verbessern können, indem wir auf binäre Suche zurückgreifen.
std::type_info ist zwar funktional, aber etwas unhandlich. Deshalb benutzen wir einen Wrapper, der ungefähr so aussieht:

class tinfo
{
private:
    const std::type_info* ti;

public:
    tinfo() : ti(0) {}  // für Container
    tinfo(const std::type_info& t) : ti(&t) {}
    const std::type_info& get() const
    {
      if (!ti)
        throw std::runtime_error("Benutzung eines uninitialisierten tinfo!!!");
      return *ti;
    }

    bool operator==(const tinfo& o) {return get() == o.get();}
    bool operator!=(const tinfo& o) {return !(*this == o);}
};
bool operator<(const tinfo& t1, const tinfo& t2) {return t1.get().before(t2.get());}

Ein Double-Dispatcher lässt sich nun einfach realisieren: er verwaltet intern eine std::map von Paaren von tinfo auf den Typ der im Erfolgsfall aufgerufenen Entität. Ungefähr so:

class double_dispatcher
{
public:
    typedef void (*callback)(object*, object*);
    typedef std::map<std::pair<tinfo, tinfo>, callback> map_t;

private:
    map_t map;

public:
    void go(object* o1, object* o2) const
    {
        map_t::const_iterator i = map.find(std::make_pair (tinfo (typeid(*o1)), tinfo (typeid(*o2))));
        if(i == map.end())
            throw std::runtime_error("Funktion nicht gefunden!!!");
        else
            return (i -> second)(o1, o2);
    }

    template<class L, class R>
    void add(callback c)
    {
        map[std::pair<tinfo,tinfo>(typeid(L), typeid(R))] = c;
    }
};

(Beachten muss man, dass add Basistypen registriert, go aber Zeiger entgegennimmt. Das könnte man auch ändern, finde ich aber am klarsten, zumal der nächste User vielleicht eine Schnittstelle will, die Referenzen nimmt.)
Es ist unschwer zu erkennen, dass die Komplexität gleich der von std::find ist, also O(ld(n)).
Unschön ist, dass jede registrierte Funktion Zeiger auf object (statt die abgeleitete Klasse) annehmen und daher zunächst casten muss. Dies lässt sich aber mittels sogenannter Trampolinfunktionen recht einfach lösen. Außerdem funktioniert der Dispatcher nicht korrekt mit Vererbung, hierfür ist mir allerdings keine Lösung bekannt.

1.3.3 Der O(1)-Double-Dispatcher

Eigentlich kann man sich eine Tabelle vorstellen, bei der sowohl Zeilen als auch Spalten Typen sind, ungefähr so:

|wall enemy round
------|------------------
wall  |  ww   we   wr
enemy |  ew   ee   er
round |  rw   re   rr

Dann ist klar, dass man, wenn man vom Typ auf den Index schließen kann, die richtige Funktion (z.B. er) in konstanter Zeit finden kann. Eine einfache aber fehlerträchtige Methode wäre, die Indexe von Hand zu definieren und jeder Klasse eine virtuelle Funktion get_index zu geben. Ganz ohne Veränderungen an den Klassen kommen wir nicht aus, aber ein wenig komfortabler geht es:

#define ADD_HOOK(theclass)\
static int& get_hook_static()\
{\
    static int i = -1;\
    return i;\
}\
virtual int& get_hook()\
{\
    assert(typeid(*this) == typeid(theclass));\
    return get_hook_static();\
}

Man ruft einfach im öffentlichen Interface der Klasse ADD_HOOK(meine_klasse) auf, und schon werden die benötigten Funktionen hinzugefügt. Der Dispatcher kann dann, wann immer er auf einen neuen Typ stößt, diesem einen Wert zuweisen. Der Dispatcher ist nun schnell definiert:

class dispatcher
{
public:
    typedef void (*callback)(object*, object*);

private:
    std::vector<std::vector<callback> > m;  // vector<vector<...> > ist nicht so optimal!
    unsigned highest;

public:
    dispatcher()
        :highest(0)
    {
    }

    template<class L, class R>
    void add(callback c)
    {
        int& li = L::get_hook_static();
        int& ri = R::get_hook_static();
        if(li == -1)
            li = highest++;
        if(ri == -1)
            ri = highest++;
        if (m.size () <= static_cast<unsigned>(li))
          m.resize (li + 1);
        if (m[li].size () <= static_cast<unsigned>(ri))
          m[li].resize (ri + 1);
        m[li][ri] = c;
    }

    void go(object* l, object* r) const
    {
        int li = l -> get_hook(), ri = r -> get_hook();
        if(li == -1 || ri == -1 || static_cast<unsigned>(li) >= m.size ()
           || static_cast<unsigned>(ri) >= m[li].size () || m[li][ri] == 0)
            // ERROR
        m[li][ri](l, r);
    }
};

Klar ist, dass go in konstanter Zeit einen Fehler meldet oder die richtige Funktion aufruft. Auch klar ist, dass der Dispatcher mit Vererbung nicht richtig funktioniert.

1.4 Multi-Dispatching

Alle 3 oben gezeigten Verfahren lassen sich leicht für mehr als 2 Objekte generalisieren: Für die "Rohvariante" führt man einfach eine weiter Ebene von Tests ein, ungefähr so:

void double_dispatch(object* o1, object* o2, object* o3)
{
    if(wall* w = dynamic_cast<wall*>(o1))
        if(wall* w2 = dynamic_cast<wall*>(o2))
            if(wall* w3 = dynamic_cast<wall*>(o3))
                do_handle(w, w2, w3);
        else if(enemy* e = dynamic_cast<enemy*>(o2))
            // ...
    else if // ...        
}

Für den logarithmischen Double-Dispatcher nimmt man einfach eine map von einem triple von tinfo zu callback (snippet spar ich mir hier, ist ja trivial).
Und den O(1)-Dispatcher kann man generalisieren, indem man ein höherdimensionales array benutzt.

2 Typlisten

2.1 Was sind Typlisten?

So kann eine Definition der Grundbestandteile von Typlisten aussehen:

template<class T, class U>
struct typelist
{
    typedef T head;
    typedef U tail;
};

struct eol
{
}

Die Definition von Typlisten sieht etwas kryptisch aus, aber ihre Verwendung und Manipulation erkläre ich gleich.
An sich sind Typlisten den klassischen Listen sehr ähnlich. typelist ist ein Element der Liste: T ist sein "Wert" und U der "Zeiger" zum nächsten Element. Da es in dieser Situation keine Direkte Entsprechung für Nullzeiger gibt, um das Ende der Liste anzuzeigen, wird per Konvention eol als Listenende festgelegt. Eine einfache List von ganzzahligen vorzeichenlosen Datentypen erhält man z.B. so:

typedef typelist
<
    unsigned char,
    typelist
    <
        unsigned int,
        typelist
        <
            unsigned long,
            eol
        >
    >
> unsigned_integrals;

Das ist natürlich viel zu viel Tipparbeit, deshalb gibt es meist Makros um Typlisten zu erstellen. Die können z.B. so aussehen:

#define TYPELIST_1(t) typelist<t, eol>
#define TYPELIST_2(t1, t2) typelist<t1, TYPELIST_1(t2) >
#define TYPELIST_3(t1, t2, t3) typelist<t1, TYPELIST_2(t2, t3) >
#define TYPELIST_4(t1, t2, t3, t4) typelist<t1, TYPELIST_3(t2, t3, t4) >
//...

Jetzt geht die Definition der obigen Typliste viel leichter von der Hand:

typedef TYPELIST_3(unsigned char, unsigned int, unsigned long) unsigned_integrals

2.2 Wozu kann man Typlisten verwenden?

Typlisten werden benutzt, um zur Kompilierzeit Informationen über eine Liste von Typen zu halten. Das ist nötig, will man die "Rohvariante" des Double-Dispatching mittels Template-Metaprogrammierung automatisieren. Ein generischer Double-Dispatcher der mittels Template-Metaprogrammierung realisiert ist, könnte z.B. so ein Interface anbieten (das hier gezeigte ist natürlich nicht ausgereift):

typedef double_dispatcher
<
    my_executor,
    object*,
    TYPELIST_3(wall*, enemy*, player*)
> my_double_disp;

//Aufruf:
my_double_disp::go(exec, o1, o2);

Wobei my_executor ein Funktor ist, der aufgerufen wird, wenn die Typen herausgefunden wurden, object* ist die Basisklasse und die Typliste sind die konkreten möglichen Typen. Die Definition von my_executor könnte z.B. sein:

struct my_executor
{
    void operator()(wall* w1, wall* w2)
    {
        do_handle(w1, w2);
    }

    void operator()(wall* w , enemy* e)
    {
        do_handle(w,e);
    }

    void operator()(object*, object*)    //alles andere
    {
        //...
    }
};

Ich denke das ist selbsterklärend. Interessant ist die letzte Überladung, die alle unbehandelten Fälle abfängt.

2.3 Manipulation von Typlisten

Manipulation von Typlisten ist sehr einfach, man muss sich nur daran gewöhnen, dass es keine imperativen Konstrukte gibt und normale Schlüsselwörter wie for nicht funktionieren. D.h., "Funktionen" zur "Manipulation" von Typlisten sind Konstrukte der Template-Metaprogrammierung. Um das Listenende zu erkennen, muss man mit (partieller) Spezialisierung arbeiten. So sieht z.B. eine einfache "Funktion" zur Bestimmung der Länge einer Typliste aus:

template<class L>
struct length
{
    static const unsigned result = length<typename L::tail>::result + 1;
};

template<>
struct length<eol>
{
    static const unsigned result = 0;
};

Ein weiteres einfaches Beispiel ist das Anhängen eines Types am Ende:

template<class L, class A>  // A an das Ende von L anhängen
struct add
{
    typedef typelist<typename L::head, typename add<typename L::tail, A>::result> result;
};

template<class A>
struct add<eol, A>
{
    typedef TYPELIST_1(A) result;
};

3 Mein Multi-Dispatcher

3.1 Idee

Wer "Modernes C++ Design" gelesen hat, weiß, dass der Autor in 11.12 sagt, dass die Generalisierung des Double-Dispatchings einfach wäre. Und da ich zu der Zeit, als ich das Buch las (oder gerade weil ich es las) voll im "Template-Meta-Programmier-Fieber" war, stellte diese Ansage natürlich eine interessante Herausforderung für mich dar. Nach kurzer Analyse schien mir die Rohvariante am meisten Template-Spielereien zu erfordern, also nahm ich mir vor, einen generischen Multi-Dispatcher nach Vorbild Alexandrescu's zu schreiben, was mir sogar gelang.

3.2 Benutzung des Multi-Dispatchers

Bevor wir zur Implementierung kommen, ist es wohl ganz nützlich, das öffentliche Interface des Dispatchers vorzustellen. Der für den Nutzer interessante Teil der Deklaration sieht so aus:

template
<
    class Executor,				// Typ des Funktors, der nach erfolgreichem Dispatching aufgerufen werden soll
                  				// sollte operator() für alle Kombinationen von Interesse überladen
    template<class l1,class l2>class Error,	// Typ des Funktors, der nach einem Dispatchingfeher aufgerufen wird
					        // muss operator()(const mer::modern_ellipse<l1>&, const mer::modern_ellipse<l2>&) definieren
						// Das erste Argument enthält bereits ermittelte Typen, das zweite die anderen
						// Wenn der 1. Template-Parameter TYPELIST_1(Loki::EmptyType) ist, schlug bereits die Ermittlung
                                                // des ersten Typs fehl
				 		// Das Argument, dass den Fehler auslöste, ist an Position 1 des 2. Arguments
    class Bases,				// Typliste, die die Basisklassen der zu dispatchenden Objekte hält
    class Types,				// Typliste von Typlisten, die die konkreten Klassen enthalten
                 				// Muss nach Basisklassen sortiert und in der selben Reihenfolge wie Bases sein.
    class Result_type=void			// Rückgabtyp von Executor::operator()
>
class static_dispatcher
{
public:
    static Result_type go
    (
      const modern_ellipse<typename TL::change_to_reference_type<Bases>::result>& me,
      const Executor& exec
    );
}

Sollten die vielen Template-Parameter auch zunächst verwirren, eigentlich sind sie ganz logisch. Auch der erste Parameter von go ist komisch:

const modern_ellipse<typename TL::change_to_reference_type<Bases>::result>& me

Dazu ein wenig Erklärung: Will man Dispatching beliebiger Ordnung implementieren, steigt die Anzahl der Argumente (z.B. für Double-Dispatching 2, für Triple-Dispatching 3). C++ bietet keine typsichere Methode, dies direkt auszudrücken. C hatte etwas vergleichbares, die sogennante Ellipse ("..."; die gibt es zwar auch in C++ noch, aber funktioniert nur mit primitiven Typen). Deshalb habe ich einen typsicheren Ersatz geschrieben (siehe 3.3.2). Für jetzt reicht es zu wissen, dass das Makro MER_NAMED_M_ELLIPSE_FROM_MER_TYPELIST_AND_BOOST_PP_SEQ_OF_ARGUMENTS (ja, ewig langer Name) solche modernen Ellipsen erzeugen kann, und zwar so:

MER_NAMED_M_ELLIPSE_FROM_MER_TYPELIST_AND_BOOST_PP_SEQ_OF_ARGUMENTS(typen, (wert1)(wert2)(wert3)...(wertn), name)
// Erzeugt eine moderne Ellipse genannt NAME mit den Werten wert1 bis wert2.
// Typen enthält die Typen der Werte

// noch ein Bsp.:
MER_NAMED_M_ELLIPSE_FROM_MER_TYPELIST_AND_BOOST_PP_SEQ_OF_ARGUMENTS(TYPELIST_3(int, bool, long), (4)(false)(25896), meine_mel);

Die Syntax der Wertübergabe ist etwas ungewöhnlich, aber die portabelste.
Einen Dispatcher könnte man also so definieren und anwenden:

template<class L_list,class R_list>
struct error
{
	void operator()(const mer::modern_ellipse<L_list>&,const mer::modern_ellipse<R_list>&) const
	{
		cout<<"Unbekanntes Objekt gefunden!!!"<<endl;
	}
};

struct executor
{
	void operator()(const mer::modern_ellipse<TYPELIST_3(space_station&,space_station&,space_station&)>&) const
	{
		cout<<"triple_dispatcher(space_station&, space_station&, space_station&)"<<endl;
	}
	void operator()(const mer::modern_ellipse<TYPELIST_3(space_station&,space_station&,spacecraft&)>&) const
	{
		cout<<"triple_dispatcher(space_station&, space_station&, spacecraft&)"<<endl;
	}
	// viele weiter Überladungen
};

class objekt
{
public:
	virtual string what(){return "objekt";}
};

class space_station
	:public objekt
{
public:
	virtual string what(){return "space_station";}
};

class spacecraft
	:public objekt
{
public:
	virtual string what(){return "spacecraft";}
};

class satellite
	:public objekt
{
public:
	virtual string what(){return "satellite";}
};

class fehler
	:public objekt
{
public:
	virtual string what(){return "ERROR";}
};

int main()
{
	objekt* pss1	= new space_station;
	objekt* pss2	= new space_station;
	objekt* pss3	= new space_station;
	objekt* psc1	= new spacecraft;
	objekt* psc2	= new spacecraft;
	objekt* psc3	= new spacecraft;
	objekt* ps1	= new satellite;
	objekt* ps2	= new satellite;
	objekt* ps3	= new satellite;

	objekt* pf	= new fehler;

	typedef TYPELIST_3(objekt&,objekt&,objekt&) ml_3;
	typedef TYPELIST_3(spacecraft&,space_station&,satellite&) l_types;

	typedef static_dispatcher
	<
		executor,
		error,
		ml_3,
		TYPELIST_3(l_types, l_types, l_types),
		void
	> triple_disp;

	MER_NAMED_M_ELLIPSE_FROM_MER_TYPELIST_AND_BOOST_PP_SEQ_OF_ARGUMENTS
		(ml_3,(*ps1)(*ps2)(*pf),me1_3);
	MER_NAMED_M_ELLIPSE_FROM_MER_TYPELIST_AND_BOOST_PP_SEQ_OF_ARGUMENTS
		(ml_3,(*ps1)(*ps2)(*ps3),me2_3);
	MER_NAMED_M_ELLIPSE_FROM_MER_TYPELIST_AND_BOOST_PP_SEQ_OF_ARGUMENTS
		(ml_3,(*ps1)(*pss2)(*psc3),me3_3);
	MER_NAMED_M_ELLIPSE_FROM_MER_TYPELIST_AND_BOOST_PP_SEQ_OF_ARGUMENTS
		(ml_3,(*pss1)(*pss2)(*psc3),me4_3);

	triple_disp::go(me1_3, executor());		// unbekanntes Objekt gefunden
	triple_disp::go(me2_3, executor());		// triple_dispatcher(satellite&, satellite&, satellite&)
	triple_disp::go(me3_3, executor());		// triple_dispatcher(satellite&, space_station&, spacecraft&)
	triple_disp::go(me4_3, executor());		// triple_dispatcher(space_station&, space_station&, spacecraft&)

	delete pss1;
	delete pss2;
	delete pss3;
	delete psc1;
	delete psc2;
	delete psc3;
	delete ps1;
	delete ps2;
	delete ps3;

	delete pf;

	return 0;
}

3.3 Implementierung

3.3.1 Allgemeiner Aufbau

Allgemein ist der generische Dispatcher eine Generalisierung der oben vorgestellten "Rohvariante" des Double-Dispatchings (und eine Generalisierung des static_dispatchers von Alexandrescu). Deshalb hat er auch ein Laufzeitverhalten linear zu seinen beiden Argumenten! Also O(anzahl_klassen * anzahl_werte). Er funktioniert etwa so:

• 0. Markiere den 1. Typ.
• 1. Teste, ob das 1. Argument mit dem markierten Typ übereinstimmt, wenn ja, gehe zu 2, sonst zu 3.
• 2. Wenn alle Argumente dispatcht sind, rufe den Executor auf. Sonst speichere das dispatchte Argument mit dem passenden Typ und gehe zu 1., mit dem dispatchten Argument aus der Argumentliste entfernt. Markiere vorher den 1. Typ und lösche die vorherige Markierung.
• 3. Wenn der letzte konkrete Typ einen Dispatchingfehler auslöste, melde einen Fehler. Sonst markiere den nächsten Typ, lösche die vorherige Markierung und gehe zu 1.

3.3.2 Moderne Ellipsen

Das Problem, das moderne Ellipsen (Mells) lösen sollen, wurde oben schon angesprochen: die typsichere Übergabe einer zur Deklarationszeit unbestimmten Menge nicht-gleichtypiger Argumente. Das klingt kompliziert, ist es auch ein bisschen. Wieder einmal können uns Typlisten helfen: Mells sind rekursive Datenstrukturen, die Typlisten mit Werten "nachbilden". Ungefähr so:

Typliste (Templateparameter): int  ->  bool  ->  foobar*  -> eol
Zugehörige Variablen        :  a   -> true   ->  0xabc

Die konkrete Realisierung ist etwas komplizierter, da Datenstrukturen mit variabler Memberzahl auch nicht existieren. Aber wir wenden wieder denselben Trick wie bei Typlisten an: die Datenstruktur selbst ist rekursiv, und endlose Rekursion wird durch partielle Spezialisierung vermieden:

template<class Tlist>
struct modern_ellipse
{
  typedef typename Tlist::head head_t;
  head_t head;

  typedef typename Tlist::tail tail_t;
  modern_ellipse<tail_t> tail;

  modern_ellipse (head_t h, tail_t t)
    :head (h), tail (t)
  {
  }
};

template<class T>
struct modern_ellipse<TYPELIST_1(T)>
{
  typedef T head_t;
  head_t head;

  modern_ellipse (head_t h)
    :head (h)
  {
  }
};

Das war's eigentlich schon. Man könnte noch ein static const bool end hinzufügen, dass einfache Endetests erlaubt. Man muss dazusagen, dass die Struktur in modern_ellipse.h anders aussieht, was vermutlich auf mein unvollkommenes Verständnis von Templates zur Zeit des Schreibens zurückzuführen ist.
Mells werden ähnlich manipuliert wie Typlisten, hier nur ein Beispiel:

template<class Tlist, const unsigned i>
struct at
{
  static TL::TypeAt<Tlist, i>::Result go (modern_ellipse<Tlist>& mell)
  {
    return at<typename Tlist::tail, i - 1>::go (mell.tail);
  }
};

template<class L>
struct at<L, 0>
{
  static typename L::head go (modern_ellipse<L>& mell)
  {
    return mell.head;
  }
};

Man muss aber im Kopf behalten, dass man jetzt von compile-time-Berechnungen zu Laufzeitberechnungen kommt, und nicht mehr unbegrenzt Zeit hat. Da Mells praktisch einfach verkettete Listen sind, ist die Zugriffskomplexität wie anzunehmen (O(n)). Das ist aber nur ein geringes Problem, da meist eh nur auf das erste Element zugegriffen (und der Rest weitergegeben) wird.
Das Deklarieren von Mells ist etwas umständlich, deshalb gibt es auch dafür Makros (wie oben schon vorgestellt). Diese sind sehr kompliziert (da ich umgehen wollte, für jede Länge eines schreiben zu müssen), wer interessiert ist, kann sich boost.preprocessor (und dort die Datenstrukturen) näher anschauen.

3.3.3 Der Dispatcher

Nun haben wir alles zusammen: Typlisten, um zur Kompilierzeit Informationen über Typen zu halten, Mells, um variable Parameter zu ermöglichen, dynamic_cast, um den dynamischen Typ eines Objektes zu testen, einen offensichtlichen Algorithmus und Template-Metaprogrammierung, um den zu implementieren. Keine Sorge, das ist trotzdem noch kompliziert genug. Hier zeige ich der Klarheit wegen nur Quasi-C++-Code:

template
<
  class Bases,
  class Types,
>
class disp
{
private:
  typedef typename Types::head head;
  typedef typename Types::tail tail;

  template<class L_List, class R_List>
  static void go_ 
  (
    /* bereits dispatchte Argumente, als Mell von L_List */ m1,
    /* noch nicht dispatchte Argumente, als Mell von R_List */ m2
  )
  {
    if (/* erstes argument ist in m2 vom Typ typename head::head */)  // Übereinstimmung gefunden
      return disp<Bases::tail, tail>::go_ (/* Mell aus m1 und dem Argument */, m2.tail); // das nächste Argument dispatchen
    else       // keine Übereinstimmung gefunden
      return disp<Bases, typelist<typename head::tail, tail> >::go_(m1, m2);   // nächsten Typ testen
  }

public:
  //öffentlicher Einstieg
  template<class L>
  static void go(/* die Argumente, verpackt als moderne Ellipse von L */ m)
  {
    if (/* erstes argument ist vom Typ typename head::head */)  // Übereinstimmung gefunden
      return disp<Bases::tail, tail>::go_ (/* das gefundene Argument als Mell */, m.tail); // das nächste Argument dispatchen
    else     // keine Übereinstimmung gefunden
      return disp<Bases, typelist<typename head::tail, tail> >::go(m);   // nächsten Typ testen
  }
};

// jetzt gibt es noch 2 Spezialfälle: Fehler und Erfolg
// ersterer tritt auf, wenn Types::head eol ist
// letzterer, wenn alle Argumente dispatcht sind (also Types eol ist)
// (und implizite Fehler, wenn z.B. Types und Bases nicht gleich lang sind)

//Fehler
template
<
  class Bases,
  class Rest_Types
>
cass disp
<
  Bases,
  typelist<eol, Rest_Types>
>
{
private:
  template<class L, class R>
  void go_(/* s.o. */ m1, /* s.o. */ m2)
  {
    // Fehler
  }
};

//Erfolg
template
<
  class Bases,
  class T
>
class disp
<
  Bases,
  TYPELIST_1(TYPELIST_1(T))
>
{
private:
  template<class L_List, class R_List>
  static void go_ (/* s.o. */ m1, /* s.o. */ m2)
  {
    if (/* erstes Argument ist vom Typ typename head::head */)  // Übereinstimmung gefunden
      return handler (/* Mell aus m1 und dem gefundenen Argument */) // Erfolg
    else     // keine Übereinstimmung gefunden
      return disp<Bases, typelist<typename head::tail, tail> >::go_(m);   // nächsten Typ testen
  }
};

Der Dispatcher ist auch nicht so toll: man sollte Fehlerbehandlung und Handleraufruf modularisieren, was aber simpel ist.
Wieder muss erwähnt werden, dass der richtige Code viel komplizierter und umständlicher ist, was man aber zu einem großen Teil auf mein zur Zeit des Schreibens unvollständiges Verständnis von Templates zurückzuführen ist.

Quellen

• Modernes C++ Design (Scott Meyers)
• Mehr Effektiv C++ (Andrei Alexandrescu)

[ness]

Also erst mal . Ich fand das klasse, dass du (und andere) in deiner (ihrer) Freizeit die Rechtschreibprüfung machen. Eine Frage: in 3.3.1 hast du "Laufzeitverhalten linear in ..." zu "Laufzeitverhalten linear zu ..." gemacht, ohne das zu kennzeichnen. Hast du das vergessen (zu kennzeichnen), oder das nur versehentlich geändert? Kann man meine Variante nicht schreiben?

[michba]

ness schrieb:

Eine Frage: in 3.3.1 hast du "Laufzeitverhalten linear in ..." zu "Laufzeitverhalten linear zu ..." gemacht, ohne das zu kennzeichnen.

Oh, das muss ich vergessen haben zu kennzeichnen. Ich hab das nicht alles am Stück gemacht, da muss ich es wohl irgendwie übersehen haben...
Ich habe das also schon absichtlich geändert, weil ich den Ausdruck "etwas ist linear in etwas" noch nie gehört habe, sondern nur "etwas ist linear zu etwas". Aber wenn du dir sicher bist, dass es diesen Ausdruck gibt, kannst du es auch gern wieder rückgängig machen.

[ness]

Naja, es klang normal für mich, aber ich vertrau dir da mal.

[michba]

Hi, ich hab noch mal gesucht, und anscheinend hast du doch recht; auf den meisten Informatik-Seiten von Unis heißt es "linear in"...
Das kannst du dann ja noch kurz ändern, wenn du den endgültigen Beitrag erstellst.

[joomoo]

Mir ist gerade aufgefallen, dass die Autoren vertauscht sind:

* Modernes C++ Design (Scott Meyers)
* Mehr Effektiv C++ (Andrei Alexandrescu)

Modernes C++ Design ist von Andrei A. und Mehr Effektiv C++ (programmieren?) von Scott Meyers.

mfg.

[ness]

Danke, das ist natürlich ziemlich blöd.