Eine STL vector hat eine size (aktuelle Anzahl gespeicherter Elemente) und ein capacity (derzeit zugewiesener Speicherplatz).
size < capacity , ein push_back einfach das neue Element an das Ende setzt und die size um 1 erhöht. size == capacity vor push_back , ein neues, größeres Array zugewiesen wird (doppelt so groß wie gewöhnlich, aber dies ist ein implementierungsabhängiges afaik), werden alle aktuellen Daten kopiert (einschließlich des neuen Elements) und der alte zugewiesene Speicherplatz wird freigegeben. Dies kann eine Ausnahme auslösen, wenn die Zuweisung fehlschlägt. Die Komplexität der Operation ist amortized O (1), was bedeutet, dass während einer push_back , die eine Größenänderung verursacht, keine Operation mit konstanter Zeit durchgeführt wird (sondern im Allgemeinen über viele) Operationen, ist es).
Das ist natürlich inhärent Implementierung definiert. Angenommen, es geht darum, wie jemand ein dynamisches Array implementieren würde, wäre es im Allgemeinen so:
push_back überprüft capacity() und stellt sicher, dass es mindestens eins größer ist als size() . Einige STL-Implementierungen werden einige der Kopien mithilfe von Swaps (d. h. für Containern von Containern) bereitstellen, aber in den meisten Fällen funktioniert das genau so.
Möglicherweise haben sie gesucht, dass push_back eine Kopie des Objekts erstellt, das auf das vector (unter Verwendung seines Kopierkonstruktors) geschoben wird.
Bezüglich der Größenanpassung: Der Standard sagt a.push_back(x) entspricht a.insert(a.end(),x) . Die Definition von insert sagt zum Teil: "Verursacht Neuzuweisung, wenn die neue Größe größer als die alte Kapazität ist."
Der Standard sagt was die Funktionen tun sollen. Aber wie sie implementiert werden, ist in den meisten Fällen implementierungsspezifisch.
vector verwendet keine verknüpfte Liste. Es verwendet kontinuierlichen Speicher.
Wenn nicht genügend reservierter Speicherplatz vorhanden ist, reserviert push_back einen neuen Speicherbereich zweimal so groß wie die ursprüngliche vector . Dadurch ist die amortisierte Laufzeit O (1).
Dank einiger Kommentare überarbeite ich eine sehr falsche ursprüngliche Antwort vollständig.
Laut STL-Spezifikation war Ihre Antwort korrekt. Der Vektor wird als dynamisch skaliertes Array implementiert:
Vektorcontainer sind als dynamische Arrays implementiert; Genauso wie reguläre Arrays haben Vektorcontainer ihre Elemente an zusammenhängenden Speicherorten gespeichert, was bedeutet, dass auf ihre Elemente nicht nur mit Iteratoren zugegriffen werden kann, sondern auch Offsets für reguläre Zeiger auf Elemente verwendet werden können Im Gegensatz zu regulären Arrays wird der Speicher in Vektoren jedoch automatisch verarbeitet, sodass er bei Bedarf erweitert und verkleinert werden kann.
Wie viel Detail wollte der Interviewer? Hat er zum Beispiel nach dir gesucht, um in die Details auf der unteren Ebene zu gelangen?
Neben der üblichen Größenanpassung, die erforderlich ist, um die durchschnittliche Semantik von O (1) beizubehalten, sind einige Dinge zu berücksichtigen, die aber nicht darauf beschränkt sind:
vector anstelle des einfachen alten Zuweisers new (beide können identisch sein oder nicht)? Im Idealfall wird dies transparent durch den% resize-Code von vector gehandhabt, Implementierungen könnten sich jedoch durchaus unterscheiden. Wenn Größe & lt; capasity, dann scheint alles in Ordnung zu sein, du fügst einfach en element in vector ein, die Komplexität ergibt sich, wenn size == capasity.
Es ist leicht zu erklären, dass Sie ein neues Array doppelt größer als das vorhandene Array zuweisen müssen und alle diese Elemente in den neuen zugewiesenen Speicher kopieren und das alte löschen und das neue Element in das neue Array einfügen. Aber hier sind einige Schlüsselmomente, von denen ich glaube, dass sie von Ihrem Interviewer erwartet werden.
Die Elemente in std :: vector werden nicht in einem Array gespeichert, daher ist das Datenelement von std :: vector [1000] kein int * der Länge 1000. Die Elemente werden in Speicherblöcken gespeichert. Daher müssen Sie beim Kopieren darauf achten.
Zweitens, der Standard-stl-Vektor erfordert "gib mir ein kopierbares Objekt und ich kann es einfügen", was bedeutet, dass Requierment auf std :: vector ist, dass irgendjemand nur einen copy_constructer (nicht operator =) haben muss. Wenn Sie also einen neuen Speicher vom Typ "IrgendjArt" reservieren, müssen Sie berücksichtigen, dass sometimy keinen Standard-Kopierkonstruktor hat. In üblichen Implementierungen geschieht dies durch die Platzierung eines neuen Operators, um den Aufruf von Kopierkonstruktoren zu vermeiden.