std :: vector versus std :: array in C ++

Was ist der Unterschied zwischen a std::vectorund an std::arrayin C ++? Wann sollte einer dem anderen vorgezogen werden? Was sind die Vor- und Nachteile von jedem? Mein Lehrbuch listet nur auf, wie sie gleich sind.

std::vectorist eine Vorlagenklasse , die ein im Heap gespeichertes dynamisches Array ¹ kapselt , das automatisch wächst und schrumpft, wenn Elemente hinzugefügt oder entfernt werden. Es bietet alle Haken ( begin(), end(), Iteratoren, usw.) , die es funktioniert gut mit dem Rest der STL. Es gibt auch einige nützliche Methoden, mit denen Sie Operationen ausführen können, die für ein normales Array umständlich wären, z. B. das Einfügen von Elementen in die Mitte eines Vektors (es übernimmt die gesamte Arbeit, die folgenden Elemente hinter die Kulissen zu verschieben).

Da die auf dem Heap zugewiesenen Elemente im Speicher gespeichert werden, hat dies einen gewissen Overhead in Bezug auf statische Arrays.

std::arrayist eine Vorlagenklasse, die ein statisch großes Array kapselt, das im Objekt selbst gespeichert ist. Wenn Sie also die Klasse auf dem Stapel instanziieren, befindet sich das Array selbst auf dem Stapel. Seine Größe muss zur Kompilierungszeit bekannt sein (es wird als Vorlagenparameter übergeben) und kann nicht wachsen oder schrumpfen.

Es ist begrenzter als std::vector, aber es ist oft effizienter, insbesondere für kleine Größen, da es in der Praxis meistens eine leichte Hülle um ein Array im C-Stil ist. Es ist jedoch sicherer, da die implizite Konvertierung in einen Zeiger deaktiviert ist und einen Großteil der STL-bezogenen Funktionen der std::vectorund der anderen Container bereitstellt , sodass Sie sie problemlos mit STL-Algorithmen & Co. verwenden können. Wie auch immer, für die Begrenzung der festen Größe ist es viel weniger flexibel als std::vector.

Eine Einführung zu std::arrayfinden Sie in diesem Artikel . Für eine schnelle Einführung in std::vectorund in die Operationen, die darauf möglich sind, sollten Sie sich die Dokumentation ansehen .

1. Tatsächlich denke ich, dass sie im Standard im Hinblick auf die maximale Komplexität der verschiedenen Operationen beschrieben werden (z. B. Direktzugriff in konstanter Zeit, Iteration über alle Elemente in linearer Zeit, Hinzufügen und Entfernen von Elementen am Ende in konstanter Amortisationszeit). usw.), aber AFAIK gibt es keine andere Methode, um solche Anforderungen zu erfüllen, als die Verwendung eines dynamischen Arrays. Wie von @Lucretiel angegeben, verlangt der Standard tatsächlich, dass die Elemente zusammenhängend gespeichert werden. Es handelt sich also um ein dynamisches Array, das dort gespeichert wird, wo der zugehörige Allokator es platziert.

Verwenden der std::vector<T>Klasse:

• ... ist genauso schnell wie die Verwendung von integrierten Arrays, vorausgesetzt, Sie tun nur die Dinge, die Sie mit integrierten Arrays tun können (Lesen und Schreiben in vorhandene Elemente).

• ... ändert automatisch die Größe, wenn neue Elemente eingefügt werden.

• ... ermöglicht es Ihnen, neue Elemente am Anfang oder in der Mitte des Vektors einzufügen und den Rest der Elemente automatisch "nach oben" zu "verschieben" (macht das Sinn?). Sie können damit auch Elemente an einer beliebigen Stelle entfernen std::vectorund den Rest der Elemente automatisch nach unten verschieben.

• ... ermöglicht es Ihnen, mit der at()Methode einen bereichsüberprüften Lesevorgang durchzuführen (Sie können immer die Indexer verwenden, []wenn diese Prüfung nicht durchgeführt werden soll).

Es gibt zwei drei Hauptvorbehalte std::vector<T>:

1. Sie haben keinen zuverlässigen Zugriff auf den zugrunde liegenden Zeiger. Dies kann ein Problem sein, wenn Sie mit Funktionen von Drittanbietern arbeiten, die die Adresse eines Arrays erfordern .

2. Die std::vector<bool>Klasse ist albern. Es ist als komprimiertes Bitfeld implementiert, nicht als Array. Vermeiden Sie es, wenn Sie ein Array von bools wollen!

