Wie macht man einen STL Container, der pointer enthält und seine Elemente besitzt

oder

Eine Odyssee.

Der STL container vector ist ein vielseitiges und flexibles Werkzeug zur Verwaltung von generischen Objektlisten.
Er läßt sich allerdings in der gegebenen Form eher nur für kleine Objekte einsetzen (d.h. für Objekte, die sich schnell kopieren lassen, bzw deren Kopierkonstruktor einigermaßen billig ist).

Warum dies? Weil der vector beim sortieren, herumschieben von Elementen in diversen anderen algorithmen (man denke an unique, make_heap, reverse und andere), und beim reallokieren die Elemente umkopieren muß.

Dies kann insbesondere beim reallokieren von großen arrays (welches nötig wird, wenn die Endgröße vor dem Einfügen nicht bekannt ist - siehe push_back) sehr teuer werden; auch direktes sortieren von großen Elementen kann teuer sein (Performancemessungen hiezu stehen noch aus.)

Im Falle dass solche Elemente verwaltet werden ist es also normalerweise besser, diese Stück für Stück vom heap zu allokieren, und nur Pointer auf diese zu verwalten.

Da ein STL vector aber nur seine Elemente (in diesem Fall pointer) verwaltet, und nicht die Elemente auf die die Pointer zeigen, ist ein Überbau nötig, um keine Memory leaks entstehen zu lassen.

Hiezu bieten sich einige Strategien und, die ich hier kurz schildern will.
 

1. Man arbeitet mit 2 vectoren:

Einer davon dient nur dazu die Elemente zu halten und zu besitzen, und an genau definierten Punkten (etwa am Programmende) werden alle Elemente gelöscht.
Dies führt dazu dass der Speicher NUR an diesen Punketn freigegeben wird, was aber normalerweise kein gröberes Problem darstellt, da der Speicher ohnedies dank der Suballokation der C++ Runtime Heapverwaltung nur durch expliziten Aufruf von heapmin oder ähnlich ans Betriebssystem zurückgegeben wird.

Dieser Ansatz erscheint aber unpraktikabel aus folgenden Gründen:

a) Neu hinzugekommene Elemente muß man in BEIDEN vectoren einfügen - heftige Fehlerquelle.

b) Das Programm wird unnötig verkompliziert und unverständlich.

Beurteilung: Recht unbrauchbar.
 

2. Man automatisiert den Ansatz,

indem man die großen Objekte (im folgenden nenne ich diese mal GOB's) sich selbst einer einem nur intern bekannten liste von Heap Objekten verwalten läßt.
D.h. wan immer ein GOB vom Heap allokiert wird, trägt es sich selbst in dies Liste ein, die von aussen nicht sichtbar ist.
Löscht man es, so trägt es sich selbst wieder aus.
An den wohldefinierten Punkten (etwa Programmende) kann die gesamte Liste gelöscht werden - hiebei muß man aber achtgeben, bzw wissen, daß keine Referenzen oder Pointer mehr auf ein solches Objekt verweisen.
Dieser Ansatz entspricht dem obigen, mit dem Vorteil, daß die Programmstruktur dadurch nicht korrumpiert wird.

Nachteile:

a) Es muß Punkte geben, an denen man weiß, daß KEIN Element des gegebenen Types mehr irgendwo referenziert wird. Nur dann kann der Speicher bereinigt werden. (im Prinzip haben wir es hier mit dem ersten Schritt in Richtung Garbage Kollektor zu tun, der allerdings nicht weiß, wann und wo Referenzen existieren - diese Arbeit hat der Programmierer zu leisten und auch der kann nur einen alles oder nichts Startegie verfolgen).

Diese Punkte sind aber in vielen Systemen, insbesondere in dokumentbasierten Systemen sehr wohl ausfindig zu machen, etwa, beim schließen eines Dokuments.
Man muß sich allerdings des Umstandes, dass ALLE GOBS gelöscht werden, auch jene, die NIE in einen vector eingetragen wurden bewußt sein.

