container
-
Direktzugriff bieten vector<> und deque<> in konstanter Zeit, alle anderen Container in linaerer Zeit (über advance()), insert()/erase() funktionieren bei list<> in konstanter Zeit, bei vector<> und deque<> in linearer Zeit. Beides gemeinsam wirst du bei keinem Container finden (und ich kenne auch kein Speicherkonzept, das beides effektiv kann), also mußt du schon einen Kompromiss eingehen.
-
Also, an dieser stelle würde ich gerne ein bisschen werbung für meine idee von einem container machen (hock schon seit paar tagen dran, wills möglichst STL-kompatibel machen
) vielleicht kann es ja jemand außer mir gut gebrauchen... (schön wärs 
)Ich bastle gerade an einem container, der gewissermaßen beides kann, und zwar habe ich diesen container "indexed_array" getauft:
Eigenschaften: -reihenfolge der elemente muss vollkommen irrelevant sein -erase in konstaner zeit, an beliebiger stelle -anhängen der elemente in konstanter zeit. Wohin das element geschrieben wird, muss irrelevant sein, allerdings liefert die insert() funktion einen index, über den später im prinzip der wahlfreie zugriff möglich ist -es wird gewährleistet, dass die elemente niemals unaugefordert ihren index verändern => in der sequenz entstehen "löcher" -wenn man über einen ungültigen index auf ein loch zugreift, ist das verhalten undefiniert -iterator FwdIt, kein random access über iterator -begin() end() wie immer da ++ in konstanter zeit möglich (große "löcher" werden übersprungen) -- += -= nicht vorhanden * -> wie immer vorhanden [] und at() in konstanter zeit [b]über einen gültigen index[/b] möglich. Dabei kann das 20. tatsächlich existierende element einen index=139 haben. Das ist der preis für das erase() in konstanter zeit (->löcher).Das alles kann zunächst "wenig sinnvoll" bis "total bescheuert" erscheinen, allerdings sah ich keine andere lösungsansätze beim folgenden problem aus dem gebiet der computergrafik
:Mein problem beim bau eines model-editors:
-ein modell besteht aus vielen vertices. DirectX verlangt
random access auf den vertex-array
-reihenfolge und "löcher" sind egal, weil man erst durch
indizieren beschreibt, welche vertizes zu dreiecken
verbunden werden.
-allerdings muss der benutzer einen überflüssigen dreieck
jederzeit löschen können => erase() muss in konstanter
zeit erfolgen, weil es ansonsten bei größeren modellen
unzumutbar wird, wenn man beim löschen jedes mal 2-3
sekunden warten muss, bis 20000 vertices kopiert werden...was meint ihr dazu? fällt euch evtl. eine bessere lösung ein? meint ihr, dass man es sonst irgendwo gut einsetzen könnte? ":):):)" wärst du möglicherweise mit so einer lösung zufrieden, hast du vielleicht ein ähnliches problem?
wäre einfach mal interesant zu hören, was ihr von soeinem container halten würdet...
-
Eine nette Idee, aber ich würde dabei sogar den -- Operator (in konstanter Zeit) zur Verfügung stellen. Hast du auch schon einige Ansätze bei der Umsetzung dieser Idee gefunden?
(falls nein - ich würde eine Mischung aus vector (für die eigentlichen Daten und die Indexzugriffe) und verketteter Liste (jedes Element hat einen Index auf das nächste/vorige gültige Element) vorschlagen)
-
also die idee hört sich relativ gut an...
Nur ein Problem seh ich noch:
Wo speicher ich die zurückgegebenen indizes? Die unterschiede beim löschen und einfügen usw. machen sich ja erst ab vielen Daten wirklich bemerkbar. Also wird man viele indizes zu verwalten haben. diese werden zwangsläufig wieder in einem container gespeichert werden müssen, (also vom benutzer) oder irre ihc mich da?
-
ja, ich hab schon ein paar richtig konkrete ansätze
[muss leider sagen, dass es mit BidIt in meinem ansatz nicht in konstanter zeit mit dem -- operator klappt. Bzw, dann bräuchte man n bissl mehr speicherplatz, ich halte es jedoch für nicht sonderlich sinvoll (einfach verkettet reicht schon: die reihenfolge ist ja irrelevant! ) ]Aber ich will es erst dann "publizieren" wenn es wirklich fertig ist, und im moment bin ich dummerweise gezwungen eine kleine pause einzulegen
(hab ebn irgendwie chaotisch mein studium begonnen, bin voll durcheinander und blick nirgendwo durch und raff nicht was abgeht und und und ...aaaah!!! 
=> totaler ausnahmezustand )Ich hoffe, dass ich am nächsten wochenende damit fortfahren kann: an diesem wochenende muss ich leider n bissl was für die uni nacharbeiten
Aber danach wäre es wirklich schön, wenn sich jemand die mühe geben würde, sich die umsetzung anzuschauen, auf ein paar tipps und verbesserungsvorschläge würde ich mich wirklich freuen.
Aber wie gesagt... ich werde damit erst dann fortfahren, wenn das mit der uni alles wieder einigermaßen routinemäßig läuft.
-
also die idee hört sich relativ gut an...
Nur ein Problem seh ich noch:
Wo speicher ich die zurückgegebenen indizes? Die unterschiede beim löschen und einfügen usw. machen sich ja erst ab vielen Daten wirklich bemerkbar. Also wird man viele indizes zu verwalten haben. diese werden zwangsläufig wieder in einem container gespeichert werden müssen, (also vom benutzer) oder irre ihc mich da?
das ist der grund, warum ich das ding möglichst STL-ähnlich bauen will.
ich habe nähmlich vor, die vertizes sowie die indizes in zwei container dieser "bauart" zu packen: eins für die indizes, zweites für die "dreiecke"/bzw indices. Die indices "zeigen" (nicht als zeiger, sondern als index) dann auf die vertices.
DirectX ist dann zufrieden, weil ja beides intern in arrays gelagert wird, und trotzdem passt das ding auf die eigene länge auf, und kümmert sich um das einfügen und das entfernen in konstanter zeit.
-
Andrey schrieb:
ja, ich hab schon ein paar richtig konkrete ansätze
[muss leider sagen, dass es mit BidIt in meinem ansatz nicht in konstanter zeit mit dem -- operator klappt. Bzw, dann bräuchte man n bissl mehr speicherplatz, ich halte es jedoch für nicht sonderlich sinvoll (einfach verkettet reicht schon: die reihenfolge ist ja irrelevant! ) ]Beim erase() mußt du aber auf jeden Fall den Vorgänger ermitteln können bzw. kennen (schon um seinen next-Zeiger umzubiegen). Also ist dieser zusätzlich nötige Speicher durchaus sinnvoll und notwendig (und mit der selben Methode, mit der erase() den Vorgänger bestimmt, kann auch op-- arbeiten).
@Maxi: Wenn es wirklich notwendig ist, die Indizes langfristig zu speichern, dann hast du sowieso die nötige Container-Struktur - in Andrey's Beispiel hast du z.B. einen indexed_array<vertex> für die Eckpunkte eines Objekts und verweist dann von der Dreiecksliste auf dessen Einträge (d.h. ein triangle (das z.B. in einem eigenen indexed_array stehen könnte) hat drei size_t-Werte, die den Index der drei Eckpunkte in diesem Array speichern).
-
CStoll schrieb:
@Maxi: Wenn es wirklich notwendig ist, die Indizes langfristig zu speichern, dann hast du sowieso die nötige Container-Struktur - in Andrey's Beispiel hast du z.B. einen indexed_array<vertex> für die Eckpunkte eines Objekts und verweist dann von der Dreiecksliste auf dessen Einträge (d.h. ein triangle (das z.B. in einem eigenen indexed_array stehen könnte) hat drei size_t-Werte, die den Index der drei Eckpunkte in diesem Array speichern).
exakt, du hast es
genau das hatte ich vor (siehe letzten beitrag )Was jetzt das "zeiger-umbiegen" beim erase angeht: ich habs etwas anders gelöst. Es werden intern keine zeiger gespeichert, stattdessen hat so ein indexed_array ding neben den eigentlichen daten ein zusätzliches size_t array, das benötigt wird, um die "lücken" zu markieren (null gibt es ja nicht in dem sinne wie bei Java) und zum anderen, um die breiten der lücken zu speichern und schnell zu überspringen. (geht aber nur in eine richtung)
Wenn ich fertig bin, werd ichs euch einfach mal zeigen, dann wird schon alles klar werden
-
Andrey schrieb:
CStoll schrieb:
@Maxi: Wenn es wirklich notwendig ist, die Indizes langfristig zu speichern, dann hast du sowieso die nötige Container-Struktur - in Andrey's Beispiel hast du z.B. einen indexed_array<vertex> für die Eckpunkte eines Objekts und verweist dann von der Dreiecksliste auf dessen Einträge (d.h. ein triangle (das z.B. in einem eigenen indexed_array stehen könnte) hat drei size_t-Werte, die den Index der drei Eckpunkte in diesem Array speichern).
exakt, du hast es
genau das hatte ich vor (siehe letzten beitrag )Ja, du darfst dir ein rotes X in den Kalendar schreiben - "ich war schneller als CStoll"
Was jetzt das "zeiger-umbiegen" beim erase angeht: ich habs etwas anders gelöst. Es werden intern keine zeiger gespeichert, stattdessen hat so ein indexed_array ding neben den eigentlichen daten ein zusätzliches size_t array, das benötigt wird, um die "lücken" zu markieren (null gibt es ja nicht in dem sinne wie bei Java) und zum anderen, um die breiten der lücken zu speichern und schnell zu überspringen. (geht aber nur in eine richtung)
Hm, das ist auch ein Ansatz. Aber das müsste ich wohl in Natura sehen, um den Ansatz verstehen zu können.
-
CStoll schrieb:
Ja, du darfst dir ein rotes X in den Kalendar schreiben - "ich war schneller als CStoll"
ne, das gilt ned, es ging ja auch schliesslich um ein problem, an dem ich schon seit ner längeren zeit hin und wieder tüftle
Hm, das ist auch ein Ansatz. Aber das müsste ich wohl in Natura sehen, um den Ansatz verstehen zu können.
wenn ichs mit der uni halbwegs auf die reihe bekomme, poste ich den ganzen header einfach hier rein