Wie groß ist die Leistungslücke bei Verwendung von Arrays oder std :: -Vektoren in C ++?

207

In unserem C ++ - Kurs wird empfohlen, keine C ++ - Arrays mehr für neue Projekte zu verwenden. Soweit ich weiß, schlägt Stroustroup selbst vor, keine Arrays zu verwenden. Aber gibt es signifikante Leistungsunterschiede?

tunnuz
quelle
2
Warum sollte es Ihrer Meinung nach eine Leistungslücke geben?
Martin York
99
Denn normalerweise kommt mit besserer Funktionalität die schlechteste Leistung.
Tunnuz
19
Ich stimme einer vorzeitigen Optimierung zu, aber die Wahl der besseren Speichermethode im Vorfeld ist sehr sinnvoll. In der realen Welt muss der Code häufig versendet und das nächste Produkt entwickelt werden, und der Optimierungsschritt findet nie statt.
Ameise
132
Ich wünschte, die Leute würden aufhören zu schreien "vorzeitige Optimierung!" wenn jemand eine einfache Frage zur Leistung stellt! Beantworten Sie die Frage und gehen Sie nicht nur PREMATUR davon aus, dass Menschen etwas vorzeitig tun.
d7samurai
4
@ d7samaurai: stimme zu, ich habe noch niemanden gesehen, der es versuchtint main(int argc, const std::vector<string>& argv)
Mark K Cowan

Antworten:

188

Die Verwendung von C ++ - Arrays mit new( dh die Verwendung dynamischer Arrays) sollte vermieden werden. Es gibt das Problem, dass Sie die Größe im Auge behalten müssen und sie manuell löschen und alle Arten von Reinigungsarbeiten durchführen müssen.

Es wird auch davon abgeraten, Arrays auf dem Stapel zu verwenden, da Sie keine Bereichsprüfung durchführen und beim Weitergeben des Arrays alle Informationen über seine Größe verloren gehen (Konvertierung von Array in Zeiger). boost::arrayIn diesem Fall sollten Sie ein C ++ - Array in eine kleine Klasse sizeeinschließen und eine Funktion und Iteratoren bereitstellen , um darüber zu iterieren.

Nun die std :: vector vs. native C ++ - Arrays (aus dem Internet):

// Comparison of assembly code generated for basic indexing, dereferencing, 
// and increment operations on vectors and arrays/pointers.

// Assembly code was generated by gcc 4.1.0 invoked with  g++ -O3 -S  on a 
// x86_64-suse-linux machine.

#include <vector>

struct S
{
  int padding;

  std::vector<int> v;
  int * p;
  std::vector<int>::iterator i;
};

int pointer_index (S & s) { return s.p[3]; }
  // movq    32(%rdi), %rax
  // movl    12(%rax), %eax
  // ret

int vector_index (S & s) { return s.v[3]; }
  // movq    8(%rdi), %rax
  // movl    12(%rax), %eax
  // ret

// Conclusion: Indexing a vector is the same damn thing as indexing a pointer.

int pointer_deref (S & s) { return *s.p; }
  // movq    32(%rdi), %rax
  // movl    (%rax), %eax
  // ret

int iterator_deref (S & s) { return *s.i; }
  // movq    40(%rdi), %rax
  // movl    (%rax), %eax
  // ret

// Conclusion: Dereferencing a vector iterator is the same damn thing 
// as dereferencing a pointer.

void pointer_increment (S & s) { ++s.p; }
  // addq    $4, 32(%rdi)
  // ret

void iterator_increment (S & s) { ++s.i; }
  // addq    $4, 40(%rdi)
  // ret

// Conclusion: Incrementing a vector iterator is the same damn thing as 
// incrementing a pointer.

