PDA

Visualizza la versione completa : [c++ stl]scelta container


giuseppe500
22-04-2010, 18:32
ciao.
Domanda banale:
Ho una struttura dati che deve poter contenere un array di n elementi che non so in anticipo.
Io ho messo un puntatore per questi array del tipo dell' array in modo da farlo puntare al primo elemento quando conosco il numero di elementi dell'array dopo aver dimensionato l'array.

Il problema che se non so in anticipo il numero di elementi e devo utilizzare un container per forza.
ecco, per questo tipo di casistiche in base a cosa scelgo un vector un set o una lista?
per il mio caso le performance non sono rilevanti , avro al max 15/16 elementi ma per un altra casistica in base a cosa bisogna scegliere il container nell' stl?

Grazie.

shodan
22-04-2010, 19:22
Il vector adatto se devi fare ricerche random al suo interno, oppure se accedi ai vari elementi con l'operatore []. In genere la prima allocazione interna del vector di 256 elementi (ma dipende dall'implementazione). Superata questa dimensione, viene allocato un nuovo buffer interno, ricopiati gli elementi dal vecchio al nuovo e liberato il buffer vecchio. Se devi inserire molti elementi, questo penalizza le prestazioni. L'ideale sarebbe predimensionare il vector con una dimensione nota, ma non sempre possibile.
Eventuali cancellazioni di dati nel mezzo del vector (tramite iteratori) penalizzano le prestazioni in quanto i dati vegono shiftati.

La lista adatta per fare ricerche sequenziali. Accedere a un elemento in mezzo a una lista, significa sempre scorrere tutti gli elementi dal primo. Ogni elemento viene allocato di volta in volta e questo permette di poter eliminare facilmente gli elementi in mezzo alla lista stessa (basta spostare due puntatori). Per moltissimi elementi, le prestazioni degradano a causa delle frequenti allocazioni.

La deque un misto dei due.

Tutto questo vale per oggetti puri, costruibili per copia. Per i puntatori a volte non ci si accorge nemmeno del calo di prestazioni (usando un allocatore fast, la cosa nemmeno si sente).

Se se incerto su cosa usare, puoi scegliere un container e misurare le prestazioni tramite un timer ( ad esempio QueryPerformanceCounter ).

Loading