Wie arbeitet der std::vector intern ?
-
Hallo,
wie arbeitet der std::vector intern? Speichert er
seine Daten in einem Array? Ich bin der Meinung
schon weil man ja mit einem Index auf die Daten
zugreifen kann. Aber wenn er mit einem Array
intern arbeitet wie ist es dann wenn ich neue
Elemente einfüge dann müsste ja immer ein neues
Array angelegt werden und alle altenen Elemente
darüberkopiert werden.mfg
-
Lern lieber mal nachzudenken und öffne einfach den Header, da ist es ja implementiert. Btw natürlich mit Array, natürlich mit Kopieren!
-
Wobei nicht immer kopiert werden muss, da wenn man ein Element rauslöscht, dann verkleinert Vektor das Array nicht, sondern behält den Speicherplatz.
-
bluecode schrieb:
Wobei nicht immer kopiert werden muss, da wenn man ein Element rauslöscht, dann verkleinert Vektor das Array nicht, sondern behält den Speicherplatz.
Ist dieser Container dann nicht sehr uneffektiv ?
-
Wenn ein std::vector sich vergrößern muß, holt er sich mehr Speicher als notwendig, um bei weiteren Vergrößerungen nicht wieder kopieren zu müssen.
Eine Strategie ist zum Beispiel den reservierten Speicher immer zu verdoppeln. Wenn du in so einen std::vector immer wieder mit push_back() neue Elemente dranhängst wird durchschnittlich jedes Element nur einmal kopiert. Dafür hat man aber einen höheren Speicherverbrauch, der aber höchstens doppelt so groß ist und durchschnittlich viel weniger.
Wenn dagegen bekannt ist, wieviele Elemente irgendwann in den std::vector rein sollen, kann man im voraus den Speicher mittels reserve() reservieren. Nun kann man die angegebene Anzahl an Elementen hinten dranfügen ohne einen höheren Speicherverbrauch oder unnütze Kopieraktionen befürchten zu müssen.