Hinweis: Wenn Sie Arrays mit newund Nicht-Klassenobjekten (wie Plain int) oder Klassen ohne benutzerdefinierten Konstruktor zuweisen und Ihre Elemente zunächst nicht initialisieren newmöchten, kann die Verwendung von zugewiesenen Arrays Leistungsvorteile haben, da std::vectoralle Elemente mit initialisiert werden Standardwerte (z. B. 0 für int) bei der Erstellung (Dank an @bernie für die Erinnerung an mich).

Johannes Schaub - litb
quelle
77
Wer hat die verdammte AT & T-Syntax erfunden? Nur wenn ich wüsste ... :)
Mehrdad Afshari
4
Dies gilt nicht für den Visual C ++ - Compiler. Aber für GCC ist es das.
toto
5
Der Punkt in meiner Antwort ist , dass Vektor nicht funktioniert hat , langsamer zu sein als Zeigeroperationen Korrespondenz - . Natürlich kann es sein (einfach zu erreichen, indem auch der Debug-Modus aktiviert wird) :)
Johannes Schaub - litb
18
+1 für "Das Indizieren eines Vektors ist dasselbe wie das Indizieren eines Zeigers." und auch für die anderen Schlussfolgerungen.
Nawaz
3
@ Piotr99 Ich werde nicht mit Ihnen streiten, aber wenn Sie nach dem Erlernen höherer Sprachen Assembler lernen, ist die Intel-Syntax viel sinnvoller als einige rückwärts, vorangestellte (Zahlen), angehängte (Anweisungen) und undurchsichtige (Zugriff auf Speicher) ) Art der AT & T-Syntax.
Cole Johnson
73

Präambel für Mikrooptimierer

Merken:

"Programmierer verschwenden enorm viel Zeit damit, über die Geschwindigkeit unkritischer Teile ihrer Programme nachzudenken oder sich darüber Gedanken zu machen, und diese Effizienzversuche wirken sich tatsächlich stark negativ aus, wenn Debugging und Wartung in Betracht gezogen werden. Wir sollten beispielsweise kleine Effizienzvorteile vergessen." 97% der Zeit: Vorzeitige Optimierung ist die Wurzel allen Übels. Dennoch sollten wir unsere Chancen in diesen kritischen 3% nicht verpassen. "

(Dank Metamorphose für das vollständige Zitat)

Verwenden Sie kein C-Array anstelle eines Vektors (oder was auch immer), nur weil Sie glauben, dass es schneller ist, da es niedriger sein soll. Du würdest dich irren.

Verwenden Sie standardmäßig den Vektor (oder den an Ihre Anforderungen angepassten sicheren Container). Wenn Ihr Profiler ein Problem angibt, prüfen Sie, ob Sie ihn optimieren können, indem Sie entweder einen besseren Algorithmus verwenden oder den Container ändern.

Dies heißt, wir können zur ursprünglichen Frage zurückkehren.

Statisches / dynamisches Array?

Die C ++ - Array-Klassen verhalten sich besser als das C-Array auf niedriger Ebene, da sie viel über sich selbst wissen und Fragen beantworten können, die C-Arrays nicht beantworten können. Sie können nach sich selbst putzen. Und was noch wichtiger ist: Sie werden normalerweise mithilfe von Vorlagen und / oder Inlining geschrieben. Dies bedeutet, dass das, was beim Debuggen von viel Code erscheint, in wenig oder gar keinen Code aufgelöst wird, der im Release-Build erstellt wurde, was keinen Unterschied zu ihrer integrierten, weniger sicheren Konkurrenz bedeutet.

Alles in allem fällt es in zwei Kategorien:

Dynamische Arrays

Die Verwendung eines Zeigers auf ein malloc-ed / new-ed-Array ist bestenfalls so schnell wie die std :: vector-Version und viel weniger sicher (siehe Litbs Beitrag ).

Verwenden Sie also einen std :: vector.

Statische Arrays

Die Verwendung eines statischen Arrays ist bestenfalls:

  • so schnell wie die std :: array version
  • und viel weniger sicher.

Verwenden Sie also ein std :: array .

Nicht initialisierter Speicher

