Größenänderung versus push_back in std :: vector: vermeidet es eine unnötige Kopierzuweisung?

Question

Beim Aufrufen der Methode push_back von std::vector wird die Größe um eins erhöht, was die Erstellung einer neuen Instanz impliziert, und dann wird der übergebene Parameter in dieses kürzlich erstellte Element kopiert, richtig? Beispiel:

myVector.push_back(MyVectorElement()); 

Na dann, wenn ich die Größe des Vektors mit einem Elemente einfach mit den Standardwerten erhöhen will, wäre es nicht besser, anstatt die resize Methode zu verwenden? Ich meine, wie folgt aus:

myVector.resize(myVector.size() + 1); 

Soweit ich sehen kann, das genau das Gleiche erreichen würde würde aber die völlig unnötige Zuordnung Kopie der Attribute des Elements vermeiden.

Ist diese Argumentation richtig oder fehlt mir etwas?

Answer 1

Zumindest bei GCC ist es egal, welche Sie verwenden (Ergebnisse unten). Wenn Sie jedoch zu dem Punkt kommen, an dem Sie sich darüber Gedanken machen müssen, sollten Sie Zeiger oder (noch besser) eine Form von smart pointers. verwenden. Ich würde natürlich the ones in the boost library empfehlen.

Wenn Sie wissen wollen, was besser war in der Praxis zu verwenden, würde ich vorschlagen, entweder push_back oder reserve als Resize wird der Vektor jedes Mal, es ist die Größe genannt, wenn es die gleiche Größe wie die gewünschte Größe. push_back und Reserve wird nur die Größe des Vektors bei Bedarf ändern. Das ist eine gute Sache, als wenn Sie die Größe des Vektors auf size+1 ändern möchten, könnte es bereits bei size+20 sein, so dass das Aufrufen der Größenänderung keinen Nutzen bringen würde.

Testcode

#include <iostream> 
#include <vector> 

class Elem{ 
    public: 
     Elem(){ 
      std::cout << "Construct\n"; 
     } 
     Elem(const Elem& e){ 
      std::cout << "Copy\n"; 
     } 
     ~Elem(){ 
      std::cout << "Destruct\n"; 
     } 
}; 


int main(int argc, char* argv[]){ 
    { 
     std::cout << "1\n"; 
     std::vector<Elem> v; 
     v.push_back(Elem()); 
    } 

    { 
     std::cout << "\n2\n"; 
     std::vector<Elem> v; 
     v.resize(v.size()+1); 
    } 
} 

Test Output

1 
Construct 
Copy 
Destruct 
Destruct 

2 
Construct 
Copy 
Destruct 
Destruct 

Answer 2

Ich vermute, dass die tatsächliche Antwort ist stark abhängig von der STL-Implementierung und Compiler verwendet, jedoch ist die „Größe ändern“ Funktion hat den Prototyp (ref)

void resize(size_type num, TYPE val = TYPE()); 

die val impliziert Standard gebaut und kopiert in den neu zugewiesenen (oder möglicherweise zuvor zugewiesenen, aber nicht verwendeten) Speicherplatz über die Platzierung neu und den Kopierkonstruktor. Als solche beide Operationen die gleiche Abfolge von Aktionen erfordern:

1. Anruf Standardkonstruktors
2. zuweisen Raum
3. Initialise über einen Copykonstruktor

Es ist wahrscheinlich besser auf die klareren und generic aufzuschieben (in Bezug auf STL-Container) push_back, anstatt vorzeitige Optimierung anzuwenden - wenn ein Profiler eine push_back als Hotspot hervorhebt, dann ist die wahrscheinlichste Ursache die Speicherzuordnung, die am besten durch vernünftige Verwendung der Reserve gelöst wird.

Answer 3

Sie haben Recht, dass push_back nicht mindestens eine Kopie vermeiden kann, aber ich denke, dass Sie sich über die falschen Dinge Sorgen machen, aber resize wird auch nicht unbedingt besser (es kopiert den Wert seines zweiten Parameters, der standardmäßig eine Standardeinstellung ist) ohnehin temporär gebaut).

vector ist nicht der richtige Container für Objekte, die teuer zu kopieren sind. (Fast) alle push_back oder resize könnte potenziell dazu führen, dass jedes aktuelle Mitglied der vector kopiert wird, ebenso wie jedes neue Mitglied.

Answer 4

myVector.resize(myVector.size() + 1); 

wird einen leeren Konstruktor von MyVectorElement aufrufen. Was versuchst du zu erreichen? Um Speicherplatz in einem Vektor zu reservieren (und Speicherzuordnungsaufwand einzusparen) gibt es die reserve() -Methode. Sie können den Konstruktor nicht vermeiden.

Answer 5

push_back: Sie erstellen das Objekt und es wird in den Vektor kopiert.
Größe ändern: Der Vektor erstellt das Objekt mit dem Standardkonstruktor und kopiert es in den Vektor.

Geschwindigkeitsunterschied: Sie müssen Ihre Implementierung der STL und Ihres Compilers testen, aber ich denke, dass es keine Rolle spielt.

Answer 6

Ich finde myVector.push_back(MyVectorElement()); viel direkter und einfacher zu lesen.

