[C++] Die Suche nach einem passenden Sequence-Container

Ich fass mich mal kurz und so allgemein wie möglich...

Ich suche einen passenden Sequence-Container, welcher möglichst schnell das ständige Entfernen und Hinzufügen von Elementen, den reihenweisen Zugriff, beliebigen Zugriff, sowie die Sortierung beherrscht.
(Es geht um den Einsatz in einer Spieleengine, also meine ich wirklich schnell.)

Bisher kam ich mit Vectors ganz gut zurecht, bin aber zufällig auf ihre Ineffizienz der Reallokation gestoßen, weswegen ich mir nun Gedanken machen was nun besser sei.
Die STL Sequence Container haben alle ihre Stärken und Schwächen. Ich bin auf der Suche nach etwas dass alles irgendwie gut kann.


Zusätlichen Libs bin ich nicht abgeneigt, muss aber plattformunabhängig funktionieren, und sollte nicht zu fett sein.


Schonmal Danke im Voraus.

Versuchs mal mit List.

Der einzige Nachteil ist, dass man nur in linearer Zeit auf ein beliebig indexiertes Element zugreifen kann. (Das geht bei Vector in constant time.)
Ansonsten sind die idR als doppeltverlinkte Zeigerliste implementiert und bieten somit Insertion und Loeschung an beliebigen Stellen sowie vor- und ruecklaeufige Iteration und Vertauschung von Elementen in contant time.
Zudem sind sie Teil der STL. Das wird wohl das beste sein, was du kriegen kannst. Alle von dir genannten Eigenschaften sind in Contant Time einfach nicht umsetzbar.

Ich möchte auch einen Esel, der Gold scheißt, und wenn er alt ist, auch noch köstlich schmeckt. :P

Braucht das den deine Spieleengine wirklich? Und es stimmt was Luki sagt, was du willst geht einfach nicht. Eine List kann keinen schnell Zugriff haben, überleg mal wie die Struktur von so einer Liste ist dann wird dir das schnell klar. Ein Array ist dafür schlecht beim hinzufügen/löschen von Objekten kann aber verdammt schnell auf solche zugreifen.

Stell dir lieber die Frage wofür die Liste in deiner Engine sein soll. Z.B. für Partikelsysteme ist besser auf pooling und einen array zu bauen während du z.B. bei einer Liste mit konstanter Größe eher auf eine tatsächliche List-Implementation zurückgreifst.

Ansonsten, what Mog said :D

@Ineluki: Danke, ich werds dann mal mit Lists probieren.

@Mog: Mir ist schon klar dass es hier keine perfekte Lösung gibt. Ich kann auch nicht wirklich abschätzen welches der Vorhaben am wichtigsten ist. Daher wollte ich nur einen Rat, was ich denn am besten nutzen sollte. :P

@R.D.: Es geht bei der Liste eigentlich um die Spielobjekte. Die müssen aber auch sehr oft neu geordnet werden. Zudem werden Objekte außerhalb der Bildschirmgrenzen aussortiert, was dann wohl die langsamere Zugriffszeit etwas in den Hintergrund rücken kann.
Das Ganze soll auch auf älteren Rechnern, als auch auf mobilen Konsolen laufen(Stichwort OpenSource Handhelds), daher ist mir die Geschwindigkeit schon sehr wichtig.