Manchmal verursacht die Verwendung eines vectoranstelle eines Rohpuffers sichtbare Kosten, da der vectorPuffer bei der Erstellung initialisiert wird, während der Code, den er ersetzt, dies nicht tat, wie bernie in seiner Antwort bemerkte .

Wenn dies der Fall ist, können Sie damit umgehen, indem Sie ein unique_ptranstelle von a verwenden vectoroder, wenn der Fall in Ihrer Codeline nicht außergewöhnlich ist, tatsächlich eine Klasse schreiben buffer_owner, die diesen Speicher besitzt, und Ihnen einen einfachen und sicheren Zugriff darauf gewähren, einschließlich Boni wie Größenänderung (mit realloc?) oder was auch immer Sie brauchen.

paercebal
quelle
1
Vielen Dank, dass Sie sich auch mit statischen Arrays befasst haben - std :: vector ist nutzlos, wenn Sie aus Leistungsgründen keinen Speicher dynamisch zuweisen dürfen.
Tom
10
Wenn Sie sagen "Die Verwendung eines statischen Arrays ist bestenfalls so schnell wie die boost :: array-Version", zeigt dies, wie voreingenommen Sie sind. Es sollte das andere sein, Boost: Array kann bestenfalls schnell sein wie statische Arrays.
toto
3
@toto: Es ist ein Missverständnis: Sie sollten es als "Die Verwendung eines statischen Arrays ist bestenfalls ((so schnell wie die boost :: array-Version) && (viel weniger sicher))" lesen. Ich werde den Beitrag bearbeiten, um dies zu klären. Übrigens, danke für den Vorteil des Zweifels.
Paercebal
1
Was ist mit std :: array?
Paulm
4
Zeigen Sie immer das vollständige Angebot. "Programmierer verschwenden enorm viel Zeit damit, über die Geschwindigkeit unkritischer Teile ihrer Programme nachzudenken oder sich darüber Gedanken zu machen, und diese Effizienzversuche wirken sich tatsächlich stark negativ aus, wenn Debugging und Wartung in Betracht gezogen werden. Wir sollten beispielsweise kleine Effizienzvorteile vergessen." 97% der Zeit: Vorzeitige Optimierung ist die Wurzel allen Übels. Dennoch sollten wir unsere Chancen bei diesen kritischen 3% nicht verpassen. " Andernfalls wird es zu einem bedeutungslosen Soundbite.
Metamorphose
32

Vektoren sind Arrays unter der Haube. Die Leistung ist die gleiche.

Ein Punkt, an dem Sie auf ein Leistungsproblem stoßen können, besteht darin, den Vektor zunächst nicht richtig zu dimensionieren.

Wenn sich ein Vektor füllt, ändert sich seine Größe selbst, und dies kann eine neue Array-Zuordnung implizieren, gefolgt von n Kopierkonstruktoren, gefolgt von ungefähr n Destruktoraufrufen, gefolgt von einem Array-Löschen.

Wenn Ihr Konstrukt / Destrukt teuer ist, ist es viel besser, den Vektor zunächst auf die richtige Größe zu bringen.

Es gibt eine einfache Möglichkeit, dies zu demonstrieren. Erstellen Sie eine einfache Klasse, die anzeigt, wann sie erstellt / zerstört / kopiert / zugewiesen wurde. Erstellen Sie einen Vektor dieser Dinge und schieben Sie sie auf das hintere Ende des Vektors. Wenn sich der Vektor füllt, tritt eine Aktivitätskaskade auf, wenn sich die Größe des Vektors ändert. Versuchen Sie es dann erneut mit dem Vektor, der auf die erwartete Anzahl von Elementen dimensioniert ist. Sie werden den Unterschied sehen.

