std :: vector di std :: vettori contiguità

Question

So che std::vector<T> memorizza internamente di dati in modo contiguo (a meno che sia std::vector<bool>) sia nella vecchia C++03 standard e la nuova C++11.

Belle domande StackOverflow che trattano questo e citano lo standard: answer, answer.

E i dati all'interno dei vettori nidificati std::vector <std::vector <T> >? Come viene memorizzato?

Se ogni vettore interno deve memorizzare i dati in modo contiguo, come può essere vero che &v[n] == &v[0] + n for all 0 <= n < v.size().

Per frase questo leggermente differente, è possibile l'accesso tutti gli elementi memorizzati in tale struttura annidata "semplicemente" e sequenzialmente (tramite un puntatore o simile) nello stesso modo può essere fatto per un vettore 1-D ?

Answer 1

No. Gli elementi di un vector sono memorizzati in un blocco di memoria assegnato dinamicamente; in caso contrario, la capacità di vector non può aumentare. L'oggetto vector contiene solo un puntatore a quel blocco.

Il requisito che gli elementi vengano memorizzati in modo sequenziale si applica solo agli elementi stessi e non ai membri allocati dinamicamente di tali elementi.

Answer 2

std::vector< std::vector<T> > è un vettore di oggetti, memorizzati in un blocco di memoria contiguo. Il fatto che questi oggetti siano anche vettori è irrilevante.

Sebbene gli elementi del vettore siano memorizzati nel blocco contiguo di memoria, la memoria in cui risiedono gli elementi non è la parte dell'oggetto vettoriale stesso.

"è possibile accedere a tutti gli elementi memorizzati in tale struttura nidificata" semplicemente "e in sequenza (tramite un puntatore o simile) nello stesso modo in cui può essere fatto per un vettore 1-D?"
Per accedere agli elementi di std::vector, è meglio usare operator[] o at() metodo di recuperare l'indirizzo del primo elemento e l'utilizzo dei puntatori. Per gli array multidimensionali rappresentati come vettore di vettori, ti suggerisco di stare con operator[], che è facile da usare e facile da leggere: myVector[i][j]. Vale la pena vedere vector::at vs. vector::operator[] :)

Answer 3

Per rispondere alla tua domanda finale: No. Gli elementi di un vettore di vettori non sono memorizzati in modo contiguo.

Si consideri il seguente codice:

std::vector<std::vector<int> > vv; 
.... fill in v[0], v[1], v[2], etc 
std::vector <int> & v = vv[1]; 
v.push_back (23); 

Se fossero tutti memorizzati in modo contiguo, allora questo potrebbe causare ogni elemento vv [2], vv [3], ecc per spostare. Come potrebbe funzionare, dal momento che stai influenzando un singolo vettore 'v'?

Answer 4

è possibile accedere a tutti gli elementi memorizzati in tale struttura nidificata "semplicemente" e in sequenza (tramite un puntatore o simile) nello stesso modo in cui può essere fatto per un vettore 1-D?

Sì, se:

• avete sempre e solo bisogno di aggiungere cose alla fine del vostro vettore di vettori, e

• siete disposti a sostituire il vettore i vettori costruiscono con una struttura dati personalizzata

Quello che puoi fare è quindi concatenare tutti i sub-vettori in un singolo buffer contiguo, con un altro buffer di indice utilizzato per accedere a questo dall'indice di ingresso di livello superiore.

Vedi my article here per più discussione su questo, e un esempio 'crollato vettore vettore' implementazione della classe ..