Die Semantik einer solchen Operation ist einigermaßen zweifelhaft, da unsere ursprüngliche Absicht ja die war, den Container seine elemente besitzen zu lassen - also sollten nur die Elemente EINES bestimmten containers gelöscht
werden.

b) Auch hier wird Speicher nicht freigegeben, wenn er verfügbar wäre, sondern erst an den wohldefinierten Punkten. Hat man etwa ein viele tausend Polygone großese 3D Modell im Speicher und wendet Reduktionsverfahren darauf an, so bleibt der Speicherbedarf unverändert - dies wäre schlecht.

Alles in allem erscheint auch diese Lösung für Systeme, die sich sehr dyanmisch verändern nicht wirklich praktikabel - sie scheint geeignet für Module, die in einer Art Batch Modus (nicht sehr interaktiv) laufen, eine Menge
Objekte erzeugen und Manipulieren und vor dem Verlassen des Moduls alles zusammenräumen sollen.

Nichtsdestotrotz hat einer solcher Ansatz seien eignen Wert insofern als man ihn benutzen sollte um die Objekte nicht gerade automatisch zu löschen (es sein denn vor Programmende, oder als zusätzliche Sicherheit an eindeutig
identifizierten No-GOB-Syncpoints) sondern um leaks zu überprüfen.

Eine Implementation eines solchen Systems findet sich in GObject.h - um den Machnismus zu nutzen muß nur von GObject abgeleitet werden; GObject::ShowAll zeigt dann zu jedem Zeitpukt alle verfügbaren GObject's an (vermittels Aufrufs der Show member function - diese sollte überladen werden für den eigenen Typ).

Beurteilung: Beschränkt brauchbar, allerdings nur für ganz bestimmte Systeme.
 

3. Dies ist der wohl billigste Ansatz:

Man überlädt die destroy Funktion für den Typ "MyObject **" solchermaßen, daß "MyObject *" gelöscht wird.

Dann wird beim löschen des vectors, oder aber auch beim erasen von Elementen der Speicher erfolgreich freigegeben.

Nachteile:

a) Es lassen sich nun keine vectoren von solchen Elementen mehr bilden, die ihre Elements NICHT besitzen sollen. Dieser Nachtei, wiegt SCHWER! Oft muß parallel zu einem besitzenden ein nicht bsitzender (nur referenzierender
vector) verwendet werden, etwa um eine andere Reihenfolge dieser Elemente zu erhalten oder ein subset auf dem gearbeitet werden soll oder ähnliches.
Dies macht diese Methode einigermaßen unbrauchbar.

b) Wir haben hiermit wiederum die Semantik eines bestimmten Objekttyps für das gesante Programm (Translation Unit) verändert, was NICHT unser Ziel war - wir wollten Ursprünglich EINEN bestimmten Container mit owner Semantik versehen.

Beurteilung: Alles in allem, eher unbrauchbar.
 

4. Man verwendet einen Elementadapter, ähnlich einem auto_ptr

Diese Methode läßt sich differenzieren nach der Art der ownership, die der gewählte Adapter hat.

i) auto_ptr: Ungeeignet. Ein auto_ptr gibt seine ownership bei Zuweisung unkonditional ab UND hat destruktive Kopiersemantik, was heißt, daß der die ownership abgebend auto_ptr zu einem NULL pointer wird. Dies führt dazu, daß etwa algorithmen nach dem folgenden Schema abstürzen:
 

Beurteilung: Komplett unbrauchbar

ii) Ähnlich auto_ptr, mit NICHT destruktiver Kopiersemantik (wird nicht NULL)

Ebenfalls völlig ungeeignet da Algorithmen nach dem folgenden Schema abstürzen:
 

