Wie funktioniert ein Vector intern



  • wenn ich einen Vector verwende:

    struct foo{
    
    int i;
    long l;
    }
    
    std::vector<foo> vBar;
    

    wenn ich nun neue elemen hinzufügen mit push oder so, dann wird interen ne objekt liste eerstell nehm ich an .. seh ich das richtig?



  • vector ist doch ein array. wenn es zu klein wird, dann wirds vergrößert, sonst nur vec[last] = x, oder so ähnlich.



  • Musst du nachsehen in <vector>. In der Regel hat der Vektor einen Pointer auf ein Array auf dem Heap und eine Variable, die sich die Größe merkt. Ist das Array zu klein wird seine Größe verdoppelt.



  • Da ein Vector laut ISO-Standard konstante Zugriffszeiten haben muß, ist er wohl zu 100% der Fälle intern als Array implementiert. Nur halt mit ein paar Komfortfunktionen, die einem das Leben ggü. einem primitiven Array unheimlich erleichtern.



  • Dann könnte es doch auch eine HashMap sein.



  • Nein, denn ein vector garantiert auch, daß seine Elemente hintereinander im Speicher stehen (und außerdem ist eine Hash-Map für den Zweck etwas übertrieben)*. Afaik passt geloescht's Aussage am ehesten zu den Vorgaben eines vector's - er hat intern einen Zeiger und eine Hilfsvariable für die Größe (capacity()) und verdoppelt seine Kapazität, wenn er überläuft.

    @Artchi: push_back() hat nur im Mittel konstante Laufzeit - und durch die Verdoppelungsstrategie ist gesichert, daß die teuren Reallokationen auf die Dauer nicht ins Gewicht fallen.

    * OK, Eigentlich ist ein Array auch eine Hash-Map - mit der primitiven Hash-Funktion h(x)=x 😉



  • KennerDerZugriffszeiten schrieb:

    Dann könnte es doch auch eine HashMap sein.

    Die ist aber ungeordnet.



  • Die ist schon geordnet. Nur sieht die Ordnungsrelation anders aus.


  • Mod

    Artchi schrieb:

    Da ein Vector laut ISO-Standard konstante Zugriffszeiten haben muß, ist er wohl zu 100% der Fälle intern als Array implementiert. Nur halt mit ein paar Komfortfunktionen, die einem das Leben ggü. einem primitiven Array unheimlich erleichtern.

    Ein guter Gedanke, leider nicht bis zu Ende durchdacht. Ein Blick in die Beschreibung von deque wird dich im Übrigen eines Besseren belehren, denn dessen Komplexitätsgarantien sind sogar noch strenger als die von vector. Richtig ist, dass vector seine Daten in einem Array speichert und auch, dass seine Eigenschaften einschließlich der Komplexitätsgarantien derart gewählt sind, dass diese Implementation geradezu nahe liegt (vector ja als Ersatz für arrays dienen). Der Schluss in die andere Richtung ist dennoch unzuöässig. Vector speichert seine Daten in einem Array, weil der Standard sagt, dass vector das tut.


Anmelden zum Antworten