EvilTeach
quelle
4
Pendantry: Die Performance hat den gleichen großen O. std :: vector erledigt ein wenig Buchhaltung, was vermutlich wenig Zeit kostet. OTOH, Sie erledigen am Ende fast die gleiche Buchhaltung, wenn Sie Ihre eigenen dynamischen Arrays rollen.
dmckee --- Ex-Moderator Kätzchen
ja ich verstehe. Der Kern seiner Frage war jedoch, was die Leistungsunterschiede sind ... Ich habe versucht, das anzusprechen.
EvilTeach
Der std :: vector von Gcc erhöht tatsächlich die Kapazität nacheinander, wenn Sie push_back aufrufen.
bjhend
3
@bjhend Dann std::vectorklingt gcc's Standards nicht konform? Ich glaube, der Standard verlangt, dass sich vector::push_backdie konstante Komplexität amortisiert hat, und eine Erhöhung der Kapazität um jeweils 1 push_backwird n ^ 2 Komplexität sein, nachdem Sie Reallocs berücksichtigt haben. - unter der Annahme einer exponentiellen Kapazitätserhöhung bei push_backund insert, wenn dies nicht der Fall ist , reserveführt dies höchstens zu einem konstanten Faktoranstieg bei Kopien von Vektorinhalten. Ein exponentieller Vektorwachstumsfaktor von 1,5 würde ~ 3x so viele Kopien bedeuten, wenn Sie dies nicht tun würden reserve().
Yakk - Adam Nevraumont
3
@bjhend du liegst falsch. Der Standard verbietet exponentielles Wachstum: In § 23.2.3 Absatz 16 heißt es: "In Tabelle 101 sind Operationen aufgeführt, die für einige Arten von Sequenzcontainern bereitgestellt werden, für andere jedoch nicht. Eine Implementierung muss diese Operationen für alle in der Spalte" Container "angegebenen Containertypen bereitstellen werden sie so umsetzen, dass sie eine konstante Zeit amortisieren. " (Tabelle 101 enthält Push_back). Hören Sie jetzt bitte auf, FUD zu verbreiten. Keine Mainstream-Implementierung verstößt gegen diese Anforderung. Die Standard-C ++ - Bibliothek von Microsoft wächst mit dem 1,5-fachen Faktor und GCC mit dem 2-fachen Faktor.
R. Martinho Fernandes
27

Um auf etwas zu antworten, sagte Mehrdad :

Es kann jedoch Fälle geben, in denen Sie noch Arrays benötigen. Bei der Schnittstelle mit Low-Level-Code (dh Assembly) oder alten Bibliotheken, für die Arrays erforderlich sind, können Sie möglicherweise keine Vektoren verwenden.

Überhaupt nicht wahr. Vektoren werden gut in Arrays / Zeiger zerlegt, wenn Sie Folgendes verwenden:

vector<double> vector;
vector.push_back(42);

double *array = &(*vector.begin());

// pass the array to whatever low-level code you have

Dies funktioniert für alle wichtigen STL-Implementierungen. Im nächsten Standard muss es funktionieren (auch wenn es heute gut funktioniert).

Frank Krueger
quelle
1
Der aktuelle Standard sagt so etwas nicht. Es ist impliziert und wird als kontinuierlicher Speicher implementiert. Der Standard besagt jedoch lediglich, dass es sich um einen Direktzugriffscontainer handelt (unter Verwendung von Iteratoren). Der nächste Standard wird explizit sein.
Frank Krueger
1
& * v.begin () wendet den Operator & lediglich auf das Ergebnis der De-Referenzierung des Iterators an. Das De-Referenzieren kann JEDEN Typ zurückgeben. Die Verwendung des Adressoperators kann wieder JEDEN Typ zurückgeben. Der Standard definiert dies nicht als Zeiger auf einen zusammenhängenden Speicherbereich.
Frank Krueger
15
Der ursprüngliche Text des Standards von 1998 erforderte dies zwar nicht, aber 2003 gab es einen Nachtrag, der sich damit befasste, sodass er wirklich vom Standard abgedeckt wird. herbsutter.wordpress.com/2008/04/07/…
Nemanja Trifunovic
2
In C ++ 03 wird ausdrücklich angegeben, dass &v[n] == &v[0] + ndie Gültigkeit ninnerhalb des Größenbereichs liegt. Der Absatz mit dieser Anweisung hat sich mit C ++ 11 nicht geändert.
bjhend
2
Warum nicht einfach std :: vector :: data () verwenden?
Paulm
15