Ferner würde jeder solche Adapter nun typischerweise doppelt so groß sein, da ein Maschinenwort mitgeführt werden muß um die ownership anzuzeigen. Dies würde das umkopieren wiederum unnötig verteuern (etwa doppelt so langsam).

Beurteilung: Komplett unbrauchbar

Bemerkung: Es wäre dennoch ein Ansatz für Container mit ownership semantik, allerdings nicht im STL Stil in Verbindung mit generischen algorithmen, sondern nur mit einer selbst geschrieben Klasse von algorithmen, die Rücksicht nehmen auf die beschriebene Ownership Semantik. Eine solche Containerklassenbibliothek mit entsprechenden Adaptoren findet sich etwa in der Open Class Library des Visual Age C++ compilers von IBM.

iii) Referenzsemantik, solange möglich

Dies wäre eine sichere Lösung, die die Kosten minimieren würde, indem sie nur kopiert wenn dies nötig wird (etwa wenn eine Referenz modifiziert wird.)
Diese ist relativ aufwendig zu implementieren da esfolgendes leisten muß:  

Alles in allem müssen solche autopointer nach aussen so aussehen, als ob sie value semantik haben, nach innen aber optimieren, so gut es geht. Ein solcher autoptr wäre erst zu entwickeln - es gibt ähnliche Ansätze etwa bei string Klassen, was diese zu guten Kandidaten für eine By Value Verwendung in containern macht.

Die zu verwaltende Klasse im Container zu einer solchen Klasse zu machen, erscheint zu viel Aufwand - feasible wäre nur eine generische (templatisierte) Adapterklasse.

Beurteilung: Gut aber komplex. Kopieren wird etwas verteuert.
 

Eine mögliche Implemetierung einer solchen pointer adapter Klasse (unter der vereinfachenden Annahme, dass die Elemente eine gemeinsame Basisklasse haben können) findet sich in var_ptr.h

Für eine detaillierte Beschreibung dieses Ansatzes, siehe auch die englische Ausgabe dieses Artikels: STLCONT

5. Man schreibt einen Container Adapter

Dies ist wohl die einzige sichere und saubere Methode, in dem Sinne, daß unbeabsichtigte memory leaks völlig verhindert werden können, als auch in dem Sinne, daß nicht etwa noch referenzierte Objekte gelöscht werden. Ferner ist keine Umstrukturierung des Programms nötig.

Eine mögliche implementation findet sich in vecadap.h

Nachteile:

a) Die Benutzung des Containers wird stark eingeschränkt. Insbesondere sind keine Standardalgorithmen aus <algo> mehr direkt anwendbar - wann immer ein solcher algorithmus benötigt wird, muß von der Container Klasse abgeleitet werden und dieser zu einer memberfunction gemacht werden, in der sowohl der orginal algorithmus aufgerufen wird, als auch dafür gesorgt wird, daß dieser keine leaks entstehen läßt.

Dies scheint eine starke Einschränkung zu sein, ist aber auch bitter nötig, denn:

Die Algorithmen aus <algo> kümmern sich nicht um etwaige entstehende Leaks - etwa würde eine naive Anwendung von remove_if leaks oder sogar Abstürze entstehen lassen, da die NICHT zu removenden elemente am Anfang des vectors kompaktiert werden, am Ende des vectors allerdings dann NICHT die zu removenden elemente stehen, sondern Überreste des remove Prozesses, die keine besondere Bedeutung haben, als dass sie vermittels erase zu entfernen sind.
Es kann sich dabei durchaus um Kopien der NICHT zu entfernenden Elemente handeln - wird nun die überladene Version von erase aufgerufen, die die GOBs löscht, so werden die falschen GOBS freigegeben.

Also muß darauf geachtet werden, WIE die algorithmen angewendet werden - viele der algorithmen die die arrays modifizieren werden überhaupt unbrauchbar sein. (etwa unique?).

