Perché Vector's size() e capacity() è diverso dopo push_back()

Question

Ho appena iniziato a imparare i vettori e poco confuso su size() e capacity() So poco di entrambi. Ma perché in questo programma entrambi sono diversi? anche array(10) sta facendo spazio per 10 elementi e inizializzare con 0.

Prima di aggiungere array.push_back(5)

Quindi array.size(); è 10 che è ok.

Quindi il array.capacity(); è 10 che va bene.

Dopo aver aggiunto array.push_back(5)

Così array.size(); è 11 che è ok (already 10 time 0 is added and then push_back add one more element 5).

Quindi array.capacity(); è 15 Perché? (is it reserving 5 blocks for one int?).

#include <iostream> 
#include <vector> 
int main(){ 
    std::vector<int> array(10); // make room for 10 elements and initialize with 0 
    array.reserve(10); // make room for 10 elements 
    array.push_back(5); 
    std::cout << array.size() << std::endl; 
    std::cout << array.capacity() << std::endl; 
    return 0; 
} 

Answer 1

La norma stabilisce che std::vector<T>::push_back() ha ammortizzato la complessità O(1). Ciò significa che l'espansione deve essere geometricamente, ad esempio raddoppiare la quantità di memoria ogni volta che è stata riempita.

Esempio semplice: sequenziale s in un std::vector<int>. Li archivierai tutti una volta e ne farai anche 31 se raddoppi la capacità ogni volta che finisce. Perché 31?Prima di memorizzare il secondo elemento, copia il primo; prima di memorizzare il terzo, copi gli elementi 1-2, prima di memorizzare il quinto, copi 1-4, ecc. Quindi copia 1 + 2 + 4 + 8 + 16 = 31 volte, con 32 negozi.

Fare l'analisi formale mostra che si ottengono O(N) negozi e copie per gli elementi N. Questo significa ammortizzato O(1) complessità per push_back (spesso solo un negozio senza una copia, a volte un negozio e una sequenza di copie).

A causa di questa strategia di espansione, si avrà size() < capacity() la maggior parte del tempo. Cerca shrink_to_fit e reserve per imparare come controllare la capacità di un vettore in un modo più fine.

Nota: con il tasso di crescita geometrica, qualsiasi fattore maggiore di 1 farà, e ci sono stati alcuni studi, sostenendo che 1.5 offre una migliore prestazione a causa di memoria meno spreco (perché ad un certo punto la memoria riallocata può sovrascrivere il vecchio memoria).

Answer 2

È per l'efficienza in modo che non debba espandere la struttura dati sottostante ogni volta che si aggiunge un elemento. cioè non dovendo chiamare delete/new ogni volta.

Answer 3

Il std::vector::capacity non è la sua dimensione effettiva (che viene restituita da size()), ma la dimensione della dimensione allocata interna effettiva.

In altri termini, è la dimensione che può raggiungere prima che sia necessaria un'altra ridistribuzione.

Non aumenta di 1 ogni volta che si esegue uno push_back per non chiamare una nuova riallocazione (che è una chiamata pesante) su ciascun elemento inserito. Si riserva di più, perché non sa se non farai altri push_back subito dopo, e in questo caso, non dovrà cambiare la dimensione della memoria allocata per i 4 elementi successivi.

Qui, 4 elementi successivi è un compromesso tra 1, che ottimizzerebbe l'allocazione di memoria al massimo ma rischierebbe un'altra riallocazione presto, e un numero enorme, che ti permetterebbe di fare molti push_back velocemente ma forse riserva molta memoria per niente.

Nota: se si desidera specificare una capacità da soli (se si conosce la dimensione massima del vettore, ad esempio), è possibile farlo con la funzione membro reserve.

Answer 4

Size() restituisce quanti valori hai nel vettore.

E capacity() restituisce la dimensione della capacità di memoria allocata indica quanti valori può contenere ora.

Answer 5

Utilizzando

std::vector<int> array(10); // make room for 10 elements and initialize with 0 

È realmente messi a tutti i dieci spazi con gli zeri. L'aggiunta di un elemento aggiuntivo ad annunci causerà l'espansione della capacità, grazie all'efficienza. Nel tuo caso è inutile chiamare la riserva di funzione perché hai istanziato lo stesso numero di elementi.

controllo this e this collegamento

Answer 6

Penso alla seguente domanda può dare maggiori dettagli circa la capacità di un vettore.

About Vectors growth

farò riferimento la risposta a domanda di cui sopra.

La strategia di crescita di capacity è necessaria per soddisfare il requisito di tempo costante ammortizzato per l'operazione push_back. Quindi, la strategia è progettata per avere una crescita esponenziale in genere quando lo spazio è carente. In breve, lo size del vettore indica il numero di elementi ora, mentre lo captacity mostra la sua capacità usata in push_back in futuro.