3. Während der Verwendung werden std::vector<T>s etwas größer sein als ein C ++ - Array mit der gleichen Anzahl von Elementen. Dies liegt daran, dass sie eine kleine Menge anderer Informationen, wie z. B. ihre aktuelle Größe, im std::vector<T>Auge behalten müssen , und dass sie bei jeder Größenänderung mehr Speicherplatz reservieren, als sie benötigen. Dies soll verhindern, dass die Größe jedes Mal geändert werden muss, wenn ein neues Element eingefügt wird. Dieses Verhalten kann durch Angabe eines Brauchs geändert werden allocator, aber ich hatte nie das Bedürfnis, dies zu tun!

Bearbeiten: Nachdem ich Zuds Antwort auf die Frage gelesen hatte, hatte ich das Gefühl, ich sollte Folgendes hinzufügen:

Die std::array<T>Klasse ist nicht mit einem C ++ - Array identisch. std::array<T>ist ein sehr dünner Wrapper um C ++ - Arrays mit dem Hauptzweck, den Zeiger vor dem Benutzer der Klasse zu verbergen (in C ++ werden Arrays implizit als Zeiger umgewandelt, was häufig einen erschreckenden Effekt hat). Die std::array<T>Klasse speichert auch ihre Größe (Länge), was sehr nützlich sein kann.

Um einen Punkt von @MatteoItalia hervorzuheben, besteht der Effizienzunterschied darin, wo die Daten gespeichert werden. Der Heap-Speicher (erforderlich mit vector) erfordert einen Aufruf des Systems, um Speicher zuzuweisen. Dies kann teuer sein, wenn Sie Zyklen zählen. arrayDer Stapelspeicher (möglich für ) ist in Bezug auf die Zeit praktisch "Null-Overhead", da der Speicher durch einfaches Anpassen des Stapelzeigers zugewiesen wird und nur einmal beim Aufrufen einer Funktion ausgeführt wird. Der Stapel vermeidet auch eine Speicherfragmentierung. Natürlich std::arraynicht immer auf dem Stapel; Es hängt davon ab, wo Sie es zuweisen, aber es wird immer noch eine Speicherzuweisung weniger vom Heap im Vergleich zum Vektor erforderlich sein. Wenn Sie eine haben

• kleines "Array" (sagen wir unter 100 Elemente) - (ein typischer Stapel ist ungefähr 8 MB groß. Weisen Sie dem Stapel also nicht mehr als ein paar KB oder weniger zu, wenn Ihr Code rekursiv ist.)
• Die Größe wird festgelegt
• Die Lebensdauer liegt im Funktionsumfang (oder ist ein Elementwert mit derselben Lebensdauer wie die übergeordnete Klasse).
• Sie zählen Zyklen,

Verwenden Sie auf jeden Fall einen std::arrayüber einen Vektor. Wenn eine dieser Anforderungen nicht erfüllt ist, verwenden Sie a std::vector.

Wenn Sie mehrdimensionale Arrays verwenden möchten, gibt es einen zusätzlichen Unterschied zwischen std :: array und std :: vector. Bei einem mehrdimensionalen std :: -Array werden die Elemente in allen Dimensionen im Speicher gepackt, genau wie bei einem Array im AC-Stil. Ein mehrdimensionaler std :: vector wird nicht in allen Dimensionen gepackt.

Angesichts der folgenden Erklärungen:

int cConc[3][5];
std::array<std::array<int, 5>, 3> aConc;
int **ptrConc;      // initialized to [3][5] via new and destructed via delete
std::vector<std::vector<int>> vConc;    // initialized to [3][5]

Ein Zeiger auf das erste Element im Array im c-Stil (cConc) oder im Array std :: (aConc) kann durch das gesamte Array iteriert werden, indem jedem vorhergehenden Element 1 hinzugefügt wird. Sie sind dicht gepackt.

Ein Zeiger auf das erste Element im Vektorarray (vConc) oder das Zeigerarray (ptrConc) kann nur durch die ersten 5 (in diesem Fall) Elemente iteriert werden, und dann gibt es 12 Bytes (auf meinem System) Overhead für das nächster Vektor.

Dies bedeutet, dass ein als [3] [1000] -Array initialisiertes std :: vector> -Array im Speicher viel kleiner ist als ein als [1000] [3] -Array initialisiertes Array, und beide im Speicher größer sind als ein std: Array in beide Richtungen zugewiesen.

Dies bedeutet auch, dass Sie ein einfach mehrdimensionales Vektor- (oder Zeiger-) Array nicht einfach an openGL übergeben können, ohne den Speicheraufwand zu berücksichtigen. Sie können jedoch ein mehrdimensionales std :: -Array naiv an openGL übergeben und es funktionieren lassen.

Ein Vektor ist eine Containerklasse, während ein Array ein zugewiesener Speicher ist.