Was passiert, wenn wir Vektor löschen oder einfügen

Question

Verschiebt es alle Elemente von der rechten Seite des Vektors (auf 1 Position links, wenn löschen und verschieben Sie auf 1 Position rechts, wenn einfügen) oder ist es wie eine verkettete Liste (es erstellt eine neue Adresse und eine neue Adresse Auch wenn ich einen Vektor mit einer Zeichenfolge initiiere, wie kümmert es sich um den Speicher Wenn es in einer Sequenz speichert, was passieren würde, wenn wir push_back weiter machen, wenn es sein Maximum erreicht

Answer 1

Eine std::vector ist (nach dem C++ - Standard) garantiert, die Elemente in einem zusammenhängenden Speicherbereich zu speichern, was bedeutet, dass nein, es ist nicht wie eine verknüpfte Liste, sondern eher wie ein dynamisch zugewiesenes Array push_back Elemente, nachdem der Vektor die Maximale Kapazität Eine Neuzuweisung findet statt und Elemente werden in den neuen Puffer kopiert. Das Gleiche passiert, wenn Sie Elemente einfügen oder löschen, Dinge werden verschoben, so dass diese Operationen im Allgemeinen O (N) und nicht O (1) sind, wie es bei verknüpften Listen der Fall ist.

So sieht es aus wie std::vector ist schlechter als ein std::list. Dies ist jedoch nicht der Fall, da in vielen Anwendungen Leseoperationen die dominierenden sind, für die eine std::vector viel schneller ist als eine std::list aufgrund von Cache-Lokalität und O (1) wahlfreiem Zugriff aufgrund der Tatsache, dass die Elemente zusammenhängend gespeichert werden. Auch push_back ist O (1), außer wenn der Vektor eine Neuzuweisung durchführt (technisch gesehen hat Push_pack die Komplexität von O (1) amortisiert).