Sortieren ist ein Thema für sich. Es ist z.B. abhängig davon was das Spiel vom Typ her ist. Für ein Top-Down-Game etwas ist ein Y-Sort ganz cool. Das muss dann aber auch nur gemacht werden wenn sich ein Entity in Y Richtung verschiebt. Vergiss so was bloß nicht. Was du auch probieren kannst ist den Z-Buffer zu nehmen. Für Sprite-Sorting ist so was Klasse (wenn du die Möglichkeit hast einen solchen Buffer zu nutzen). Das Problem hierbei ist das Blending nicht mehr funktioniert (Speziell bei OpenGL ist das sehr ärgerlich).
Ich würde außerdem NIE, ich meine wirklich NIE Entities außerhalb des Bildschirms aussortieren. Stattdessen würde ich einen check machen und sie nicht mehr rendern. Entitites außerhalb des Bildschirmrandes müssen ja trotzdem ge-updated werden. Es sei denn du willst so ein Mega Man-Verhalten. Dort machen die Entities ja erst etwas wenn sie auf den Bildschirm sichtbar werden. Oder was genau meinst du damit?
Und mach dir nicht allzugroße Sorgen um ältere Rechner. Ganz ehrlich, 100 Entites... pff Bubblesort ftw! Für alles andere würde ich eh Radix-Sort nehmen. Das ist wirklich wichtig. Also wäre es vllt ganz wichtig darüber nachzudenken ob es sich überhaup lohnt eine List zu nehmen weil man viel ordnen muss obwohl vllt maximal 100 Entities in einem "Level" oder so sind (PartikelSysteme mal ausgeschlossen).

Listen lassen sich sogar verhaeltnismaessig gut sortieren. Kommt natuerlich auch auf den Algorithmus an.

Ansonsten koenntest du natuerlich auch mit einem Array von Pointern arbeiten. Du alloziierst genug Speicher um alle Pointer zu halten, die du jemals brauchen wirst und initialisierst das Array dann mit NULL.
Damit hast du Zugriff auf einen Index in O(1) (Constant Time), Anfuegen ans Ende in O(1), falls du die Anzahl belegter Indizes speicherst, sowie Vertauschen von zwei Indizes in O(1).
Sogar das Loeschen eines Index kannst du in O(1) hinkriegen, wenn du den Pointer des Index auf NULL setzt und den Index selbst in einer Queue oder einem Stack zwischenspeicherst, damit du in O(1) Elemente hinzufuegen kannst, falls dir der konkrete Index dabei egal ist. Allerdings frisst diese Methode relativ viel Speicher (du hast ein Array aller maximal moeglichen Eintraege und noch eine Liste mit vakanten Eintraegen), den du allerdings ggf durch Anwenden getimeter Blockinkement/-dekrement Alloziierungen/Freigaben etwas reduzieren kannst.

Der ganze Aufwand lohnt allerdings wohl nur dann, wenn der Zugriff auf deine "Liste" wirklich DER Zeitkritische Faktor ist und du wirklich ALLE obigen Operationen in moeglichst O(1) haben musst. Wahrscheinlicher ist es wohl, dass dein Algorithmus suboptimal ist. Was nuetzt dir ein Zugriff in O(1) statt O(n) auf deine Liste, wenn du (z.B. zum Sortieren) einen Algorithmus verwendest, der mit O(n^2) (z.B. Bubblesort) statt O(n log(n)) (Quicksort) bei sehr grossem n arbeitet ... richtig: gar nichts.

Ich denke, was du suchst, sind Octrees, KD-Trees oder BSP-Trees. Das ist so, was man in der Regel für sowas verwendet.

Wenn es um einen Container von Spiel-Objekten geht habe ich der Regel mit 3 Vektoren gelöst:
1. Vektor: Speichert die eigentlichen Spielobjekte (bzw. Pointer).
Besonderheit: Wenn ein Objekt aus dem Vektore gelöscht wird, wird der jeweilige Eintrag auf null gesetzt. Damit bleiben die Indices für die Spielobjekte für die gesamte Lebenszeit erhalten. Ergo ID = Index in diesem Vektor.
2. Vektor: Speichert eine Liste von freien Indices vom 1. Vektor. Die Indicies werden beim entfernen drauf gepuscht und beim einfügen abgepopt (damn, wie schreibt man das auf Deutsch?). Damit wird sicher gestellt, dass der 1. Vektor beim wiederholten entfernen und einfügen nicht beliebig anwächst.
3. Vektor: Ein Vektor mit Indicies die die Renderreihenfolge der Objekte im 1. Vektor angibt. An der Stelle kannst du auch stattdessen eine KD-Tree oder eine beliebige andere Struktur aufbauen. Wichtig ist jedenfalls, dass die Struktur die Objekte selber nicht enthält sondern diese nur per Index im 1. Vektor referenziert.

