Container mit unterschiedlichen Template-Spezialisierungen

[eXile]

Und schon wieder ein Problem, an welchem ich rumnage. Haben wir einen Container, sagen wir eine std::list, so gibt es ein Problem, wenn man Instanzen einer Template-Klasse in unterschiedlichen Spezialisierungen speichern möchte. Sagen wir unsere Template-Klasse ist MyItem<T>, und unsere Spezialisierungen seien MyItem<MyA> und MyItem<MyB>. Da MyItem<MyA> und MyItem<MyB> ja schließlich unterschiedliche Typen sind, kann man sie nicht einfach in einem homogenen (also gleich-typigen) Container speichern.

Wenn man über das Problem ein wenig nachdenkt, so kommt man zumindest auf vier unterschiedliche Lösungen:

1. Die ekelhafte Lösung.
   
   Man erstellt ein enum:

   Code: Alles auswählen

   enum MyTypeEnum
   {
           myAType,
           myBType
   };

   Und macht dann einfach eine Verzweigung bei den zu implementierenden Funktionen:

   Code: Alles auswählen

   void MyItem::Print()
   {
           if(myType == myAType)
                   cout << "MyItem - myA" << endl;
           else if(myType == myBType)
                   cout << "MyItem - myB" << endl;
   }

   Damit muss man nur noch homogene Typen speichern:

   Code: Alles auswählen

   list<MyItem> myList;

   Ich habe solchen Code oft genug gesehen; er ist so ekelhaft, dass diese Lösung schon einmal indiskutabel ist. ;)
2. Die Lösung ohne Indirektion.
   
   Man spezialisiert einfach die Myitem-Klasse:

   Code: Alles auswählen

   template <class T>
   class MyItem
   {
   public:
           void Print();
   };
    
   template <>
   void MyItem<MyA>::Print()
   {
           cout << "MyItem - MyA" << endl;
   }
    
   template <>
   void MyItem<MyB>::Print()
   {
           cout << "MyItem - MyB" << endl;
   }

   Damit hält man homogene Listen vor, und zwar pro Typ eine:

   Code: Alles auswählen

   list<MyItem<MyA>> myAList;
   list<MyItem<MyB>> myBList;

   Das Einfügen kann man dann mittels Hilfsfunktionen auch ganz geschmeidig implementieren:

   Code: Alles auswählen

   template <typename T>
   void MyItemList::AddItem(MyItem<T> theItem)
   {
           GetTypedList<T>().push_back(theItem);
   }
    
   template <>
   list<MyItem<MyA>> & MyItemList::GetTypedList()
   {
           return myAList;
   }
    
   template <>
   list<MyItem<MyB>> & MyItemList::GetTypedList()
   {
           return myBList;
   }

3. Die Lösung mit Indirektion.
   
   Man lässt alle Template-Spezialisierungen von einer gemeinsamen Basis-Klasse erben:

   Code: Alles auswählen

   class MyItemBase
   {
   public:
           virtual void Print() = 0;
   };

   Code: Alles auswählen

   template <class T>
   class MyItem : public MyItemBase
   {
   public:
           virtual void Print();
   };
    
   template <>
   void MyItem<MyA>::Print()
   {
           cout << "MyItem - MyA" << endl;
   }
    
   template <>
   void MyItem<MyB>::Print()
   {
           cout << "MyItem - MyB" << endl;
   }

   Und hält eine homogene Liste von unique_ptrern:

   Code: Alles auswählen

   list<std::unique_ptr<MyItemBase>> myList;

4. Man nehme boost::variant. Nicht von mir ausprobiert.

Kurze Diskussion:

1. Stinkt nach Fisch.
2. Ist wohl am effizientesten, da es nur homogene Datentypen ohne Indirektionen und ohne virtuelle Funktionen hält.
3. Benutzt Indirektion, braucht virtuelle Funktionen.
4. Keine Ahnung. Habe noch nie damit Erfahrungen gemacht. Hat jemand von Euch schon einmal damit rumgespielt?

Was meint Ihr dazu? Das riecht so sehr nach Standard-Problem, als dass es eine Standard-Lösung geben sollte; nur ich habe wohl wieder Tomaten auf den Augen, weil ich keine sehe. ;)

[kaiserludi]

Ich würde Variante 3 nehmen und nur dann über eine andere Lösung nachdenken, wenn der Container tatsächlich zum Performanceflaschenhals werden sollte. Fast immer wird der Overhead durch die Polymorphie für die Gesamtperformance des Programms absolut vernachlässigbar sein.

