vector vs. eingebautes array
-
Ben04 schrieb:
23.2.4
A vector is a kind of sequence that supports random access iterators. In addition, it supports (amortized) constant time insert and erase operations at the end;.
Wenn du es schaffst eine Implementirung zu schreiben die (in den meisten Fällen) konstant schnell am Ende anfügen kann und dann noch random access Iterators zur Verfügung stellt (verkettete Listen scheiden aus) und nicht mehr Speicher verbraucht als von den Elementen verbraucht wird (verkettete Listen und Bäume scheiden aus) dann Hut ab.
Kleiner Tip: schlag mal dict.leo.org auf und schau nach was amortized heißen könnte. Darüber hinaus stell dir folgende Situation vor: du hast einen vector, Kapazität 24 Elemente, Inhalt 23 Elemente. Du fügst ein Element am Ende an. Was passiert?
Ben04 schrieb:
aber ich glaube ganz ehrlich, dass du die problematik hier nicht verstehst. niemand sagt dass vector schlecht ist, aber es ist bloedsinn vector zu verwenden wenn boost::array den job besser machen wuerde.
Genau, vector ist ein Array das dafür gebaut ist seine Größe zu verändern. Fals die Größe bekannt ist dann gibt es besseres.
Genau. Das ist ja die Ausgangssituation, die Größe ist nicht bekannt, und sie verändert sich. Du hast lediglich eine Obergrenze, und da diese bekannt ist kommt man um die angesprochene Speicherproblematik herum. Was soll daran so schwer zu kapieren sein?
-
du hast einen vector, Kapazität 24 Elemente, Inhalt 23 Elemente
Kleine Frage : Wenn du eine Kapazität von 24 Elementen hast und weis, dass du nie mehr als 23 Elemente brauchen wirst, wird dann Speichrer verschwendet? Na?
Was soll daran so schwer zu kapieren sein?
Gute Frage, nur sehe ich nicht wen du damit ansprechen willst. Fals du mich meinst dann ließ doch noch einmal was ich geschrieben habe.
-
Ben04 schrieb:
du hast einen vector, Kapazität 24 Elemente, Inhalt 23 Elemente
Kleine Frage : Wenn du eine Kapazität von 24 Elementen hast und weis, dass du nie mehr als 23 Elemente brauchen wirst, wird dann Speichrer verschwendet? Na?
wenn du weisst, dass du nur 23 elemente brauchst, aber 24 reservierst, ist das nicht deine eigene dummheit? Na?
-
ist der Geschwindgkeits und Speicherverlust überhaupt bemerkbar? Wenn ja ab dem wievielten Element?
und kann ich an einen vector auch die zeiger von Klassen ranhängen?Achja, was den Stack angeht... werden die Elemente nun auf den Stack gelegt? Das wär nämlich schlecht (bei vielen Elementen). Irgendwie ist das so in der Diskusion untergegangen.
-
Chris++ schrieb:
ist der Geschwindgkeits und Speicherverlust überhaupt bemerkbar? Wenn ja ab dem wievielten Element?
Kommt auf die Situation und die Implementierung von vector an.
Chris++ schrieb:
und kann ich an einen vector auch die zeiger von Klassen ranhängen?
Warum nicht? std::vector<MeineKlasse*>
Chris++ schrieb:
Achja, was den Stack angeht... werden die Elemente nun auf den Stack gelegt?
Beim vector? Nein.
-
Chris++ schrieb:
ist der Geschwindgkeits und Speicherverlust überhaupt bemerkbar? Wenn ja ab dem wievielten Element?
Ich habe schon weiter oben gesagt: vector allokiert idR mit Faktor 2 bzw. modernen mit Fakto 1.5 einige behaupten auch 1.3 soll ideal sein...
dh, wenn du 100 elemente hast und neu allokieren musst, hast du speicher von 130 bis 200 elementen belegt.
jetzt rechne dass auch 10000 elemente um...
da kann eine schlechte allokations strategie sehr schlimm werden. denn bei vector hängt alles nur von der allokierung ab.Aber was ihr dauernd übergeht sind die kosten für die allokierung. die sind nicht groß, aber gegenüber einem array auf dem stack doch merkbar.
-
Shade Of Mine schrieb:
Aber was ihr dauernd übergeht sind die kosten für die allokierung. die sind nicht groß, aber gegenüber einem array auf dem stack doch merkbar.
In wie fern, positiv (geht schneller) oder negativ (langsamer). Ich würd mit meinem jetztigen Wissen ja auf negativ tippen da das Array ja jedesmal größer erstellt wird und die alten Daten erst rüberkopiert werden müssen.
Was die speicherallokierung angeht (um sicher zu gehen): es wird erst wieder neuer Speicher allokiert wenn der vorhandene aufgebraucht ist?
-
Chris++ schrieb:
In wie fern, positiv (geht schneller) oder negativ (langsamer).
langsamer.
Chris++ schrieb:
Was die speicherallokierung angeht (um sicher zu gehen): es wird erst wieder neuer Speicher allokiert wenn der vorhandene aufgebraucht ist?
Genau. Und dabei etwas mehr als du für die aktuelle Operation brauchst, um nicht ständig umkopieren zu müssen.
Ben04 schrieb:
du hast einen vector, Kapazität 24 Elemente, Inhalt 23 Elemente
Kleine Frage : Wenn du eine Kapazität von 24 Elementen hast und weis, dass du nie mehr als 23 Elemente brauchen wirst, wird dann Speichrer verschwendet? Na?
Wenn du schon nicht antworten willst dann lern zumindest lesen.
-
Also ich habe hier ein halbes Gigabyte an Speicher. Ob jetzt Speicher für 24 oder 48 Objekte angelegt wird, interssiert mich also erst, wen ein einzelnes Objekt verdammt groß sind.
Das ändert natürlich nichts daran, das boost::array hier am sinnvollsten erscheint.
-
finix schrieb:
Ben04 schrieb:
du hast einen vector, Kapazität 24 Elemente, Inhalt 23 Elemente
Kleine Frage : Wenn du eine Kapazität von 24 Elementen hast und weis, dass du nie mehr als 23 Elemente brauchen wirst, wird dann Speichrer verschwendet? Na?
Wenn du schon nicht antworten willst dann lern zumindest lesen.
Alles relevant wurde bereits gesagt. Und wenn du nicht siehst, dass man mehr Speicher holen muss als angefragt um ein Anfügen am Ende ohne Neuanlegung des Buffers zu realisiren, dann kann ich dir auch nicht helfen.
wenn du weisst, dass du nur 23 elemente brauchst, aber 24 reservierst, ist das nicht deine eigene dummheit? Na?
Die Implementirung kann frei wählen wie viel Speicher sie holt. Ich kann nur per reserve Tips geben.
-
Chris++ schrieb:
ist der Geschwindgkeits und Speicherverlust überhaupt bemerkbar?
hier nicht. bei hunderten von std::strings, die alle selber mit new operieren, ist das eine mal new vom std::vector echt egal. bei sowas immer std::vector nehmen. guter tip.
ich wehre mich nur dagegen, immer und überall std::vector zu nehmen, zum beispiel bei meiner 4-gewinnt-ki. jeder zug wird bewertet, indem die (bis zu 7) folgezüge bewertet werden und davon der für den gegner beste genommen wird. der suchbaum wird recht breit, wenn er in die tiefe geht, dauert deswegen alles langsam. die klasse Spielfeld kann eine liste aller von dieser Stellung aus möglichen Züge ausgeben. soll ich da vector, stack, rohe arrays, bitfields oder was nehmen? naja, ich nahm rohe arrays. und auf jeden fall verbieten sich hier std::vectors. also es gibt fälle, wo std::vector echt kacke ist. deswegen hatte ich anfangs widersprochen. weil diese all-aussage einfach falsch war. das ändert natürlich nix daran, daß std::vector fast immer eine gute wahl ist.