So ein System habe ich schon in zwei Spielengines verwendet. Außerdem haben wir die Technik für einen Software-Raytracer verwendet bei uns an der Uni. Also das sollte so schon performant sein.
Ich denke mal wenn dir Performance wichtig ist solltest du versuchen Vektoren zu verwenden, einfach wegen dem lokalem Speicherzugriff.

Zugriff auf Spielobjekte sollte definitiv in O(1) laufen (per Id / Index), weil sowas bei der Kollisions-Engine und ähnlichen Berechnung massig verwendet wird.

Gruß

Felix

Interessanter Ansatz, Lachsen. Aber den zweiten Vektor brauchst du gar nicht. Es reicht ein einziger Integer, der den ersten Index auf eine freie Stelle speichert. Die freien Stellen speichern dann, statt Zeiger auf Spielobjekte, Indizes der jeweils nächsten freien Stelle.

Zitat:

---

Zitat von Kyuu

Interessanter Ansatz, Lachsen. Aber den zweiten Vektor brauchst du gar nicht. Es reicht ein einziger Integer, der den ersten Index auf eine freie Stelle speichert. Die freien Stellen speichern dann, statt Zeiger auf Spielobjekte, Indizes der jeweils nächsten freien Stelle.

---

Gefährlich, wenn man über den ersten Vector mal eben drüber iteriert.

Der Sinn ist doch gerade, dass man nicht iterieren braucht, zumindest nicht wenn man nach freien Stellen sucht. Das ist eine Strategie für memory pools und nichts anderes ist sein erster Vektor.

Richtig, aber in vielen Fällen will man das. Gibt ja immer wieder Funktionen, die man tatsächlich auf alle Objekte auf einmal anweden will.

Zitat:

---

Zitat von Lachsen

Wenn es um einen Container von Spiel-Objekten geht habe ich der Regel mit 3 Vektoren gelöst:
1. Vektor: Speichert die eigentlichen Spielobjekte (bzw. Pointer).
Besonderheit: Wenn ein Objekt aus dem Vektore gelöscht wird, wird der jeweilige Eintrag auf null gesetzt. Damit bleiben die Indices für die Spielobjekte für die gesamte Lebenszeit erhalten. Ergo ID = Index in diesem Vektor.
2. Vektor: Speichert eine Liste von freien Indices vom 1. Vektor. Die Indicies werden beim entfernen drauf gepuscht und beim einfügen abgepopt (damn, wie schreibt man das auf Deutsch?). Damit wird sicher gestellt, dass der 1. Vektor beim wiederholten entfernen und einfügen nicht beliebig anwächst.
3. Vektor: Ein Vektor mit Indicies die die Renderreihenfolge der Objekte im 1. Vektor angibt. An der Stelle kannst du auch stattdessen eine KD-Tree oder eine beliebige andere Struktur aufbauen. Wichtig ist jedenfalls, dass die Struktur die Objekte selber nicht enthält sondern diese nur per Index im 1. Vektor referenziert.

So ein System habe ich schon in zwei Spielengines verwendet. Außerdem haben wir die Technik für einen Software-Raytracer verwendet bei uns an der Uni. Also das sollte so schon performant sein.
Ich denke mal wenn dir Performance wichtig ist solltest du versuchen Vektoren zu verwenden, einfach wegen dem lokalem Speicherzugriff.

Zugriff auf Spielobjekte sollte definitiv in O(1) laufen (per Id / Index), weil sowas bei der Kollisions-Engine und ähnlichen Berechnung massig verwendet wird.

Gruß

Felix

---