[Alexander Kornrumpf]

Hmm, ich meine doch mich dunkel zu erinnern, dass es einen Grund gab polymorphe Typen nicht zusammen in einer Liste zu speichern. Aber wenn du ihn nicht kennst kann er so wichtig auch nicht gewesen sein.

Variante 2 sieht für mich überhaupt nicht nach einer Lösung aus sondern nach dem ursprüngglichen Problem. Nämlich dass sie nicht in derselben Liste sein können. Und wenn das kein Problem ist (du also damit leben kannst, zwei Listen zu haben) dann würde ich doch genau das tun, oder?

[odenter]

Hmm, ich meine doch mich dunkel zu erinnern, dass es einen Grund gab polymorphe Typen nicht zusammen in einer Liste zu speichern. Aber wenn du ihn nicht kennst kann er so wichtig auch nicht gewesen sein.

Du hast bestimmt das hier: http://pages.cpsc.ucalgary.ca/~kremer/S ... /ref2.html genannte Problem im Hinterkopf oder?

Variante 2 kann auch gut sein, wenn es nur ein paar Listen sind. Wenn Du nachher 10 Listen mit unterschiedlichen Typen brauchst, dann würde ich Variante 3 nehmen. Bei nur 2 Typen z.B. aber Variante 2.

Ich würde Version 3 nehmen und Zeiger auf den Basistyp speichern und irgeneinen shared_ptr verwenden.
Wenn ich keinen shared_ptr verwenden würde dann würde ich als Regel entweder den Erzeuger die Objekte löschen lassen, oder die Liste als Regel einfach am Ende leeren. Je nachdem wie ich gerade drauf bin und wofür das genau ist.
EDIT:
Und das würde ich vermutlich auch kapseln, und ne MyItemList zur Verfügung stellen die das alles macht, wenn ich keine Lust auf smart pointer habe.
So wie zu einem "new" ein "delete" gehört, gehört dann bei Dir eben zu einem "create" auch ein "release", völlig normal. Wenn das nicht beachtet wird, ist es eben ein Programmierfehler, auch völlig normal. :)

Variante 4 ist doof, "variant" ist immer gaga. Da könntest auch void* in der Liste speichern, geht auch.

[eXile]

Variante 2 sieht für mich überhaupt nicht nach einer Lösung aus sondern nach dem ursprüngglichen Problem. Nämlich dass sie nicht in derselben Liste sein können. Und wenn das kein Problem ist (du also damit leben kannst, zwei Listen zu haben) dann würde ich doch genau das tun, oder?

Da hast du recht. ;) Im Augenblick kann ich damit sehr gut sogar leben. Es handelt sich nämlich um einfache Listen von Vertex- und Pixelshadern; die verschiedenen Shader-Arten ändern sich zum Glück nicht so oft. Variante 2 zeigt eigentlich einfach nur den syntaktischen Zucker, denn man zur einfachen Implementation von AddItem benutzen kann.

Hmm, ich meine doch mich dunkel zu erinnern, dass es einen Grund gab polymorphe Typen nicht zusammen in einer Liste zu speichern. Aber wenn du ihn nicht kennst kann er so wichtig auch nicht gewesen sein.

Mmmh, bei mir klingelt da kein Glöckchen.:?

Du hast bestimmt das hier: http://pages.cpsc.ucalgary.ca/~kremer/S ... /ref2.html genannte Problem im Hinterkopf oder?

Sehr schöner Link, danke! Die Implementierung von dort entspricht im Wesentlichen Variante 3. Eine Sache, die ich im Eingangspost nicht geschrieben habe, die mir aber aufgefallen ist und sich auch im Link wiederfindet:

One of problems with this solution is that it defeats a lot of the efficiency of the STL. The STL goes to great lengths to efficiently store its objects in blocks (separating memory allocation/deallocation and construction/destruction). The Ref2 class blatantly allocates and deallocates its referents one at a time!

Variante 4 ist doof, "variant" ist immer gaga. Da könntest auch void* in der Liste speichern, geht auch.

Da ist was dran. Diese komischen Visitors sind mir dabei auch suspekt; ich glaube, dass ich hierfür nicht wirklich geeignet.

[CodingCat]

