amortizing in std :: vector :: Größe und std :: vector :: push_back

Wir wissen, dass die Neuzuweisung Mechanismus sorgt mehr Speicher der Zuteilung, die wir wirklich brauchen, wenn std::vector::push_back() anrufen. Normalerweise wächst die Kapazität mit dem Multiplikator 2x oder mit einer goldenen Verhältnis Zahl ~ 1,618 ...amortizing in std :: vector :: Größe und std :: vector :: push_back

Angenommen, wir Elemente hinzufügen wie folgt:

std::vector<int> v; 
for(unsigned i = 0; i < 100000; ++i) 
{ 
    v.resize(v.size() + 1); 
}

Ist sichergestellt, dass die Kapazität des Vektors " verdoppelt "wenn die Umverteilung stattfindet? Mit anderen Worten: wäre das „+1 Resize“ zuteilen dem Speicher die gleiche Art und Weise, wie es für push_back erfolgt.

Oder es ist ein reines Implementierung abhängig, was?

Quelle

2017-10-26 paceholder

ich nicht die Frage verstehen. Sie erwähnen bereits, dass die Kapazität normalerweise um den Faktor 2 (dh verdoppelt) ** oder ** goldener Wert wächst. – user463035818

@ tobi303 Ich denke OP fragt nach 'resize' im Vergleich zu' push_back'. –

@ChrisDrew ah ok, jetzt muss ich die Frage verstehen;), obwohl ich denke immer noch, es – user463035818

Ist garantiert, dass die Kapazität des Vektors verdoppelt wird, wenn die Neuzuordnung stattfindet?

Nein. Die Komplexität der Speicherreallokation wird konstant amortisiert. Ob die Kapazität des Objekts bei Bedarf verdoppelt oder um einen weiteren Faktor erhöht wird, hängt von der Implementierung ab.

würde das "+1 Resize" zuteilen dem Speicher die gleiche Art und Weise, wie es für push_back

Ja erfolgt.

std::vector::resize(size_type sz) anhängt sz - size() Wert initialisierten Elemente der Sequenz, wenn sz größer als size() ist. Das entspricht:

insert(end(), sz-size(), <value initialized object>);

std::vector::insert, std::vector::emplace und std::vector::push_back die gleiche Komplexität für Speicherzuweisung - abgeschrieben konstant.

Quelle

2017-10-26 15:34:39

verbessert werden könnte OP über 'resize' bittet. –

@ChrisDrew, siehe die aktualisierte Antwort. –

Da Ihr "Nein" nur als Antwort auf das Wort "verdoppelt" steht, und nicht als Antwort auf die Frage, die ich als OP bezweifle (ob die Größenänderung dasselbe amortisierte konstante Verhalten wie push_back hat), würde ich zur Klarstellung vorschlagen, Bewegen Sie Ihren letzten Satz (wo Sie erklären, dass andere Faktoren als 2 möglich sind) neben Ihrem ersten. Beachten Sie, dass das Wort "verdoppelt" in Anführungszeichen steht und das OP bereits andere mögliche Faktoren erwähnt und das Wort amortisiert in seinem Titel verwendet hat. –

Ein Vektor ist eine Folge Behälter, der (abgeschrieben) konstant Zeiteinsatz unterstützt, und Operationen am Ende löschen; [Vector.overview]

und

Wenn size() < sz, sz anhängt - size() default-eingefügten Elemente an die Sequenz.

für Resize. IMHO das heißt, ja, es ist gewährleistet, dass die Kapazität des Vektors ist „verdoppelt“, wenn die Umverteilung stattfindet

Quelle

2017-10-26 16:05:25

amortizing in std :: vector :: Größe und std :: vector :: push_back

Antwort

Verwandte Themen