Ersetze in 1. Vector durch Array und lass den Zeichenreihenfolgenvektor aus 3. weg, und du hast genau das, was ich oben vorgeschlagen habe. ^_^
Das einzige Problem am Vector ist ja, dass der iirc keine Inserts in Constant Time (aka O(1)) machen kann, was elvissteinjr ja wollte.

Ich hab grade auch nochmal drüber nachgedacht. Wozu sollen die Vectors 1 und 2 gut sein? Effektiv sind die auch nur ein sehr primitiver Memory Manager, da ja - zumindest soweit ich das sehe - eine 1:1 Beziehung zwischen dem Index in Vector 1 und der Adresse im RAM besteht. Daher kannst du die beiden auch einfach weglassen und direkt im dritten Vector mit Pointern arbeiten.

@Kyuu:
Ich denke mal das Iterieren durch Spielobjekte ist sehr wichtig, z.B. um die den Status aller Spielobjekte zu aktualiseren.
Mir persoenlich waeren solche index Spielereien auch zu riskant. Vielleicht ist es minimal schneller und spart dir etwas Speicher, dafuer ist der Code verwirrender und Fehleranfaelliger.

@Ineluki:
Das Einfuegen in einem Vector mit push_back hat eine amortisierte Laufzeit von O(1). Gerade in meinem Fall werden elemente ja oft geloescht und neu eingefuegt, weshalb der Vektor ab einem bestimmten Zeitpunkt nicht mehr reallokiert werden muss. Ansonsten ja... du hattest praktisch den selben Ansatz. Ich war nur zu Faul zum lesen. ^^"

@DFYX
Prinzipiell kann man nur die optimierte Struktur fuers Rendern beibehalten und den Rest mit Pointern regeln. Daraus folgt dann auch, dass Render unabhaengige Prozesse, zum Beispiel das aktualisieren der Spielobjekte ueber die optimierte Struktur laufen (wie will mann sonst ueber die Spielobjekte iterieren?). Dazu kommt auch, das man die optimierte Struktur aktualiseren koennen muss, ohne auf eine andere Struktur zurueck zu greifen. Bei einer sortieren Liste ist das machbar, bei einem KD tree ist das schon schwerer. Und schliesslich muessen alle Referencen unterhalb von Objekten mit Pointern geloest werden, da schneller Zugriff ueber index mit der optimierten Struktur alleine nicht geht.
Ich bevorzuge an der Stelle indizes anstelle von Pointern. Bei indizes kannst du bei geloeschten Spielobjekten einfach null zurueck geben - bei Pointern hast du da ein Problem. (es sei denn du verwendest smart pointers... da hast du dann wieder andere Probleme.)

Also ja, im Prinzip ist so eine Struktur nicht notwendig ums zum Laufen zu bekommen, aber auf langer sich zahlt es sich schon aus, finde ich.

Zitat:

---

Zitat von Lachsen

@Kyuu:
Ich denke mal das Iterieren durch Spielobjekte ist sehr wichtig, z.B. um die den Status aller Spielobjekte zu aktualiseren.
Mir persoenlich waeren solche index Spielereien auch zu riskant. Vielleicht ist es minimal schneller und spart dir etwas Speicher, dafuer ist der Code verwirrender und Fehleranfaelliger.

---

Das ist keine Spielerei, sondern eine bewährte Strategie und wird zum Beispiel so in der Referenzbibliothek Loki implementiert.

Dass du über die Spielobjekte im ersten Vektor iterieren willst, kann ich irgendwie nicht ganz nachvollziehen, da du immer auch über alle nicht belegten Stellen iterieren würdest.

Zitat:

---

Zitat von Lachsen

Bei indizes kannst du bei geloeschten Spielobjekten einfach null zurueck geben - bei Pointern hast du da ein Problem. (es sei denn du verwendest smart pointers... da hast du dann wieder andere Probleme.)

---

Verwende weak references.

Zitat:

---

Zitat von Kyuu

Das ist keine Spielerei, sondern eine bewährte Strategie und wird zum Beispiel so in der Referenzbibliothek Loki implementiert.

---