Sie haben noch weniger Gründe, einfache Arrays in C ++ 11 zu verwenden.

Es gibt 3 Arten von Arrays in der Natur, von den schnellsten bis zu den langsamsten, abhängig von den Funktionen, die sie haben (natürlich kann die Qualität der Implementierung die Dinge selbst für Fall 3 in der Liste sehr schnell machen):

  1. Statisch mit der zur Kompilierungszeit bekannten Größe. --- ---.std::array<T, N>
  2. Dynamisch mit zur Laufzeit bekannter Größe und ohne Größenänderung. Die typische Optimierung hierbei ist, dass das Array direkt im Stack zugeordnet werden kann. - Nicht verfügbar . Vielleicht dynarrayin C ++ TS nach C ++ 14. In C gibt es VLAs
  3. Dynamisch und zur Laufzeit anpassbar. --- ---.std::vector<T>

Verwenden Sie für 1. einfache statische Arrays mit einer festen Anzahl von Elementenstd::array<T, N> in C ++ 11.

Für 2. Arrays mit fester Größe, die zur Laufzeit angegeben wurden, deren Größe sich jedoch nicht ändert, wird in C ++ 14 diskutiert, aber es wurde in eine technische Spezifikation verschoben und schließlich aus C ++ 14 erstellt.

Für 3. std::vector<T> wird normalerweise nach Speicher im Heap gefragt . Dies kann Auswirkungen auf die Leistung haben, obwohl Sie std::vector<T, MyAlloc<T>>die Situation mit einem benutzerdefinierten Allokator verbessern können. Der Vorteil gegenüber T mytype[] = new MyType[n];ist, dass Sie die Größe ändern können und dass es nicht wie bei einfachen Arrays in einen Zeiger zerfällt.

Verwenden Sie die genannten Standardbibliothekstypen, um zu vermeiden, dass Arrays in Zeiger zerfallen . Sie sparen Debugging-Zeit und die Leistung ist genau die gleiche wie bei einfachen Arrays, wenn Sie dieselben Funktionen verwenden.

Germán Diago
quelle
2
std :: dynarray. Nach Überprüfung der Kommentare der nationalen Stellen zu n3690 wurde diese Bibliothekskomponente aus dem C ++ 14-Arbeitspapier in eine separate technische Spezifikation abgewählt. Dieser Container ist nicht Teil des Entwurfs von C ++ 14 ab n3797. von en.cppreference.com/w/cpp/container/dynarray
Mohamed El-Nakib
1
sehr gute Antwort. kurz und zusammenfassend, aber mehr Details als alle anderen.
Mohamed El-Nakib
6

Gehen Sie mit STL. Es gibt keine Leistungseinbußen. Die Algorithmen sind sehr effizient und können die Details, über die die meisten von uns nicht nachdenken würden, gut verarbeiten.

John D. Cook
quelle
5

STL ist eine stark optimierte Bibliothek. Es wird sogar empfohlen, STL in Spielen zu verwenden, in denen möglicherweise eine hohe Leistung erforderlich ist. Arrays sind zu fehleranfällig, um für alltägliche Aufgaben verwendet zu werden. Die heutigen Compiler sind auch sehr intelligent und können mit STL wirklich exzellenten Code erzeugen. Wenn Sie wissen, was Sie tun, kann STL normalerweise die erforderliche Leistung erbringen. Wenn Sie beispielsweise Vektoren auf die erforderliche Größe initialisieren (wenn Sie dies von Anfang an wissen), können Sie im Grunde die Array-Leistung erzielen. Es kann jedoch Fälle geben, in denen Sie noch Arrays benötigen. Bei der Schnittstelle mit Low-Level-Code (dh Assembly) oder alten Bibliotheken, für die Arrays erforderlich sind, können Sie möglicherweise keine Vektoren verwenden.