b) Es läßt sich schwer vorhersehen, welche Operationen nötig sein werden. Etwa gibt es in der vorgestellten Version kein remove_if äquivalent - dies stellt sich in der Verwendung dann aber als eine häufig benötigte operation heraus
(etwa: entferne alle selektierten Polygone).

Um a&b zu umgehen wäre es nun möglich, die begin und end iteratoren des Containers ins interface zu nehmen (siehe das define DANGEROUS_BUT_FLEXIBLE) sodaß der caller alle algorithmen anwenden kann.
Er dürfte dann allerdings diese algorithmen anwenden, die keine elemente verwerfen sondern nur die ORDNUNG der elemente verändern, wie etwa, reverse, sort, rotate und dergleichen. Dies KANN NICHT sichergestellt werden, ja, man ist sogar geneigt selbst auf diese Restriktion zu vergessen, und daher ist es wohl besser, diese algorithmen als members unter der Kontrolle der Containerklasse (und NICHT des Aufrufers) laufen zu lassen.

Sollten algorithmen fehlen, so wären diese in einer abgeleiteten Klasse zu implementieren, die Zugriff auf den Container hat, da dieser protected ist.
Diese könnte nun durch falsche Manipulation den orginal container sehr wohl kompromitieren (leaks, abstürze) hat aber eben die Verantwortung dies ordnungsgemäß zu handhaben - nicht ganz sicher, aber recht sicher, und es
bietet die Möglichkeit ohne Performance Verluste die Klasse auf die Bedürfnisse des callers abzustimmen. Der Caller selbst ist aus dem Schneider.

Beurteilung: Erscheint brauchbar.

Vorschlag für standardalgorithmen, die fast immer gebraucht werden, und daher
members von der Basisklasse werden sollten:

sort, mit und ohne explizitem Sortierkriterium
remove_if
reverse
 

6. Ableiten, erase und destructor überladen und gefährliche members private

machen

Dies wären alle Funktionen die nicht const iteratoren zurückliefern, da man über diese das Pointer Array in unzulässiger weise modifizieren könnte sowie die nicht const Version von operator[], da hier durch eine Zuweisung ein leak entstehen könnte. Siehe unten.

Ist ziemlich äquivalent zum Adapter Ansatz, allerdings gefährlicher, da man so manchen gefährlichen member nicht gleich erkennt.

So kann etwa die nicht const version von operator[] leicht zu leaks führen, wenn man etwa folgenden code schreibt:

c.push_back( new Test(1) ) ;
c.push_back( new Test(2) ) ;

c[0] = c[1] ; // Leak: GOB Test(1) lost!

Man müßte diese also um sicherheit zu erlangen private oder zumindest protected machen - dies würde dazu führen daß die algorithmen aus <algo> die diesen operator benötigen erneut nicht funktionieren. Es wären erneut memberalgorithmen zu definieren, die mit den basisalgorithmen arbeiten, allerdings unter spezieller berücksichtigung der Umstände.

Beispiel implementation:  rvect.h

Vorteile:

a) Gewisse iteratoren (wie const iteratoren) können Freihaus verwendet werden (müssen allerdings doch deklariert werden in der Klasse, da die nicht const versionen als protected überladen werden müssen und somit auch die const versionen überladen werden).

b) Das interface hält sich relativ steng an das schon von andern STL containern gewohnte interface, ausser einer neuen member function zum Einfügen von Elementen (insertAt). Diese wurde eingeführt, da das einfügen vermittels operator[] und operator= zu leaks führen würde und nur eine kombinierte Indizierungs und Einfügeoperation auf Ebene des containers dies verhindern kann.

c) Alle nicht explizit versteckten members stehen zur vollen Verfügung.

d) Algorithmen, die den container nicht modifizieren stehen zur Verfügung (etwa copy).

Nachteile:

a) Modifizierende Algorithmen müssen zu members werden und teilweise recht aufwendig codiert werden, um leaks zu vermeiden (siehe etwa remove_if in der Beispiel Implementation revct.h)

