Ist std :: vector :: insert reserve per Definition?

Question

Wenn Sie die insert Mitgliedsfunktion auf einem std::vector aufrufen, wird es reserve vor dem "Zurückschieben" der neuen Elemente? Ich meine, garantiert der Standard das oder nicht?

Mit anderen Worten soll ich tun es wie folgt aus:

std::vector<int> a{1,2,3,4,5}; 
std::vector<int> b{6,7,8,9,10}; 
a.insert(a.end(),b.begin(),b.end()); 

oder so:

std::vector<int> a{1,2,3,4,5}; 
std::vector<int> b{6,7,8,9,10}; 
a.reserve(a.size()+b.size()); 
a.insert(a.end(),b.begin(),b.end()); 

oder eine andere bessere Lösung?

Answer 1

Im Hinblick auf die Komplexität der Funktion [link]:

Linear von der Anzahl der Elemente eingefügt (Kopieren/Verschieben Bau) plus die Anzahl der Elemente nach der Position (bewegen).

Außerdem, wenn InputIterator im Bereich Einsatz (3) nicht mindestens eine vorderen Iterator Kategorie ist (dh nur ein Eingang Iterator) die neue Kapazität kann nicht im voraus bestimmt werden, und das Einsetzen entsteht in zusätzlicher logarithmischer Komplexität in der Größe (Neuzuweisungen).

Daher gibt es zwei Fälle:

• Die neue Kapazität bestimmt werden kann, deshalb werden Sie nicht
• Die neue Kapazität reservieren aufrufen müssen nicht ermittelt werden kann, damit ein Anruf zu reserve sollte nützlich sein.

Answer 2

Vom documentation, es scheint, dass:

Neuzuteilung Ursachen, wenn die neue Größe() größer ist als die alte Kapazität().

Beachten Sie auch, dass in einem solchen Fall alle Iteratoren und Referenzen ungültig sind.

Es versteht sich daher von selbst, dass Umschichtungen verantwortlich sind der insert und, wenn man sich diese Vorgänge zu der Zeit aussehen, es ist wie eine konsistente Reserve-size-plus-eins Betrieb bei jedem Schritt vorgenommen wird.
Sie können argumentieren, dass ein reserve Aufruf an der Spitze der Einfügung alles in jenen Fällen beschleunigen würde, wenn mehr als eine Umverteilung stattfindet ... Nun, richtig, es könnte helfen, aber es hängt meistens von Ihrem tatsächlichen Problem ab.

Answer 3

Wird std::vector::insert per Definition reserviert?

Ja, nein; hängt von der aktuellen Kapazität ab.

Vom Entwurf N4567, §23.3.6.5/1 ([vector.modifiers]):

Verursacht Neuzuteilung wenn die neue Größe größer als die alte Kapazität ist.

Wenn die zugeordnete Speicherkapazität im vector groß genug ist, um die neuen Elemente enthalten, sind keine zusätzlichen Mittel für die vector benötigt. Also nein, dann wird es keinen Speicher reservieren.

Wenn die Kapazität vector nicht groß genug ist, wird ein neuer Block zugewiesen, der aktuelle Inhalt wird verschoben/kopiert und die neuen Elemente werden eingefügt. Der genaue Zuweisungsalgorithmus ist nicht spezifiziert, würde aber typischerweise wie in der reserve()-Methode verwendet werden.

... oder ein anderer besserer Ansatz?

Wenn Sie sich über zu viele Zuweisungen betroffen sind, während Elemente in die vector Einfügen dann mit der Größe der Anzahl der erwarteten Elemente der reserve Aufruf der Methode hinzugefügt werden die Zuweisungen nicht minimiert.

Ruft die vectorreserve vor den/irgendwelchen Einfügungen? I.e. Ordnet es genügend Kapazität in einer einzigen Zuweisung zu?

Keine Garantien. Wie würde es den Abstand zwischen den Eingabe-Iteratoren wissen? Vorausgesetzt, dass das insert-Verfahren einen InputIterator (d. H. Single-Pass-Iterator) annehmen kann, hat es keinen Grund, die erwartete Größe zu berechnen. Könnte die Methode die Größe berechnen, wenn die Iteratoren etwas anderes (z. B. Zeiger oder RandomAccessIterator)? Ja könnte es. Wäre es? Hängt von der Implementierung und den Optimierungen ab.