Come viene implementato C ++ std :: vector?

Ho usato molto std::vector , e recentemente mi sono posto questa domanda: “Come è implementato lo std::vector ?”

Ho avuto due alternative:

1) Elenco collegato, quindi rendere l’API come un accesso casuale (es. operator[] overload operator[] ).

2) Usando new , per esempio Foo* temp = new Foo[20] : Credo che facciano qualcosa del genere, ma poi solleva un’altra domanda. Assegnano sempre una memoria massima ( uint32_t ) per dare accesso casuale? (Questo è inefficiente in termini di memoria.)

O c’è qualcos’altro di cui dovrei essere a conoscenza?

È implementato utilizzando una matrice sottostante.

Non è ansible implementare uno std::vector con un elenco collegato perché lo standard garantisce che gli elementi nell’elenco siano conservati in memoria contigua.

Credo che sia la terza opzione. Non può semplicemente usare la new T[n] perché in tal caso dovrebbe effettivamente build tanti oggetti quanti ne assegna. Per esempio

 std::vector v; v.reserve(10); 

Se la tua implementazione finisse semplicemente con il new Foo[10] , avresti creato solo 10 istanze di Foo.

Invece utilizza il suo allocatore per allocare e deallocare la memoria non push_back (senza build oggetti) e, se necessario (ad esempio, quando si push_back effettivamente push_back oggetti) posiziona le istanze copiate in posizioni di memoria corrette nella sua riserva utilizzando il nuovo posizionamento e le rimuove con esplicito chiama al distruttore (cosa che faresti solo in combinazione con il posizionamento nuovo). La class allocatore fornisce i seguenti metodi per ciò che presumo utilizzino le implementazioni del vettore

  void construct(pointer p, const_reference val); Returns: new((void *)p) T(val) void destroy(pointer p); Returns: ((T*)p)->~T() 

(I “ritorni” probabilmente dovrebbero leggere “effetto” o simili.)

Ulteriori informazioni sul posizionamento nuovo

Usano un array allocato dynamicmente che viene rigenerato secondo necessità. È necessario utilizzare qualcosa come una matrice in modo che gli elementi siano contigui nella memoria, il che è garantito dallo standard.

Per inciso, un modo comune di ricomporre un array è raddoppiare le dimensioni secondo necessità. Questo è così che se si inseriscono n elementi al massimo vengono eseguite solo le ricrescite di O(log n) e al massimo O(n) spazio viene sprecato.

Puoi leggere una implementazione per te stesso presso SGI (dove STL è stato originariamente concepito).

Non esiste un modo in cui è implementato. Diverse implementazioni possono essere diverse, purché mantengano la semantica e soddisfino i requisiti.

In qualsiasi momento, ci deve essere una matrice primitiva di T per soddisfare i requisiti di contiguità. Tuttavia, l’assegnazione, la crescita, la riduzione e la liberazione spetta all’implementatore.

Puoi leggere l’implementazione per te, è proprio lì nel file di intestazione.

Posso dirti che nessuna implementazione usa liste collegate. Non sono coerenti con i requisiti dello standard.

La Sezione 23.2.4, ¶1 dello standard richiede che l’aritmetica sui puntatori in un vettore funzioni come con i puntatori in un array.

Gli elementi di un vettore sono memorizzati in modo contiguo, nel senso che se v è un vettore in cui T è un tipo diverso dal bool, allora obbedisce all’id quadro & v [n] == & v [0] + n per tutto 0 <= n

Ciò garantisce che lo spazio di archiviazione si trovi in ​​un array. Ovviamente, se ridimensionate la matrice per essere più grande, potrebbe essere spostato in memoria.

Una versione pedagogica (e quindi semplificata) di un contenitore chiamato “Vec” è discussa nel capitolo 11 del meraviglioso (introduttivo) libro “Accelerated C ++”. Quello che descrivono è una versione ridotta di std :: vector, ma penso che valga ancora la pena notare che:

1) implementano la loro class template in termini di array,

2) discutono di push_back in termini di trucco (menzionato sopra) di allocare più spazio di archiviazione di quanto è necessario e di tornare di più quando si esauriscono, e

3) usano allocator > per la gestione della memoria. Il nuovo operatore non è abbastanza flessibile in questo contesto, poiché alloca e inizializza la memoria.

Ripeto, tuttavia, che questo non significa che le implementazioni reali là fuori siano così semplici. Ma poiché "Accelerated C ++" è abbastanza diffuso, gli interessati possono trovare nel capitolo pertinente gli oggetti vettoriali in un modo che possono essere creati, copiati, assegnati e distrutti.

EDIT: Su una nota correlata, ho appena trovato il seguente post di Herb Sutter in cui commenta un precedente post del blog di Andrew Koenig, riguardante se uno dovrebbe essere preoccupato per gli elementi vettoriali che sono contigui nella memoria: Cringe no: Vectors sono garantiti per essere contigui .

Credo che l’STL utilizzi l’opzione n. 2 (o qualcosa di simile) perché è garantito che std :: vector <> memorizzi gli elementi nella memoria contigua.

Se stai cercando una struttura di memoria che non ha bisogno di usare memoria contigua, guarda std :: deque.

Non esiste alcuna matrice effettiva in alcuna implementazione decente (se esiste, non è ansible utilizzare alcun object senza un costruttore predefinito), ma solo la memoria non elaborata che viene allocata. Viene assegnato in un modo che di solito è lungo la linea del raddoppio ogni volta che è necessario espanderlo.

Il vettore utilizza quindi l’allocazione in loco per chiamare i costruttori della class nella posizione corretta dopo l’effettivo utilizzo di ogni slot effettivamente utilizzato.

Quando c’è l’espansione cercherà di riallocare sul posto (ma questo è un po ‘sciocco e normalmente non funziona, si pensi a Windows 98 compattazione dell’heap) ma di solito finirà per creare una nuova allocazione e copiare tutto.

Un vettore stl standard è sempre tutto insieme, ma non tutte le implementazioni funzionano in quel modo (lo so, dopo averne scritte alcune). Probabilmente nessuno è esattamente un elenco collegato, comunque.

Da quello che ho letto nei libri e dalla funzionalità di riserva e dal requisito che elementi di vettori siano contigui, questo è quello che penso potrebbe essere un modo ansible per implementare Vector.

1) Gli elementi dei vettori sono contigui, supportano l’accesso casuale a O (1) e i vettori dovrebbero essere compatibili con i C array. Questo significa che non ci sono elenchi concatenati.

2) Quando chiami riserva, riserva ulteriore memoria. Ma riserva chiama

 new T[newSize] 

per riservare più memoria. Altrimenti chiamerà costruttore predefinito. Come spiegato da uncleben ogni volta che viene chiamata reserve, la class vettoriale assegna più memoria non inizializzata nel suo allocatore (se necessario) e copia costruisce nuovi oggetti in quella memoria usando il nuovo posizionamento (se è stata allocata più memoria)

3) Inizialmente il vettore ha una capacità predefinita. per cui la memoria non inizializzata viene allocata quando viene costruito l’object vettoriale

4) push_back copy costruisce l’object nella prima posizione disponibile. Se necessario, più memoria deve essere allocata in modo simile a riserva