Joa, ok. Wenn es um maximale Performance geht ist im endeffekt alles erlaubt. In so einem Fall muss man sich dennoch recht stark auf die implementieren der Struktur an sich konzentieren, weil man bei solchen Optimierungen doch auch schnell Fehler machen kann. Das ist genauso als ob man std::vector selbst implementiert. Da gibt es genug Kleinigkeiten, die man falsch machen kann. Aus dem Grund finde ich eine einfache Kombination aus Standard Containern die besser Wahl um auf der sicheren Seite zu sein.
Aber ja, "Spielereien" ist der falsche Begriff an dieser Stelle.

Zitat:

---

Dass du über die Spielobjekte im ersten Vektor iterieren willst, kann ich irgendwie nicht ganz nachvollziehen, da du immer auch über alle nicht belegten Stellen iterieren würdest.

---

Den overhead hast du als trade-off für schnelles einfügen und entfernen von Einträgen. Iterieren musst du auf jedenfall. Hm.. man kann auch über die beschleunigte Struktur iterieren, das stimmt.

Zitat:

---

Verwende weak references.

---

In C/C++? Soweit ich weiß gibt es dort keine einfache Implementierung dafür. In std sicher nicht, wahrscheinlich in boost. Ich habe weak pointers aber in der Praxis noch nicht erlebt in CPP und das hat wahrscheinlich seinen Grund...

Zitat:

---

Zitat von Lachsen

In C/C++? Soweit ich weiß gibt es dort keine einfache Implementierung dafür. In std sicher nicht, wahrscheinlich in boost. Ich habe weak pointers aber in der Praxis noch nicht erlebt in CPP und das hat wahrscheinlich seinen Grund...

---

In boost und seit C++11 auch in std.

Zitat:

---

Zitat von Lachsen

Ich habe weak pointers aber in der Praxis noch nicht erlebt in CPP und das hat wahrscheinlich seinen Grund...

---

Ja, den Grund, dass du sie noch nicht in C++ (bewusst) erlebt hast. ;)

Weak references sind sehr wichtig und überall dort wo reference cycles auftreten können, unverzichtbar. Im Prinzip stellen Indizes in deinen ersten Vektor auch (naive) weak references dar.

Zitat:

---

Zitat von Kyuu

Ja, den Grund, dass du sie noch nicht in C++ (bewusst) erlebt hast. ;)

Weak references sind sehr wichtig und überall dort wo reference cycles auftreten können, unverzichtbar. Im Prinzip stellen Indizes in deinen ersten Vektor auch (naive) weak references dar.

---

Ich habe nochmal nachgeschlagen und der Grund warum bei uns weak pointer noch nicht zum Einsatz kamen ist der, dass sie auf shared_ptr basieren, die wiederum einen overhead gegenüber normalen pointern verursachen, da der object counter dynamisch zusätzlich zum objekt allokiert wird. Wir verwenden hauptsächlich intrusive_ptr und da funktionieren die weak_ptr aus boost und std nicht, wenn ich das richtig verstehe.

Man braucht nicht weak pointer um reference cycles aufzuheben. Raw pointer und etwas vorsicht tun es auch. Ich schätze mal shared und weak ptr sind die sichere Methode, wenn man den Overhead in Kauf nehmen kann.

Zitat:

---

Zitat von Lachsen

Ich habe nochmal nachgeschlagen und der Grund warum bei uns weak pointer noch nicht zum Einsatz kamen ist der, dass sie auf shared_ptr basieren, die wiederum einen overhead gegenüber normalen pointern verursachen, da der object counter dynamisch zusätzlich zum objekt allokiert wird. Wir verwenden hauptsächlich intrusive_ptr [...]

---