Mehrdad Afshari
quelle
4
Da der Vektor zusammenhängend ist, ist es immer noch ziemlich einfach, eine Schnittstelle zu Bibliotheken herzustellen, für die Arrays erforderlich sind.
Greg Rogers
Ja, aber wenn Sie sich mit den internen Dingen des Vektors anlegen möchten, ist die Verwendung eines Vektors weniger vorteilhaft. Das Schlüsselwort lautete übrigens "möglicherweise nicht".
Mehrdad Afshari
3
Ich weiß nur in einem Fall, wo Vektoren nicht verwendet werden können: Wenn die Größe 0 ist, funktioniert & a [0] oder & * a.begin () nicht. c ++ 1x wird das beheben, indem eine a.data () -Funktion eingeführt wird, die den internen Puffer zurückgibt, der die Elemente behält
Johannes Schaub - litb
Das spezifische Szenario in meinem Kopf, als ich schrieb, waren stapelbasierte Arrays.
Mehrdad Afshari
1
Schnittstellenvektor oder zusammenhängender Container mit C: vec.data()für Daten und vec.size()Größe. So einfach ist das.
Germán Diago
5

Über Dulis Beitrag .

Die Schlussfolgerung ist, dass Arrays von Ganzzahlen schneller sind als Vektoren von Ganzzahlen (in meinem Beispiel fünfmal). Arrays und Vektoren sind jedoch für komplexere / nicht ausgerichtete Daten ungefähr gleich schnell.

Lalebarde
quelle
3

Wenn Sie die Software im Debug-Modus kompilieren, werden viele Compiler die Accessor-Funktionen des Vektors nicht inline. Dadurch wird die Implementierung des STL-Vektors unter Umständen, bei denen die Leistung ein Problem darstellt, viel langsamer. Dies erleichtert auch das Debuggen des Codes, da Sie im Debugger sehen können, wie viel Speicher zugewiesen wurde.

Im optimierten Modus würde ich erwarten, dass sich der stl-Vektor der Effizienz eines Arrays nähert. Dies liegt daran, dass viele der Vektormethoden jetzt inline sind.


quelle
Dies ist wichtig zu erwähnen. Das Profilieren von Debug-STL-Inhalten ist sehr, sehr langsam. Und es ist einer der Gründe, warum Menschen STL langsam machen.
Erik Aronesty
3

Die Verwendung eines std::vectorvs-Raw-Arrays hat definitiv Auswirkungen auf die Leistung, wenn Sie einen nicht initialisierten Puffer möchten (z. B. als Ziel für memcpy()). An std::vectorinitialisiert alle seine Elemente mit dem Standardkonstruktor. Ein Raw-Array wird nicht.

Die c ++ - Spezifikation für den std:vectorKonstruktor, der ein countArgument annimmt (es ist die dritte Form), lautet:

