Vettore bidimensionale in C ++ - inefficiente con vettori secondari di dimensioni dinamiche?

Question

Vettore bidimensionale in C ++ - inefficiente con vettori secondari di dimensioni dinamiche?

#1 da (6 voti)
#2 da (1 voti)
#3 da (0 voti)

1

So che std::vector usa un blocco contiguo di memoria, ma spesso vedo che le persone usano vettori di vettori, anche quando modificano il numero di elementi in questi vettori contenuti all'interno di un vettore esterno . Questo non porterà a problemi di efficienza quando un vettore interno deve essere ridimensionato poiché tutti i seguenti vettori dovranno spostare anche i loro elementi?

In altre parole, nel codice seguente, la crescita di lists[0] non determinerà lo spostamento degli elementi dei 99 sub vettori che seguono anche questo, e non solo lists[0] ?

std::vector<std::vector<int>> lists;
lists.resize(100);

// use and grow sub vectors
// ...
lists[0].push_back(88); // ← !

c++ c++11 stl

posta beta 08.05.2013 - 20:32

fonte

3 risposte

1

Ogni std::vector memorizza i suoi elementi in una allocazione heap contigua. Ciò significa che i dati dell'elemento sono separati dai dati del membro dell'oggetto (ricorda che gli% localmente dichiarati in% co_de sono allocati nello stack, non l'heap ...). Questo è ciò che permette a std::vector di essere ridimensionato dinamicamente - nota che C / C ++ non ha disposizioni per ridimensionare un std::vector !

Quindi, in una struct , la% esterna co_de memorizza una matrice di strutture a dimensione fissa di std::vector< std::vector<int> > nella sua allocazione dell'heap. Ognuno di questi vettori gestisce la propria matrice allocata su heap di std::vector , separatamente dal suo "genitore" o da uno dei suoi "fratelli".

risposta data 08.05.2013 - 21:42

fonte

0

Il meccanismo descritto da Timo è accurato, ma può essere utile considerare che cambiare vector.size() non può cambiare sizeof(vector) , perché quest'ultimo deve essere una costante in fase di compilazione.

Al contrario, se il tuo array 2D era realmente un% co_de contiguo, cambiando la larghezza sarebbe necessario riorganizzare tutto.

risposta data 08.05.2013 - 23:09

fonte

Leggi altre domande sui tag c++ c++11 stl

Se accetto i contributi con un CLA, posso scrivere "Copyright (c) My-Name"? È più efficiente imparare mentre si va avanti con un progetto o sviluppare un'ampia base di abilità di programmazione? [chiuso]

score 6 · Accepted Answer

std::vector memorizza i suoi elementi in un blocco contiguo di memoria come descritto, ma ciò non significa che l'intero oggetto vettoriale risieda in un pezzo contiguo di memoria. Sebbene dipenda dall'implementazione, è molto probabile presumere che l'oggetto vettoriale stesso contenga alcuni dati che sono per lo più "overhead di gestione" come la dimensione del vettore e un puntatore ai dati del payload invece dei dati del carico utile stesso. In questo modo è molto più facile eseguire assegnazioni o riallocazioni efficienti.

Ad esempio, se guardi all'implementazione vettoriale in Visual C ++, scoprirai che i suoi membri dati sono in realtà solo alcuni indicatori.

Quindi, nello scenario di un vettore di vettori, i dati memorizzati nel vettore "interno" contengono semplicemente i dati di gestione ma non il carico utile per il vettore annidato. Pertanto, l'estensione o il restringimento del vettore nidificato non causerà la migrazione di elementi nel vettore esterno nella memoria.