Inwiefern spielt der overhead beim Allozieren des reference counters für euch eine Rolle? Solange ihr nicht in einer kritischen Schleife die Objekte immer wieder erzeugt, ist dieser zusätzliche overhead vernachlässigbar, da mit ihm nur bei der Objekterzeugung zu rechnen ist. Intrusive reference counting aus dem Grund zu wählen, weil es den overhead beim Allozieren des reference counters vermeidet ist fragwürdig, ich hoffe das ist nur deine Interpretation. Intrusive reference counting ist praktisch etwa wenn reference counting über Programm/Bibliothek-Grenzen hinweg funktionieren soll, oder wenn die Objekte in memory pools alloziert werden.

Zitat:

---

Zitat von Lachsen

Man braucht nicht weak pointer um reference cycles aufzuheben. Raw pointer und etwas vorsicht tun es auch.

---

Ich kann mir Situationen vorstellen, in denen raw pointer nicht reichen würden.

----------------------

Übrigens fällt mir gerade ein Problem bei deiner Struktur weiter oben ein. Dein Argument war, dass du null zurückgeben kannst, wenn ein Objekt gelöscht wurde. Dem entnehme ich, dass bei dir Situationen eintreten können, in denen Objekte referenziert werden, die bereits gelöscht wurden. Was nun, wenn ein Objekt gelöscht wird und die Stelle im Vektor durch ein neues ersetzt wird, noch bevor der Code, der das gelöschte Objekt referenziert, realisiert, dass das referenzierte Objekt nicht mehr existiert?

Zitat:

---

Zitat von Kyuu

Inwiefern spielt der overhead beim Allozieren des reference counters für euch eine Rolle? Solange ihr nicht in einer kritischen Schleife die Objekte immer wieder erzeugt, ist dieser zusätzliche overhead vernachlässigbar, da mit ihm nur bei der Objekterzeugung zu rechnen ist. Intrusive reference counting aus dem Grund zu wählen, weil es den overhead beim Allozieren des reference counters vermeidet ist fragwürdig, ich hoffe das ist nur deine Interpretation. Intrusive reference counting ist praktisch etwa wenn reference counting über Programm/Bibliothek-Grenzen hinweg funktionieren soll, oder wenn die Objekte in memory pools alloziert werden.

---

Ich empfinde die Optimierung durch das auslassen von shared_ptr ähnlich fragwürdig was das weg-optimieren des 2. Vektors der auf freie Felder speichert. Allokation ist eine teure operation, das könnte einen Unterschied machen wenn viele Objekte neu erstellt und entfernt werden (bei partikeln etwa?). Dazu kommt auch, dass dein shared_ptr zwei sachen referenziert (counter und pointer) und damit doppelt so groß ist. Wenn du also über einen Array mit shared_pointern itereierst kannst du genauso gut über eine Vektor doppelter größe mit raw-pointer iterieren. (vergleichbar mit dem Overhead, wenn man bei meiner Struktur über 0 pointer iteriert)

Im übrigen ist fast alles was wir hier diskutieren premature optimization. Just sayin'.

Zitat:

---

Ich kann mir Situationen vorstellen, in denen raw pointer nicht reichen würden.

---

Care to share? Ich kann mir keine solche Situation vorstellen, die man nicht genauso gut mit einer Routine im Destuktor lösen kann.

Zitat:

---

Übrigens fällt mir gerade ein Problem bei deiner Struktur weiter oben ein. Dein Argument war, dass du null zurückgeben kannst, wenn ein Objekt gelöscht wurde. Dem entnehme ich, dass bei dir Situationen eintreten können, in denen Objekte referenziert werden, die bereits gelöscht wurden. Was nun, wenn ein Objekt gelöscht wird und die Stelle im Vektor durch ein neues ersetzt wird, noch bevor der Code, der das gelöschte Objekt referenziert, realisiert, dass das referenzierte Objekt nicht mehr existiert?

---

Da hast du recht. In dem Fall verhält sich das System fehlerhaft.
Also ich vermute mal das Argument mit sicheren zugriff per id zieht nicht wirklich.
Es ist also lediglich eine Struktur in der man schnell einfügen und entfernen kann, direkten zugriff hat und bei der auch iteration funktioniert. (mit einem gewissen overhead)
Naja, es funktioniert für meine Anwendungen gut genug.

