Newsgroup: it.comp.lang.c++
Titolo: Prestazioni dei contenitori STL e libC++

Salve,
qualcuno qui dice che si dovrebbe sempre usare il VECTOR perchè è molto
performante e conviene SEMPRE all'uso di malloc/realloc/free o new/delete.
Mi stavo chiedendo: e gli altri contenitori ???
Per esempio il std::set contiene delle utili find(), ecc. Quando conviene
utilizzarli (con grandi qta di dati ?) e quali solo le loro prestazioni ???
Grazie,
Ciao Lvc@.

C'è qualcosa di interessante su...
http://www.yrl.co.uk/~phil/stl/stl.htmlx
Ciao, Luc.


Per ora ti so dire solo dei contenitori sequenziali (cioè quelli che
contengono una collezione ordinata di elementi dello stesso tipo) che sono:
vector, list e deque.
Il deque è caratterizzato dal fatto che inserisce ed elimina sempre
l'elemento in testa per cui è sicuramente da preferire se si vuole
implementare per es una coda.
Tutti e tre crescono dinamicamente e quindi la scelta dipende dagli
inserimenti e dagli elementi da inserire.
L'accesso casuale ad elementi del vettore si rivela efficiente perchè ogni
elemento è ad una distanza prefissata. D'altra parte però inserire un
elemento in una pos diversa dalla fine è molto inefficiente perchè andranno
riposizionati tutti gli elementi alla destra del nuovo elemento inserito.
In una lista invece non è efficiente l'accesso ad un elemento casuale perchè
bisognerà "scorrere" la lista stessa.
Ora:
° se si richiede accesso casuale agli elementi, ad una lista è preferibile
un vector;
° se è noto il numero degli elementi da inserire è meglio un vector;
° se si devono eliminare elem diversi dagli estremi è preferibile una list;
° se non si devono ins elementi all'inizio o alla fine è preferibile un
vector ad un deque.
Inoltre posso presentare un  raffronto fra vector e list.
----------------------------------------------------------------------------
----------------------------
tipo di dato                          dimensione in byte        capacità
dopo il primo ins
----------------------------------------------------------------------------
-----------------------------
int                                           4
256
double                                    8
128
cl semplice #1                      12
85
string                                      12
85
cl semplice grande                8000                                    1
cl complessa grande            8000                                     1
Il vector ha una sua capacità ( vettore.capacity() ) che dipende dal tipo di
dato.
Ogni volta che si arriva alla capacità indicata (per es dopo aver inserito
il 256° elemento) il contenitore dovrà ridimensionarsi.
Ora per piccoli oggetti se dobbiamo inserire 10.000.000 di elem avremo:
----------------------------------------------------------
tipo di dato                 lista                vettore
int                                 10.38             3.76
string                            14.42             11.80
I numeri sono il tempo in secondi.
Se dobbiamo inserire 10.000 oggetti grandi potremmo avere:
----------------------------------------------------------------------------
------
tipo di dato                                lista
vettore
classe semplice grande           0.36                               2.23
classe complessa grande        2.37                               6.70
Per classe complessa intendo una classe che implementi sia un costruttore
per copia sia un operatore di assegnamento per copia.
Quindi come si vede per oggetti grandi e complessi conviene di più una lista
perchè il vector ha bisogno di ridimensionarsi spesso (la prima tabella) e
il ridimensionamento funziona così:
si riserva nuovo spazio per il tipo di dati, si copia tutto nella nuova area
(le classi grandi invocheranno il costruttore per copia!).
Se proprio si vuole usare un vector anche in questi casi si possono inserire
puntatori agli oggetti e non gli oggetti stessi.
Ps: i dati delle tabelle non me li sono inventati e sicuramente non sono
sempre gli stessi, ma li ho presi dal Lippman\Lajoie
---Seek and Destroy---
Lvc@ <l.garull...@tin.it.removee> wrote in message
8lmocu$qab$1...@fe1.cs.interbusiness.it...
