Gibts sowas schon (Liste mit rel. schnellem op[] ) ??
-
Das bringt aber nur was, wenn die Anzahl der Elemente nahezu statisch ist. Andernfalls ziehen insert/delete die Performance in den Keller. In diesem Fall bietet sich aber wieder ein Vector an.
-
aber wenn man nur selten was hinzufügt, bzw wenn dann nur an bestimmten stellen und dann ganz oft hintereinander, ist das besser.
-
Maxi schrieb:
aber wenn man nur selten was hinzufügt, bzw wenn dann nur an bestimmten stellen und dann ganz oft hintereinander, ist das besser.
Wenn du wenig hinzufügst und löscht, dann ist vector einfach das beste
btw: hast du dir schonmal deque angesehen? uU ist es das was du willst.
Und es gibt ja immernoch die Möglichkeit nur Zeiger in dem vector zu speichern - so sind die copy kosten extrem gering.
-
Wenn man nur selten etwas hinzufügt, kann die Liste ihren Vorteil gar nicht richtig ausspielen.
Wenn du viele Elemente an derselben Stelle mitten in einem Vector eingüfen willst, könntest du sie auch erst alle hintereinander in einen zweiten Vector einfügen und dann auf einen Rutsch alle gleichzeitig in den ersten Vector einfügen. Dann fällt das ständige Umkopieren weg.
-
Deine Liste macht keinen Sinn, wenn insert und erase nicht performant sind. Dann hast du die Vorteile von verketteten Listen verspielt.
-
Gibts nicht weil, geht nicht.
Die Vorteil des Vector ist der schnelle der wahlfreie Zugriff auf seine Elemente. Dies wird dadurch ermöglicht das die Elemente physikalisch in einem zusammenhängendem Speciherbereich verwaltet werden. Wenn du mitten hinein was einfügen willst, muss daher ein grosser Teil der anderen Elemente ebenfalls bewegt werden, was eben nicht so performant ist.
Der Vorteil einer Map ist das effiziente Einfügen und Löschen von Elementen an jeder Stelle der Struktur. Das wird wird durch Verpointerung der Elemente ermöglicht physikalisch bilden sie keinen zusammenhängenden Speicherblock. Dadurch ist jedoch der Direktzugriff auf beliebige Elemente nicht mehr so performant, falls überhaupt erlaubt.
In diesem Sinne ist es daher die Aufgabe des Entwicklers von Fall zu Fall zu entscheiden welches die für sein Problem beste Lösungsmöglichkeit darstellt.
Du kannst dir natürlich für spezielle Probleme deine persönlich Lösung zusammenstellen. Das mag vielleicht eine Mischung aus beiden Methoden sein. Du solltest aber auch dann übelegen ob der zusätzliche Entwicklungs-/Testaufwand durch das Ergebnis gerechtfertigt wird.mfg JJ
-
Es gibt ja auch noch Hashs.
-
Die Hashs die ich kenne (ist ja schliesslich kein Standard
) haben keinen wahlfreien Zugriff 
mfg JJ
-
Wie man's nimmt. Ich mein, man kann ja einfach schreiben:
Hashmap<int, Foo> hash; hash[22] = Foo(...); ... cout << hash[22];Ist doch zeimlich wahlfrei. Zuminest geht sowas bei meinen Hashs.
-
Guter Kunstgriff, weiss aber nicht ob das den "Anforderungen" entspricht.
Wenn du ein Element rauslöscht hast du immerhin keinen fortlaufenden Index mehr. :pmfg JJ
-
es gibt ne möglichkeit, die einen schnellen(aber nich standard konformen) operator[] ermöglicht.
teile die liste in x teillisten auf,merk dir die größe jeder liste und wenn dann zb list[123] kommt, gehst du zur ersten teilliste, bei der die größe+die größe der vorgänger teillisten größer=123 ist(nicht gleich, das wär nämlich das 1.element der nächsten teilliste).
und dann lieferst du das xte element der teilliste zurück, wobei x=suchzahl-größe der vorgängerlisten.hoffe, das is so halbwegs klar geworden, was ich sagen wollte(bin müde, da geht sowas nichmehr so gut^^)
-
otze schrieb:
es gibt ne möglichkeit, die einen schnellen(aber nich standard konformen) operator[] ermöglicht.
Das geht auf kosten des einfügens und löschens. das kann bei einer großen liste ziemlich lahm werden... somit bringt sich die liste nicht mehr.
-
Maxi schrieb:
Gibt es schon eine Datenstruktur, die die Vorteile von vector und list vereint, also schneller direktzugriff und schnelles löschen eines elementes an einer bestimmten stelle ohne umkopieren der anderen daten?
ja. vector.
schneller zugriffg ist eh da. und schnelles löschen macht man, indem man das zu löschende elem mit dem letzten elem tausch und dann das letzte löscht.oder willste die reihenfolge der elems sogar gleich halten? dann müßtest du in der nähe vom suchwort "rope" daheim sein.
-
Shade Of Mine schrieb:
otze schrieb:
es gibt ne möglichkeit, die einen schnellen(aber nich standard konformen) operator[] ermöglicht.
Das geht auf kosten des einfügens und löschens. das kann bei einer großen liste ziemlich lahm werden... somit bringt sich die liste nicht mehr.
nix da,einfügen am anfang/ende geht genauso shcnell wie bei ner normalen liste, einfügen in der mitte...eigentlich auch
ok, man muss von der konstanten größe der teillisten weggehen,bzw bei zu großen teillisten noch eine interne unterteilung benutzen,aber das is nich wirklich das problem(ich hab mal ne test implementation davon gemacht, die ergebnisse waren ziemlich gut, dafür dass ich eigentlich keine ahnung vom programmeiren hab)