Salve a tutti.
Una cosa che mi ha sempre colpito del container C++ vector della STL è il modo con cui viene gestita la memoria, soprattutto in fase di eliminazione degli elementi (di cui avevo già parlato tempo fa).
Citando dalla solita Wikipedia:
“Erasing elements from a vector or even clearing it entirely does not necessarily free any of the memory associated with that element. The rationale here is that a good estimate of the future size of the vector is the maximum size of the vector since its creation.”
Questo fatto ha una sua logica: un vector è implementato come un array dinamico e quindi la sua espansione/contrazione comporta costi di riallocazione consistenti (perchè questa operazione comporta la creazione di un secondo array ed il “travasamento” dei dati dal primo), per cui si tende ad evitare di variarne in continuazione la dimensione.
Se prevedete continui cambiamenti di dimensione, il vector non è allora il container STL più appropriato per tale scopo (cfr. questa pagina per sceglierne uno migliore). 
In ogni caso, se vi serve recuperare memoria dopo aver rimosso un po’ di elementi, esiste un trucchetto semplice e relativamente efficiente.
Da Wikibooks:
std::vector <int> v; //... Lots of push_backs and then lots of remove on v. std::vector<int>().swap (v);
Nell’esempio abbiamo viene proposto un vector di interi che subisce una serie di inserimenti e cancellazioni.
L’ultima riga risolve il problema del recupero della memoria in stile C++: viene creato un nuovo vector anonimo e temporaneo (già questo è fantastico) dopodichè tramite la funzione swap() avverrà il travasamento efficiente dei dati.
Probabilmente l’utilità dell’esempio apparirà più chiara supponendo di avere un vector contenente strutture di grosse dimensioni tali per cui abbia davvero senso recuperare memoria…
Ciau!
Bel suggerimento, ma rimane la considerazione di fondo (alla base del comportamento del vector STL): se si ha bisogno di recuperare memoria sfruttando un trucchetto, probabilmente si sta sbagliando struttura dati!
Il vector e’ si dinamico, ma e’ pensato con dinamicita’ “direzionale”, ovvero e’ pensato soprattutto per crescere.
Le stesse strategie di allocazione dei blocchi di memoria sono probabilmente di tipo “moltiplicativo” o “esponenziale”, per evitare una eccessiva frammentazione della memoria.
L’uso piu’ efficiente del vector rimane comunque quando si abbia almeno una stima della dimensione del vettore, rendendo l’inserimento dei dati iniziali, e possibilmente i successivi, privo di riallocazione.
Insomma, la dinamicita’ dei vettori DTL deve servire un po’ da paracadute, pena perdita di efficienza…
Ciao Max.
Ho scritto il post perchè vedo i vector usati ovunque come se esistessero solo loro e penso che spiegarne i limiti intrinseci sia un fatto utile.
Quanto all’allocazione, suppongo avvenga effettivamente a blocchi ma non credo ci siano obblighi sull’algoritmo da usare a tale scopo (ho fatto una rapida ricognizione nei sorgenti della libstc++ partendo dal codice di vector – ho trovato pure il supporto sperimentale allo standard C++0x – e arrivando a new_allocator, ma poi mi son perso nelle varie inclusioni dei file header ^^’ )
Ciau! ^^