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

Question

Was sind die Unterschiede zwischen einer std::vector und ein std::array in C++? Wann sollte das eine dem anderen vorgezogen werden? Was sind die Vor- und Nachteile der einzelnen Systeme? In meinem Lehrbuch wird nur aufgelistet, dass sie gleich sind.

Answer 1

std::vector ist eine Vorlagenklasse, die ein dynamisches Array kapselt 1 die auf dem Heap gespeichert sind und automatisch wachsen und schrumpfen, wenn Elemente hinzugefügt oder entfernt werden. Es bietet alle Haken ( begin() , end() , Iteratoren usw.), so dass es mit dem Rest der STL gut funktioniert. Es hat auch mehrere nützliche Methoden, mit denen Sie Operationen durchführen können, die bei einem normalen Array umständlich wären, wie z. B. das Einfügen von Elementen in der Mitte eines Vektors (es erledigt die ganze Arbeit des Verschiebens der folgenden Elemente im Hintergrund).

Da die Elemente in einem auf dem Heap zugewiesenen Speicher gespeichert werden, entsteht im Vergleich zu statischen Arrays ein gewisser Overhead.

std::array ist eine Vorlagenklasse, die ein statisch dimensioniertes Array kapselt, das im Objekt selbst gespeichert ist, was bedeutet, dass sich das Array selbst auf dem Stack befindet, wenn Sie die Klasse auf dem Stack instanzieren. Seine Größe muss zur Kompilierzeit bekannt sein (sie wird als Template-Parameter übergeben), und es kann weder wachsen noch schrumpfen.

Sie ist eingeschränkter als std::vector aber es ist oft effizienter, vor allem für kleine Größen, weil es in der Praxis meist ein leichtgewichtiger Wrapper um ein C-artiges Array ist. Es ist jedoch sicherer, da die implizite Konvertierung in Zeiger deaktiviert ist, und es bietet einen Großteil der STL-bezogenen Funktionalität von std::vector und der anderen Container, so dass Sie sie problemlos mit STL-Algorithmen & Co. verwenden können. Jedenfalls ist es durch die Beschränkung auf eine feste Größe viel weniger flexibel als std::vector .

Für eine Einführung in std::array sehen Sie sich an dieser Artikel ; für eine schnelle Einführung in std::vector und zu den möglichen Operationen, die damit möglich sind, können Sie sich die Dokumentation .

---

1. Ich glaube, dass sie in der Norm in Bezug auf die maximale Komplexität der verschiedenen Operationen beschrieben werden (z. B. Zufallszugriff in konstanter Zeit, Iteration über alle Elemente in linearer Zeit, Hinzufügen und Entfernen von Elementen am Ende in konstanter amortisierter Zeit usw.), aber AFAIK gibt es keine andere Methode, solche Anforderungen zu erfüllen, als ein dynamisches Array zu verwenden. Wie von @Lucretiel erwähnt, verlangt der Standard eigentlich, dass die Elemente zusammenhängend gespeichert werden, also es ist ein dynamisches Array, das dort gespeichert wird, wo der zugehörige Allocator es hinlegt.

Answer 2

Um eine Aussage von @MatteoItalia zu unterstreichen: Der Unterschied in der Effizienz liegt darin, wo die Daten gespeichert werden. Heap-Speicher (erforderlich bei vector ) erfordert einen Aufruf an das System, um Speicher zuzuweisen, und das kann teuer werden, wenn Sie Zyklen zählen. Stapelspeicher (möglich bei array ) ist in Bezug auf den Zeitaufwand praktisch "Null-Overhead", da der Speicher durch einfaches Anpassen des Stack-Zeigers zugewiesen wird und dies nur einmal beim Eintritt in eine Funktion geschieht. Der Stack vermeidet auch die Fragmentierung des Speichers. Um sicher zu sein, std::array wird nicht immer auf dem Stack liegen; es hängt davon ab, wo Sie es zuweisen, aber es wird immer noch eine Speicherzuweisung weniger vom Heap im Vergleich zum Vektor erfordern. Wenn Sie eine

• kleines "Array" (z. B. weniger als 100 Elemente) - (ein typischer Stack ist etwa 8 MB groß, also nicht mehr als ein paar KB auf dem Stack oder weniger, wenn Ihr Code rekursiv ist)
• die Größe wird festgelegt
• die Lebensdauer liegt im Funktionsbereich (oder ist ein Mitgliedswert mit der gleichen Lebensdauer wie die übergeordnete Klasse)
• Sie zählen die Zyklen,

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

Answer 3

Zusammenfassung der obigen Diskussion in einer Tabelle zum schnellen Nachschlagen:

C-Style Array

std::array

std::vector

Größe

Feststehend/Statisch

Feststehend/Statisch

Dynamisch

Speichereffizienz

Mehr Effizienz

