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

Was ist der Unterschied zwischen a std::vector und ein std::array in C++? Wann sollte man einem anderen den Vorzug geben? Was sind die Vor- und Nachteile der einzelnen? Alles, was mein Lehrbuch tut, ist aufzulisten, wie sie gleich sind.

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

Da es die Elemente im auf dem Heap zugewiesenen Speicher speichert, hat es in Bezug auf statische Arrays einen gewissen Overhead.

std::array ist eine Vorlagenklasse, die ein Array mit statischer Größe kapselt, das im Objekt selbst gespeichert ist. Wenn Sie also die Klasse auf dem Stack instanziieren, befindet sich das Array selbst auf dem Stack. Seine Größe muss zur Kompilierzeit bekannt sein (sie wird als Vorlagenparameter übergeben) und kann nicht wachsen oder schrumpfen.

Es ist begrenzter als std::vector, aber es ist oft effizienter, besonders für kleine Größen, weil es in der Praxis meistens ein leichtgewichtiger Wrapper um ein Array im C-Stil ist. Es ist jedoch sicherer, da die implizite Konvertierung in einen Zeiger deaktiviert ist, und es bietet einen Großteil der STL-bezogenen Funktionalität von std::vector und der anderen Container, sodass Sie es problemlos mit STL-Algorithmen & Co. verwenden können. Wie auch immer, für die Beschränkung auf eine feste Größe ist es viel weniger flexibel als std::vector.

Zur Einführung in std::arrayschau mal Dieser Beitrag; zum schnellen Einstieg std::vector und zu den Operationen, die darauf möglich sind, möchten Sie vielleicht einen Blick darauf werfen Dokumentation.

1. Tatsächlich denke ich, dass sie im Standard in Bezug auf die maximale Komplexität der verschiedenen Operationen beschrieben werden (z. B. wahlfreier Zugriff 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, um solche Anforderungen zu erfüllen, als ein dynamisches Array zu verwenden. Wie von @Lucretiel angegeben, erfordert der Standard tatsächlich, dass die Elemente zusammenhängend gespeichert werden, also es ist ein dynamisches Array, das dort gespeichert wird, wo der zugeordnete Allokator es ablegt.

Um einen Punkt von @MatteoItalia hervorzuheben: Der Effizienzunterschied besteht darin, wo die Daten gespeichert werden. Heap-Speicher (erforderlich bei vector) erfordert einen Aufruf an das System, um Speicher zuzuweisen, und dies kann teuer werden, wenn Sie Zyklen zählen. Stapelspeicher (möglich für array) ist praktisch “null Overhead” in Bezug auf die Zeit, da die Speicherzuweisung nur durch das Anpassen des Stapelzeigers erfolgt und dies nur einmal beim Aufrufen einer Funktion erfolgt. Der Stack vermeidet auch eine Speicherfragmentierung. Um sicher zu sein, std::array wird nicht immer auf dem Stack sein; 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 Elementen) – (ein typischer Stack ist etwa 8 MB groß, weisen Sie dem Stack also nicht mehr als ein paar KB oder weniger zu, wenn Ihr Code rekursiv ist)
• Die Größe wird festgelegt
• Die Lebensdauer liegt im Funktionsbereich (oder ist ein Elementwert mit derselben Lebensdauer wie die übergeordnete Klasse).
• Du zählst Zyklen,

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

Verwendung der std::vector<T> Klasse:

• …ist genauso schnell wie bei der Verwendung integrierter 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 das Einfügen neuer Elemente am Anfang oder mitten drin des Vektors, wodurch die restlichen Elemente automatisch “nach oben” “verschoben” werden (macht das Sinn?). Es erlaubt Ihnen, Elemente überall in der zu entfernen std::vectorwodurch die restlichen Elemente automatisch nach unten verschoben werden.

• …ermöglicht es Ihnen, einen bereichsgeprüften Lesevorgang mit dem durchzuführen at() Methode (Sie können immer die Indexer verwenden [] wenn Sie diese Prüfung nicht wünschen).

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

1. Sie haben keinen zuverlässigen Zugriff auf den zugrunde liegenden Zeiger, was dürfen ein Problem sein, wenn Sie es mit Funktionen von Drittanbietern zu tun haben, die die Adresse eines Arrays verlangen.

2. Die std::vector<bool> Klasse ist dumm. Es ist als komprimiertes Bitfeld implementiert, nicht als Array. Vermeiden Sie es, wenn Sie ein Array von möchten boolS!

3. Während der Nutzung, std::vector<T>s werden etwas größer sein als ein C++-Array mit der gleichen Anzahl von Elementen. Dies liegt daran, dass sie eine kleine Menge anderer Informationen im Auge behalten müssen, z. B. ihre aktuelle Größe und wann immer sie möchten std::vector<T>s Größe ändern, reservieren sie mehr Platz, als sie benötigen. Dies soll verhindern, dass sie jedes Mal die Größe ändern müssen, wenn ein neues Element eingefügt wird. Dieses Verhalten kann durch Bereitstellung einer benutzerdefinierten geändert werden allocatoraber ich hatte nie das Bedürfnis, das 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> class ist nicht dasselbe wie ein C++-Array. 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, oft mit erschreckender Wirkung). Die std::array<T> Klasse speichert auch ihre Größe (Länge), was sehr nützlich sein kann.

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 multidimensionaler std::vector wird nicht in alle 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 std::array (aConc) kann durch das gesamte Array iteriert werden, indem jedem vorangehenden Element eine 1 hinzugefügt wird. Sie sind dicht gepackt.

Ein Zeiger auf das erste Element im Vektorarray (vConc) oder im 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 die nächster Vektor.

Dies bedeutet, dass ein std::vector> Array als initialisiert wird [3][1000] Das Array wird im Speicher viel kleiner sein als eines, das als a initialisiert wird [1000][3] array, und beide haben einen größeren Arbeitsspeicher als ein std:array, das so oder so zugewiesen wurde.

Das bedeutet auch, dass Sie nicht einfach ein mehrdimensionales Vektor- (oder Zeiger-) Array an OpenGL übergeben können, ohne den Speicheraufwand zu berücksichtigen, aber Sie können naiv ein mehrdimensionales std::array an OpenGL übergeben und es funktioniert.

Fassen Sie die obige Diskussion in einer Tabelle zum schnellen Nachschlagen zusammen:

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