Und das würde ich vermutlich auch kapseln, und ne MyItemList zur Verfügung stellen die das alles macht, wenn ich keine Lust auf smart pointer habe.
So wie zu einem "new" ein "delete" gehört, gehört dann bei Dir eben zu einem "create" auch ein "release", völlig normal. Wenn das nicht beachtet wird, ist es eben ein Programmierfehler, auch völlig normal. :)

Wo ist der C++-Spirit? Programmier doch gleich C oder Java! :P

Ich gebe zu, wasserdichte Smart Pointers zu schreiben ist nicht ganz trivial, höchst traurig angesichts des Gewinns. Eventuell sollte eine C++21 STL dafür ein Meta-Template anbieten, schlussendlich ist es ja doch immer dasselbe.

Variante 2 sieht für mich überhaupt nicht nach einer Lösung aus sondern nach dem ursprüngglichen Problem. Nämlich dass sie nicht in derselben Liste sein können. Und wenn das kein Problem ist (du also damit leben kannst, zwei Listen zu haben) dann würde ich doch genau das tun, oder?

Da hast du recht. Im Augenblick kann ich damit sehr gut sogar leben. Es handelt sich nämlich um einfache Listen von Vertex- und Pixelshadern; die verschiedenen Shader-Arten ändern sich zum Glück nicht so oft. Variante 2 zeigt eigentlich einfach nur den syntaktischen Zucker, denn man zur einfachen Implementation von AddItem benutzen kann.

Dafür gewinnst du auf jeden Fall Mike Actons Data-Oriented-Design-Preis. Naja, vielleicht doch nicht; du nutzt C++, Templates und die STL. :mrgreen:

Wenn es kein Problem ist, verschiedene Listen zu haben, dann sind verschiedene Listen auf jeden Fall die effizienteste Lösung. Dank Templates kostet dich das nicht mal wesentlich mehr Code. Wenn du die Elemente am Ende womöglich auch noch typabhängig behandeln musst (z.B. mit vollständigem Typ aus der Liste holen?), dann ersparen dir die Listen gleich noch lästige Checks und Casts.

Oder, ganz einfach, um nochmal eben genannten zu zitieren: Sort, don't search.

[eXile]

Ich gebe zu, wasserdichte Smart Pointers zu schreiben ist nicht ganz trivial, höchst traurig angesichts des Gewinns. Eventuell sollte eine C++21 STL dafür ein Meta-Template anbieten, schlussendlich ist es ja doch immer dasselbe.

In der Tat; seitdem ich ich mit kleinen NonCopyAssignable/NonAssignable/NonCopyable-Hilfsklassen bestimmte std::move-Semantiken erzwinge, hat sich die Lebensqualität signifikant verbessert. :)

Dafür gewinnst du auf jeden Fall Mike Actons Data-Oriented-Design-Preis. Naja, vielleicht doch nicht; du nutzt C++, Templates und die STL. :mrgreen:

Grrr, der Herr Acton; seitdem ich diese Antwort gelesen habe, steigt schon mein Blutdruck, wenn ich den Namen nur lese. :evil:

(Kleiner Rant am Rande: Problemlösung ist meiner Meinung nach wie ein bidirektionaler Path-Tracer: Man befindet sich im Dunkeln, kennt das Problem (Ziel) und wo man aktuell steht (Start), und versucht von beiden Enden her Lösungspfade zu finden. Die Pfade vom Start aus stellen bekannte Algorithmen dar (STL; spatiale Datenstrukturen wie kd-Trees, BSP-Trees, etc; bekannte Graph-Algorithmen wie Traveling Salesman; usw.). Die Pfade vom Ziel aus sind Problem-individuelle Lösungen. Irgendwo in der Mitte trifft man sich, und hat das Problem gelöst.

Ein pauschaler Verzicht auf die STL ist genauso wie ein pauschaler Verzicht auf individuelle Lösungen kompletter Nonsens. ;))

Wenn es kein Problem ist, verschiedene Listen zu haben, dann sind verschiedene Listen auf jeden Fall die effizienteste Lösung. Dank Templates kostet dich das nicht mal wesentlich mehr Code. Wenn du die Elemente am Ende womöglich auch noch typabhängig behandeln musst (z.B. mit vollständigem Typ aus der Liste holen?), dann ersparen dir die Listen gleich noch lästige Checks und Casts.

Hab's jetzt auch so gemacht, und funktioniert soweit sehr gut.

Vielen Dank für die gepflegte Diskussion hier. :)