Effizienter

Weniger effizient
(Kann seine Größe bei neuer Zuteilung verdoppeln.)

Kopieren

Über Elemente iterieren
oder std::copy() verwenden

Direkte Kopie: a2 = a1;

Direkte Kopie: v2 = v1;

Übergabe an die Funktion

Durch Zeiger weitergegeben.
(Größe nicht in Funktion verfügbar)

Übergeben durch Wert

Übergeben durch Wert
(Größe verfügbar in dieser Funktion)

Größe

sizeof(a1) / sizeof(a1[0])

a1.size()

v1.size()

Anwendungsfall

Für schnellen Zugriff und wenn
Einfügungen/Löschungen werden nicht häufig benötigt.

Wie bei der klassischen Anordnung, aber
sicherer und einfacher zu übermitteln und zu kopieren.

Wenn häufige Hinzufügungen oder
Streichungen könnten erforderlich sein

Answer 4

Wenn Sie die Verwendung von mehrdimensionalen Arrays in Erwägung ziehen, gibt es einen weiteren Unterschied zwischen std::array und std::vector. Bei einem mehrdimensionalen std::array werden die Elemente in allen Dimensionen in den Speicher gepackt, genau wie bei einem c-artigen Array. Ein mehrdimensionaler std::vector wird nicht in allen Dimensionen gepackt.

Gegeben sind die 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 c-style Array (cConc) oder im std::Array (aConc) kann durch das gesamte Array iteriert werden, indem zu jedem vorangehenden Element 1 addiert wird. Sie sind dicht gepackt.

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

Das bedeutet, dass ein std::vector>-Array, das als [3][1000]-Array initialisiert wird, im Speicher viel kleiner sein wird als eines, das als [1000][3]-Array initialisiert wird, und beide werden im Speicher größer sein als ein std:Array, das auf die eine oder andere Weise zugewiesen wird.

Dies bedeutet auch, dass Sie nicht einfach einen mehrdimensionalen Vektor (oder Zeiger) Array zu, sagen wir, OpenGL ohne Berücksichtigung der Speicher-Overhead, aber Sie können naiv übergeben ein mehrdimensionales std::Array zu OpenGL und haben es funktioniert.

Answer 5

Die Verwendung des std::vector<T> Klasse:

• ...ist genau so schnell wie bei der Verwendung integrierter Arrays, vorausgesetzt, Sie tun nur das, was integrierte Arrays Ihnen erlauben (Lesen und Schreiben auf vorhandene Elemente).

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

• ...ermöglicht das Einfügen neuer Elemente zu Beginn o in der Mitte des Vektors, wobei die übrigen Elemente automatisch "nach oben" verschoben werden (macht das Sinn?). Damit können Sie Elemente an beliebiger Stelle im std::vector und verschiebt automatisch die übrigen Elemente nach unten.

• ...ermöglicht es Ihnen, ein bereichsgeprüftes Lesen mit dem at() Methode (Sie können jederzeit die Indexer [] wenn Sie nicht möchten, dass diese Prüfung durchgeführt wird).

Es gibt zwei drei wesentliche Vorbehalte gegen die Verwendung std::vector<T> :

1. Sie haben keinen zuverlässigen Zugriff auf den zugrunde liegenden Zeiger, der Mai ein Problem darstellen, wenn Sie mit Funktionen von Drittanbietern arbeiten, die die Adresse eines Arrays verlangen.

2. En std::vector<bool> Klasse ist dumm. Sie ist als komprimiertes Bitfeld implementiert, nicht als Array. Vermeiden Sie es, wenn Sie ein Array von bool s!

3. Während der Nutzung, std::vector<T> s werden etwas größer sein als ein C++-Array mit der gleichen Anzahl von Elementen. Das liegt daran, dass sie eine kleine Menge anderer Informationen, wie z.B. ihre aktuelle Größe, speichern müssen, und weil jedes Mal, wenn std::vector<T> Sie reservieren mehr Platz, als sie benötigen. Damit soll verhindert werden, dass die Größe jedes Mal angepasst werden muss, wenn ein neues Element eingefügt wird. Dieses Verhalten kann geändert werden, indem man eine eigene allocator aber ich hatte nie das Bedürfnis, das zu tun!

---

Edit: Nachdem ich Zuds Antwort auf die Frage gelesen habe, wollte ich dies hinzufügen:

En std::array<T> Klasse ist nicht dasselbe wie ein C++-Array. std::array<T> ist ein sehr dünner Wrapper um C++-Arrays herum, dessen Hauptzweck es ist, den Zeiger vor dem Benutzer der Klasse zu verbergen (in C++ werden Arrays implizit als Zeiger gecastet, oft mit erschreckender Wirkung). Die std::array<T> Klasse speichert auch ihre Größe (Länge), was sehr nützlich sein kann.