Nach Accelerated C ++:
Um diese Strategie zu verwenden, müssen wir ein Element aus einem Vektor entfernen. Die gute Nachricht ist, dass eine solche Einrichtung existiert; Die schlechte Nachricht ist, dass das Entfernen von Elementen aus Vektoren langsam genug ist, um gegen die Verwendung dieses Ansatzes für große Mengen von Eingabedaten zu argumentieren. Wenn die Daten, die wir verarbeiten, wirklich groß werden, verschlechtert sich die Leistung in einem erstaunlichen Ausmaß.
Wenn zum Beispiel alle unsere Schüler ausfallen würden, würde die Ausführungszeit der Funktion, die wir gerade sehen, proportional zum Quadrat der Schülerzahl wachsen. Das bedeutet, dass für eine Klasse von 100 Studenten das Programm 10.000 Mal so lange dauern würde wie für einen Studenten. Das Problem besteht darin, dass unsere Eingabedatensätze in einem Vektor gespeichert sind, der für schnellen Direktzugriff optimiert ist. Ein Preis dieser Optimierung ist, dass es teuer sein kann, andere Elemente als am Ende des Vektors einzufügen oder zu löschen.
Die Autoren erklären nicht, warum der Vektor für 10.000+ Studenten so langsam ist und warum es im Allgemeinen langsam ist, Elemente in der Mitte eines Vektors hinzuzufügen oder zu entfernen. Könnte jemand auf Stack Overflow eine schöne Antwort für mich finden?
Nimm eine Reihe von Häusern: Wenn du sie in einer geraden Linie baust, ist es sehr einfach, Nr. 32 zu finden: Geh einfach die Straße entlang, die 32 Häuser wert ist, und du bist da. Aber es macht nicht so viel Spaß, Haus Nr. 31 und die Hälfte hinzuzufügen; in der Mitte - das ist ein großes Bauprojekt mit vielen Unterbrechungen für das Leben von Ehemann / Ehefrau und Kindern. Im schlimmsten Fall ist sowieso nicht genug Platz für ein anderes Haus, also muss man alle die Häuser auf eine andere Straße ziehen, bevor man überhaupt anfängt.
Ähnlich speichern Vektoren ihre Daten zusammenhängend , d.h. in einem fortlaufenden, sequentiellen Block im Speicher.
Dies ist sehr gut, um schnell das n th -Element zu finden (da Sie einfach n -Positionen und Dereferenzierung durchlaufen müssen), aber sehr schlecht für das Einfügen in die Mitte, da Sie alle späteren Elemente einzeln nacheinander verschieben müssen.
Andere Container sind so konstruiert, dass sie einfach zu verwenden sind, aber der Nachteil ist, dass sie folglich nicht so leicht zu finden sind. Es gibt keinen Container, der für alle Operationen optimal ist.
Beim Einfügen von Elementen in die Mitte eines std::vector<T> oder Entfernen von Elementen müssen alle Elemente nach dem Änderungspunkt verschoben werden: Beim Einfügen müssen sie weiter nach hinten verschoben werden, beim Entfernen müssen sie zum Schließen nach vorne verschoben werden die Lücke. Der Hintergrund ist, dass std::vector<T> im Grunde nur eine zusammenhängende Folge von Elementen ist.
Obwohl diese Operation für bestimmte Typen nicht schlecht ist, kann sie vergleichsweise langsam werden. Es ist jedoch zu beachten, dass die Größe des Containers eine vernünftige Größe haben muss oder die Kosten des Bewegens signifikant sind: für kleine Vektoren ist das Einfügen in / aus der Mitte wahrscheinlich schneller als die Verwendung anderer Datenstrukturen, z. B. Listen. Letztendlich zahlen sich die Kosten für die Aufrechterhaltung einer komplexeren Struktur jedoch aus.
std :: vector weist Speicher als einen Extent zu. Wenn Sie ein Element in die Mitte des Extents einfügen müssen, müssen Sie alle Elemente des Vektors nach rechts verschieben, um einen freien Slot zu bilden, an dem Sie das neue Element einfügen. Und außerdem, wenn die Erweiterung bereits voller Elemente ist, muss der Vektor eine neue größere Ausdehnung zuweisen und alle Elemente von der ursprünglichen Ausdehnung in die neue kopieren.
Tags und Links c++ performance vector containers