Objekt Baumstruktur frage?
-
Was macht der Vector, wenn der reservierte Speicherplatz zu klein ist, um ein neues Element anzufordern (wir wissen natürlich, dass ein Vector intern als zusammenhängendes Stück Speicher, spricht Array, implementiert ist)? Richtig, er muss neuen Speicher anfordern und die bestehenden Objekte umkopieren.
Umsortieren ist evtl. der falsche Ausdruck, sonst ist der Einwand vollkommen ok.
-
ok danke.. das hab ich verstanden.. dann wäre eine liste besser.. aber die ist halt 5 mal langsamer..
hab mal gesteste bei 100000 int werten jeweils anlegen in einem vector und liste.
vector 500ms
list 3000ms
-
BorisDieKlinge schrieb:
ok danke.. das hab ich verstanden.. dann wäre eine liste besser.. aber die ist halt 5 mal langsamer..
hab mal gesteste bei 100000 int werten jeweils anlegen in einem vector und liste.
vector 500ms
list 3000ms6-mal langsamer ;o)
du koenntest aber auch anstatt einen pointer, den index im vector speichern. dann waere es egal wenn der vector mal den speicher wechselt
Meep Meep
-
Meep Meep schrieb:
du koenntest aber auch anstatt einen pointer, den index im vector speichern. dann waere es egal wenn der vector mal den speicher wechselt
Das klappt aber vermutlich nur, wenn er einen Super-Vector hat, der alle Baumknoten speichert.
@Boris: Vielleicht ist ein deque<> für dich geeignet - afair bleiben dessen Elemente an seiner Position, solange nichts im Inneren der Struktur dazwischengeschoben wird.
-
jepp ich bin grad am deque vs. list testen..
deque ist langsamer beim travestieren ca. 20%
aber den untschied zwischen deque und list hab ich noch nich verstanden..
-
Deque alias "double ended Queue" ist eine eher Array-artige Struktur, die im Gegensatz zum vector in beide Richtungen wachsen kann. Du kannst ebenfalls recht schnell über den Index zugreifen (wie beim vector) und du kannst recht schnell am Anfang und am Ende neue Werte einfügen und entfernen (beim vector nur am Ende, bei der list überall). Intern sieht die Struktur der deque etwas komplizierter aus - idR dürfte sie eine zweischichtige Sammlung von Speicherblöcken verwenden.
-
list: [payload|*next] [payload|*next] [payload|*next] +---^ +---^ vector: [#|payload] [#|payload] [#|payload] deque: [#|payload] [#|payload] [#|payload] ^ ^ | | *first | *last -------------------+so ungefähr kann man sich das vorstellen
-
ist so deque mit einer doppeltverketteten liste vergleichbar?
-
BorisDieKlinge schrieb:
ist so deque mit einer doppeltverketteten liste vergleichbar?
nein, deque behandelt nur einfüge operationen an den anfang (push_front) und das ende (push_back) anders als vector. eine doppeltverkettete liste würde sich für jedes einzelne element den vorgänger und nachfolger merken.
-
Wie ich schon sagte, der Aufbau der deque ist recht komplex - meistens sieht das eher so aus:
[*block1|*block2|*block3|...] | | +---------------------------------------------+ | +----------------------+ | v| v v [payload][payload][payload]... [payload][payload][payload]... [payload][payload][payload]... +----------------^ [*first][*last]------------------>(list<> ist normalerweise eine doppelt verkettete Liste)