Die Sache ist, resize skaliert nicht nur das Array und default-Konstrukt Elemente an diesen Orten; das ist genau das, was es standardmäßig ist. Es benötigt tatsächlich einen zweiten Parameter, aus dem für jedes neue Element eine Kopie erstellt wird, und dies ist standardmäßig T(). Im Wesentlichen sind Ihre beiden Codebeispiele genau gleich.

Answer 7

Wenn Sie push_back aufrufen, wird unter der Annahme, dass keine Größenanpassung des zugrunde liegenden Speichers erforderlich ist, die Klasse vector den Operator "Placement new" verwenden, um die neuen Elemente direkt zu kopieren. Die Elemente in dem Vektor werden nicht werden standardmäßig erstellt, bevor kopiert werden.

Wenn Sie resize aufrufen, tritt fast die exakt gleiche Sequenz auf. vector reserviert Speicherplatz und kopiert dann den Standardwert über die Platzierung neu an jeden neuen Speicherort.

Die Konstruktion sieht wie folgt aus:

::new (p) _T1(_Val); 

Wo p der Zeiger auf den Vektor-Speicher ist, _T1 ist die Art in dem Vektor gespeichert wird, und _Val ist der „Vorgabewert“ Parameter (die Standardeinstellung _T1()).

Kurz gesagt, Größe ändern und push_back tun die gleichen Dinge unter den Abdeckungen, und die Geschwindigkeitsdifferenz würde aufgrund mehrerer interner Zuweisungen, mehrere Array-Grenzen-Prüfungen und Funktionsaufruf-Overhead sein. Die Komplexität von Zeit und Speicher wäre dieselbe.

Answer 8

Bei EA (Electronic Arts) wurde dies als ein so großes Problem angesehen, dass sie ihre eigene Version der STL, EASTL, geschrieben haben, die unter anderem eine push_back(void) in ihrer vector Klasse enthält.

Answer 9

Wenn Sie push_back() ausführen, überprüft die Methode den zugrunde liegenden Speicherbereich, um festzustellen, ob Speicherplatz benötigt wird. Wenn Platz benötigt wird, wird ein neues Gebiet für alle Elemente zugewiesen und die Daten werden in das neue Are kopiert.

ABER: Die Größe des neu zugewiesenen Speicherplatzes ist nicht nur ein Element größer. Es verwendet einen raffinierten kleinen Algorithmus, um den Raum zu vergrößern (ich glaube nicht, dass der Algorithmus als Teil des Standards definiert ist, aber er verdoppelt normalerweise den zugewiesenen Raum). Wenn Sie also eine große Anzahl von Elementen verschieben, bewirkt nur ein kleiner Prozentsatz von ihnen tatsächlich, dass der zugrunde liegende Speicherplatz neu zugewiesen wird.

Zur Erhöhung der tatsächlich zuzuteilen den Raum manuell haben Sie zwei Möglichkeiten:

• Reserve()
  Dies erhöht tatsächlich den zugrunde liegenden Stauraum ohne Elemente zu dem Vektor hinzugefügt wird. Daher ist es weniger wahrscheinlich, dass zukünftige puah_back() 's erfordern, den Platz zu vergrößern.
• resize()
  Dies fügt dem Vektor Elemente hinzu oder entfernt sie, um die richtige Größe zu erhalten.
• Kapazität() Gibt die Gesamtzahl der Elemente an, die hinzugefügt werden können, bevor das zugrunde liegende Lager neu zugewiesen werden muss. Daher wird if ((capacity() - size())> 0) ein push_back nicht dazu führen, dass der Vektorspeicher neu zugewiesen wird.

Answer 10

A C++ 0x Perspektive in Bezug auf Testcode von Yacobi der akzeptierte Antwort:

1. einen move Konstruktor der Klasse hinzufügen:

   Elem(Elem&& e) { std::cout << "Move\n"; } 
   

   Mit gcc I "Move" statt bekommen von "Copy" als Ausgabe für push_back, die im Allgemeinen viel effizienter ist.

2. sogar etwas besser mit emplace Operationen (nehmen Sie die gleichen Argumente wie der Konstruktor):

   v.emplace_back()

Test Output:

1 
Construct 
Destruct 

2 
Construct 
Copy 
Destruct 
Destruct 

Answer 11

Offensichtlich Sie besorgt über Effizienz und Leistung.

Std :: Vektor ist eigentlich ein sehr guter Darsteller. Verwenden Sie die Reservemethode, um Speicherplatz vorab zuzuweisen, wenn Sie ungefähr wissen, wie groß der Speicherplatz sein könnte. Offensichtlich geht dies auf Kosten von potentiell verschwendetem Speicher, aber es kann sich durchaus auswirken, wenn Sie push_back viel benutzen.

Ich glaube, es hängt von der Implementierung ab, wie viel Speicher für einen Vektor reserviert ist, wenn überhaupt, oder wie viel für künftige Verwendung als Elemente reserviert ist. Worst-Case-Szenario ist, was Sie sagen - nur um ein Element zu einem Zeitpunkt wachsen.

Testen Sie einige Leistungstests in Ihrer App, indem Sie ohne die Reserve und damit vergleichen.