`Erstellt einen neuen Container aus einer Vielzahl von Datenquellen, optional unter Verwendung eines vom Benutzer bereitgestellten Allokator-Allokations.

3) Konstruiert den Container mit der Anzahl der standardmäßig eingefügten Instanzen von T. Es werden keine Kopien erstellt.

Komplexität

2-3) Linear in der Zählung

Für ein Raw-Array fallen diese Initialisierungskosten nicht an.

Siehe auch Wie kann ich vermeiden, dass std :: vector <> alle seine Elemente initialisiert?

Bernie
quelle
2

Der Leistungsunterschied zwischen den beiden ist sehr stark von der Implementierung abhängig. Wenn Sie einen schlecht implementierten std :: vector mit einer optimalen Array-Implementierung vergleichen, gewinnt das Array, dreht es jedoch um und der Vektor gewinnt ...

Solange Sie Äpfel mit Äpfeln vergleichen (entweder haben sowohl das Array als auch der Vektor eine feste Anzahl von Elementen oder beide werden dynamisch in der Größe geändert), würde ich denken, dass der Leistungsunterschied vernachlässigbar ist, solange Sie die STL-Codierungspraxis befolgen. Vergessen Sie nicht, dass Sie mit Standard-C ++ - Containern auch die vorgefertigten Algorithmen verwenden können, die Teil der Standard-C ++ - Bibliothek sind. Die meisten von ihnen sind wahrscheinlich leistungsfähiger als die durchschnittliche Implementierung desselben Algorithmus, den Sie selbst erstellt haben .

IMHO gewinnt der Vektor in einem Debug-Szenario mit einer Debug-STL, da die meisten STL-Implementierungen mit einem geeigneten Debug-Modus zumindest die typischen Fehler hervorheben / kathcieren können, die von Menschen bei der Arbeit mit Standardcontainern gemacht wurden.

Vergessen Sie nicht, dass das Array und der Vektor dasselbe Speicherlayout verwenden, sodass Sie Vektoren verwenden können, um Daten an älteren C- oder C ++ - Code zu übergeben, der grundlegende Arrays erwartet. Denken Sie jedoch daran, dass die meisten Wetten in diesem Szenario ungültig sind und Sie sich wieder mit dem Rohspeicher beschäftigen.

Timo Geusch
quelle
1
Ich denke , dass die Leistungsanforderungen (O (1) Lookups und Einfügungen) gerecht zu werden, Sie fast haben zu implementieren , um std :: vector <> dynamische Arrays verwendet wird . Dies ist sicherlich der naheliegende Weg, dies zu tun.
dmckee --- Ex-Moderator Kätzchen
Nicht nur die Leistungsanforderungen, sondern auch die Anforderung, dass die Speicherung zusammenhängend ist. Bei einer fehlerhaften Vektorimplementierung werden zu viele Indirektionsebenen zwischen dem Array und der API platziert. Eine gute Vektorimplementierung ermöglicht Inline-Code, SIMD für Schleifen usw.
Max Lybbert
Eine schlechte Vektorimplementierung wie beschrieben würde dem Standard nicht entsprechen. Wenn Sie eine Indirektion wünschen, std::dequekann diese verwendet werden.
Phil1970
1

Wenn Sie die Größe nicht dynamisch anpassen müssen, haben Sie den Speicheraufwand zum Speichern der Kapazität (ein Zeiger / size_t). Das ist es.

Greg Rogers
quelle
1

Es kann einen Randfall geben, in dem Sie einen Vektorzugriff innerhalb einer Inline-Funktion innerhalb einer Inline-Funktion haben, bei dem Sie über das hinausgegangen sind, was der Compiler inline macht, und einen Funktionsaufruf erzwingen. Das wäre so selten, dass man sich keine Sorgen machen sollte - im Allgemeinen würde ich litb zustimmen .

Ich bin überrascht, dass dies noch niemand erwähnt hat - machen Sie sich keine Sorgen um die Leistung, bis sich herausgestellt hat, dass es sich um ein Problem handelt, und setzen Sie dann einen Benchmark.

Mark Ransom
quelle
1

Ich würde argumentieren, dass das Hauptanliegen nicht die Leistung, sondern die Sicherheit ist. Sie können mit Arrays viele Fehler machen (z. B. Größenänderung in Betracht ziehen), bei denen ein Vektor Ihnen viel Schmerz ersparen würde.

Gabriel Isenberg
quelle
1

Vektoren verwenden ein kleines bisschen mehr Speicher als Arrays, da sie die Größe des Arrays enthalten. Sie erhöhen auch die Festplattengröße von Programmen und wahrscheinlich den Speicherbedarf von Programmen. Diese Erhöhungen sind winzig, können jedoch von Bedeutung sein, wenn Sie mit einem eingebetteten System arbeiten. Obwohl die meisten Stellen, an denen diese Unterschiede von Bedeutung sind, Orte sind, an denen Sie C anstelle von C ++ verwenden würden.

Brian
quelle
2
Wenn dies wichtig ist, verwenden Sie offensichtlich keine Arrays mit dynamischer Größe. Daher müssen Ihre Arrays die Größe nicht ändern. (Wenn ja, würden Sie die Größe irgendwie speichern). Daher können Sie auch boost :: array verwenden, es sei denn, ich irre mich - und warum sagen Sie, dass dies irgendwo "die Größe speichern" muss?
Arafangion
1

Der folgende einfache Test:

Erklärung des Leistungstests für C ++ Array vs Vector

widerspricht den Schlussfolgerungen aus "Vergleich des Assembler-Codes, der für grundlegende Indizierungs-, Dereferenzierungs- und Inkrementierungsoperationen für Vektoren und Arrays / Zeiger generiert wurde".

Es muss einen Unterschied zwischen den Arrays und Vektoren geben. Der Test sagt es ... probieren Sie es einfach aus, der Code ist da ...

Hamed100101
quelle
1

Manchmal sind Arrays tatsächlich besser als Vektoren. Wenn Sie immer einen Satz von Objekten mit fester Länge bearbeiten, sind Arrays besser. Betrachten Sie die folgenden Codefragmente:

int main() {
int v[3];
v[0]=1; v[1]=2;v[2]=3;
int sum;
int starttime=time(NULL);
cout << starttime << endl;
for (int i=0;i<50000;i++)
for (int j=0;j<10000;j++) {
X x(v);
sum+=x.first();
}
int endtime=time(NULL);
cout << endtime << endl;
cout << endtime - starttime << endl;

}

wo die Vektorversion von X ist

class X {
vector<int> vec;
public:
X(const vector<int>& v) {vec = v;}
int first() { return vec[0];}
};

und die Array-Version von X ist:

class X {
int f[3];

public:
X(int a[]) {f[0]=a[0]; f[1]=a[1];f[2]=a[2];}
int first() { return f[0];}
};

Die Array-Version von main () wird schneller sein, da wir den Overhead von "new" jedes Mal in der inneren Schleife vermeiden.

(Dieser Code wurde von mir in comp.lang.c ++ gepostet).

duli
quelle
1

Wenn Sie Vektoren verwenden, um mehrdimensionales Verhalten darzustellen, gibt es einen Leistungseinbruch.

Verursachen 2d + -Vektoren einen Leistungseinbruch?

Das Wesentliche ist, dass jeder Subvektor mit Größeninformationen einen geringen Overhead aufweist und nicht unbedingt eine Serialisierung der Daten erfolgt (wie dies bei mehrdimensionalen c-Arrays der Fall ist). Dieser Mangel an Serialisierung kann mehr als nur Möglichkeiten zur Mikrooptimierung bieten. Wenn Sie mehrdimensionale Arrays erstellen, ist es möglicherweise am besten, std :: vector zu erweitern und Ihre eigene Funktion zum Abrufen / Setzen / Ändern der Größe von Bits zu verwenden.

Seph Reed
quelle
0

Unter der Annahme eines Arrays mit fester Länge (z. B. int* v = new int[1000];vs std::vector<int> v(1000);, wobei die Größe vauf 1000 festgelegt bleibt) ist die Geschwindigkeit, auf die wirklich zugegriffen werden kann (oder zumindest für mich, wenn ich mich in einem ähnlichen Dilemma befand), die Geschwindigkeit des Zugriffs auf ein Array Element. Ich habe den Vektorcode der STL nachgeschlagen und Folgendes gefunden:

const_reference
operator[](size_type __n) const
{ return *(this->_M_impl._M_start + __n); }

Diese Funktion wird mit Sicherheit vom Compiler eingebunden. Solange Sie also vnur den Zugriff auf seine Elemente planen, operator[]sollte es keinen wirklichen Leistungsunterschied geben.

Subh_b
quelle