b) Dieser Nachteil trifft die Container Adapter Klasse genauso wie diese Variante:
Wenn der Compiler keine member templates unterstütz, können an sort, remov_if und ähnliche funktionen keine function obejcts als predicates übergeben werden sondern nur function pointers - das ergibt eine performance Strafe. Dies entspricht ungefähr der Situation unter C, wo man bei qsort function pointers verwenden mußte und sollte kein allzugroßes Problem darstellen - es ist auf jeden Fall besser als ein value container, bei dem explizites kopieren der Objekte in diesem Fall stattfände.
Bei compilern mit member templates läßt sich dieser Nachteil komplett ausschalten.

Eine andere Möglichkeit wäre, die angepaßten Algorithmen zu friends der Klasse zu machen - dann wäre obiger Nachteil hinfällig. Hierzu sind noch Untersuchungen nötig.

Beurteilung: Erscheint brauchbar. Womöglich die beste Variante.

Zusammenfassung:

Wie in Stroustroup's C++, The Language nachzulesen, ist der wohl beste wenn auch arbeitsintensivste und gewissermaßen "hausbackenste" Weg der einen Container Adapter zu erzeugen (evtl. abzuleiten, siehe Punkt 6.)

Eine einzige weitere Alternative wäre die von intelligenten Pointer Adaptoren, die aus ainer Klasse mit primitiver value Semantik eine solche mit intelligenter machen und somit die Kopierkosten reduzieren. Untersuchungen auf
diesem Gebiet sowie eine Referenzimplementation sind noch ausständig. Diese Varianten wären aber unter allen Umständen langsamer und würden mehr Speicherplatz benötigen, kommen daher für high Performance Lösungen nicht in Betracht und widersprechen insofern dem Geist der STL.

Es erscheint verwunderlich, dass eine so wichtig Art von Containern (die Referenzen auf ihre Elemente besitzen, und diese bei Bedarf richtig löschen) von der STL so stiefmütterlich behandelt wird.

Bei den meisten Anwendungen werden Container dieser Art benötigt! Da es nun hiefür keinen Standard gibt und der existierende vector sich nur schwer hiefür einsetzen läßt, ist wiederum eine Fülle von eigenlösungen zu erwarten, die
vermutlich auf vector basieren und die Gestalt von Containeradaptoren haben werden. Es ist allerdings nicht anzunehmen, dass sich diese Lösungen gut und schlüssig in das Konzept der STL fügen, und wie wir gesehn haben, sind ja bereits durch die Benutzung von adaptoren, die Hauptvorteile der STL, nämlich die Benutzung generischer algorithmen, verloren gegangen.
 
Aus all dem gesagten leitet sich für mich ab, dass die Lösung 6 die beste ist - sie bietet die meiste Funktionalität bei relativ hoher Sicherheit gegen Fehlbenutzung; sie entspricht in ihrem Interface am nähesten den schon existierenden STL containern und sie ist sowohl was Speicherplatz als auch Rechenzeit betrifft so billig als möglich (you pay only what you need - Prinzip). (einzige Ausnahme, die bei manchen Compilern notwendige Verwendung von function pointern, siehe jedoch die ausständige Untersuchung von algorithmen als friends der Klasse).

Was wäre wünschenswert:

Es wäre gut, wenn man eine Methode an der Hand hätte, modifizierende algorithmen in 2 Klassen zu teilen, destruktive und nicht destruktive. Nicht destruktive Algorithmen würden sich dadurch auszeichen, dass sie Elemente eines containers nur umordnen (sort, reverse,...) und könnten OHNE GEFAHR auf die nicht const iteratoren des containers zugreifen! Da diese aber aus Sicherheitsgründen protected wurden, muss man für jeden neuen solchen Algorithmus von dem Container ableiten und den Algorithmus zu einem member respektive friend machen.