Come funziona C++ std :: vector?

Question

In che modo aggiungere e rimuovere elementi "ridimensiona" i dati? Come viene calcolata la dimensione del vettore (credo che sia tenuto traccia di)? Sarebbe gradita qualsiasi altra risorsa aggiuntiva per conoscere i vettori.

Answer 1

In termini di dimensionamento, ci sono due valori di interesse per un std::vector: size e capacity (accessibile tramite .size() e .capacity()).

.size() è il numero di elementi contenuti nel vettore, mentre .capacity() è il numero di elementi che possono essere aggiunti al vettore, prima che la memoria venga riallocata.

Se si .push_back() un elemento, la dimensione aumenterà di uno, fino a quando non si raggiunge la capacità. Una volta raggiunta la capacità, la maggior parte (tutte?) Le implementazioni, riallocare la memoria, raddoppiando la capacità.

È possibile prenotare una capacità utilizzando .riservare. Ad esempio:

std::vector<int> A; 
A.reserve(1);  // A: size:0, capacity:1 {[],x} 
A.push_back(0);  // A: size:1, capacity:1 {[0]} 
A.push_back(1);  // A: size:2, capacity:2 {[0,1]} 
A.push_back(2);  // A: size:3, capacity:4 {[0,1,2],x} 
A.push_back(3);  // A: size:4, capacity:4 {[0,1,2,3]} 
A.push_back(4);  // A: size:5, capacity:8 {[0,1,2,3,4],x,x,x} 

Riassegnazioni di memoria si verificherebbe a linee 4, 5 e 7.

Answer 2

Ho scritto un vettore in C++ un anno fa. Si tratta di un array con una dimensione impostata (ad esempio 16 caratteri) che viene espansa di tale importo quando necessario. Vale a dire, se la dimensione predefinita è di 16 caratteri e occorre memorizzare Hi my name is Bobby, raddoppierà la dimensione dell'array a 32 caratteri, quindi memorizzerà l'array di caratteri.

Answer 3

Il vettore ha solitamente tre puntatori. Se il vettore non è mai stato utilizzato, sono tutti 0 o NULL.

• Uno al primo elemento del vettore. (Questo è l'inizio() iterator)
• Soltanto all'ultimo elemento del vettore + 1. (questa è la fine() iterator)
• E un'altra all'ultima assegnato ma elemento inutilizzato + 1. (questo meno iniziale() è la capacità)

Quando un elemento viene inserito, il vettore assegna un po 'di spazio e imposta i puntatori. Potrebbe allocare 1 elemento o allocare 4 elementi. Oppure 50.

Quindi inserisce l'elemento e incrementa il puntatore dell'ultimo elemento.

Quando si inseriscono più elementi di quelli allocati, il vettore deve ottenere più memoria. Si spegne e ne prende un po '. Se la posizione della memoria cambia, deve copiare tutti gli elementi nel nuovo spazio e liberare il vecchio spazio.

Una scelta comune per il ridimensionamento è raddoppiare l'allocazione ogni volta che è necessario più memoria.

Answer 4

L'implementazione di std::vector è leggermente cambiata con C++ 0x e in seguito con l'introduzione della semantica di spostamento (vedere What are move semantics? per un'introduzione).

Quando si aggiunge un elemento in un std::vector che è già pieno allora il vector viene ridimensionato che comporta una procedura di assegnazione di un nuovo, più grande area di memoria, spostando i dati esistenti al nuovo vector, eliminando il vecchio vector spazio e quindi aggiungendo il nuovo elemento.

std::vector è una classe di raccolta nella libreria di modelli standard. Mettendo gli oggetti in vector, portandoli fuori, o con lo vector che esegue un ridimensionamento quando un elemento viene aggiunto ad un intero vector, tutti richiedono che la classe dell'oggetto supporti un operatore di assegnazione, un costruttore di copie e la semantica del movimento. (Vedere type requirements for std::vector nonché std::vector works with classes that are not default constructible? per i dettagli.)

Un modo di pensare std::vector è come stile C array di elementi contigui del tipo specificato quando il vector è definito che ha alcune funzionalità aggiuntive per integrarla nel standard Offerte di libreria di modelli. Ciò che separa uno da uno standard è che uno vector crescerà in modo dinamico man mano che gli elementi vengono aggiunti. (Vedere std::vector and c-style arrays nonché When would you use an array rather than a vector/string? per qualche discussione su differenze.)

Utilizzando std::vector consente l'utilizzo di altri componenti Standard Template Library, come gli algoritmi in modo da utilizzare std::vector viene fornito con un bel paio di vantaggi rispetto a uno stile di C array come si arriva a usa la funzionalità che esiste già.

È possibile specificare una dimensione iniziale se il massimo è noto in anticipo. (Vedere Set both elements and initial capacity of std::vector e Choice between vector::resize() and vector::reserve())

Le nozioni di base della rappresentazione fisica std::vector sono di un insieme di puntatori che utilizzano la memoria allocata dall'heap. Questi puntatori consentono le operazioni effettive di accesso ai elementi memorizzati nel vector, cancellazione di elementi dal vector, iterando il vector, determinare il numero di elementi, determinare le dimensioni, ecc

Poiché la rappresentazione fisica è memoria contigua , l'eliminazione di elementi può comportare lo spostamento di elementi rimanenti per chiudere eventuali fori creati dall'operazione di eliminazione.

Con moderno C++ spostare la semantica, il sovraccarico di std::vector è stato ridotto in modo tale che è in genere il contenitore predefinito che sarebbe stato utilizzato per la maggior parte delle applicazioni, come raccomandato da Bjarne Stroustrup nel suo libro The C++ Programming Language 4 ° Edizione che discute C + +11.