Zitat:

---

Zitat von Lachsen

Ich empfinde die Optimierung durch das auslassen von shared_ptr ähnlich fragwürdig was das weg-optimieren des 2. Vektors der auf freie Felder speichert. Allokation ist eine teure operation, das könnte einen Unterschied machen wenn viele Objekte neu erstellt und entfernt werden (bei partikeln etwa?).

---

Könnte, würde, müsste... Teste. Und wenn es sich herausstellt, dass die Allokation der Flaschenhals ist, würden sich memory pools als sinnvolle Lösung anbieten (auch für den reference counter).

Gerade bei Partikeln (und ähnlich kleinen Objekten) bieten sich memory pools an und um ehrlich zu sein, habe ich noch nie gesehen, dass Partikel einzeln auf dem Heap alloziert werden (obwohl es durchaus gute Gründe geben könnte, dies zu tun).

Aber ich gebe zu, mein Vorschlag den zweiten Vektor wegzuoptimieren ist nicht gerade einleuchtend. Aber um einen Performance-/Speichervorteil ging es mir dabei weniger, das hast du dann selbst hineininterpretiert. Ich habe gesehen, dass deine Sruktur Ähnlichkeiten mit einem memory pool hat und habe einen Ansatz vorgeschlagen, wie man den zweiten Vektor eliminieren könnte. Ob es in deinem Anwendungsfall sinnvoll wäre, musst du dann selbst entscheiden.

Zitat:

---

Zitat von Lachsen

Dazu kommt auch, dass dein shared_ptr zwei sachen referenziert (counter und pointer) und damit doppelt so groß ist. Wenn du also über einen Array mit shared_pointern itereierst kannst du genauso gut über eine Vektor doppelter größe mit raw-pointer iterieren. (vergleichbar mit dem Overhead, wenn man bei meiner Struktur über 0 pointer iteriert)

---

Den Gedankengang kann nicht nicht ganz nachvollziehen. Willst du damit sagen, dass die Zeit, um über 50 acht Byte große Elemente zu iterieren, dieselbe ist, wie über 100 vier Byte große Elemente? Das Einzige, was hier wahrscheinlich gleich wäre, wäre das Cacheverhalten.

Übrigens könnte man, statt nur den reference counter zu allozieren, eine Struktur allozieren, die sowohl den reference counter, als auch den Objektzeiger enthält, womit der smart pointer nur noch die Größe eines Zeigers hätte. Ob das sinnvoll wäre, muss man wieder im Anwendungsfall genauer betrachten.

Zitat:

---

Zitat von Lachsen

Im übrigen ist fast alles was wir hier diskutieren premature optimization. Just sayin'.

---

I beg to differ. (Hey, ich kann auch ein bisschen Englisch. ;)) Ich halte es nicht für premature optimization, sich ein paar Gedanken über die Implementierungsmöglichkeiten zu machen. Eine naive Implementierung könnte sich im Nachhinein als mindestens genauso problematisch erweisen, als eine mikrooptimierte, verworrene Implementierung mit einem effektiven Vorteil von 0.0001%. Dass die Leser hier sich ihre eigenen Gedanken machen und vor dem Implementieren abwägen, soviel möchte ich ihnen zutrauen.

Zitat:

---

Zitat von Lachsen

Care to share? Ich kann mir keine solche Situation vorstellen, die man nicht genauso gut mit einer Routine im Destuktor lösen kann.

---

Zwei Objekte, A und B, beide reference counted und beide besitzen auf das jeweils andere Objekt eine Referenz. Um den reference cycle aufzuheben, machen wir As Zeiger auf B zu einem raw pointer. Wenn nun alle Referenzen auf B erlöschen, wird B gelöscht und As raw pointer wird zu einem dangling pointer.

Und As Zeiger auf B aus Bs Destruktor zu manipulieren werde ich nicht akzeptieren. :p