STL e Container

STL sta per Standard Template Library, ovvero una libreria di classi basate su template. Particolarmente utili sono i containers che STL mette a disposizione, ovvero dei contenitori di oggetti, ognuno con caratteristiche diverse, dei pro e dei contro.

E’ molto importante sapere quale container utilizzare in ogni situazione, perchè sbagliando il container ne potremmo perdere molto in prestazioni, magari vanificando gli sforzi fatti per ottenere perfomance in altri punti del nostro programma.

I container non sono altro che contenitori dinamici di oggetti, ovvero si ridimensionano a nostro piacimento quando aggiungiamo o togliamo elementi, togliendoci l’onere di gestione che avevamo con gli array statici, a cui dobbiamo dare una dimensione fissa al momento della dichiarazione. la parola “template” indica che quando si crea un container bisogna specificare il tipo di elementi che dovrà contenere, in modo che il container sappia come trattarli. Questo li rende molto flessibili perchè con un ristretto numero di tipi di container abbiamo un numero grandissimo di possibilità.

I container sono di due tipi: associativi o sequenziali. Quelli sequenziali si basano sul concetto che ciascun elemento abbia una posizione specifica rispetto agli altri (è il primo, è l’ultimo, è il quinto), mentre quelli associativi si preoccupano di associare un elemento a una chiave, prescindendo dall’ordine effettivo in cui gli elementi si trovino nel container.

Queste due particolarità sono già il primo criterio di scelta di un container: sceglieremo un container sequenziale quando ad esempio cicleremo molto spesso il container (esempio: ogni tot secondi devo rigenerare dei punti vita a un’armata di soldati), useremo un container associativo quando dobbiamo accedere frequentemente a degli elementi specifici del container, in quanto i container associativi sono organizzati secondo un albero binario, per cui la ricerca di un elemento al loro interno ha una complessità O(log n) che è minore di una ricerca sequenzale, che ha complessità O(n). Per approfondire gli alberi binari, Albero binario da Wikipedia

Altri aspetti importanti da tenere presente:

1. aggiungendo un elemento ad un container, viene fatta una copia dell’oggetto e salvata nel container.

2. il container non si occupa di eliminare gli oggetti, per cui prima di eliminare il container, vanno distrutti a mano gli oggetti al suo interno.

Vediamo ora i container più comuni:

1. Vector

Il vector è un container sequenziale, ed ha lo stesso comportamento di un normale array, salvo che non dobbiamo decidere a priori la sua lunghezza. Sarà infatti il container ad auto adattarsi in base al numero di elementi che inseriamo al suo interno.

Dietro le quinte, il vector utilizza in effetti un array statico. Quando inseriamo un elemento in più di quelli che l’array può contenere, il vector si occupa di creare un array più grande, di una dimensione proporzionale al numero di elementi contenuti, e copiare tutti gli elementi dal vecchio al nuovo array.

Basandosi su un singolo array, gli elementi allocati in memoria sono contigui, e questo rende molto veloce l’iterazione degli elementi e l’accesso tramite indice agli elementi (accesso casuale), e consente inoltre di utilizzare l’aritmetica dei puntatori (dato un puntatore p, posso fare p++, p–, ecc)

Quando rimuoviamo elementi, la memoria già allocata rimane tale, come vale per un normale array, per cui in termini di risorse utilizzate, più aggiungiamo elementi e più la memoria occupata aumenta, senza mai diminuire fino alla distruzione del vector stesso.

Quando inseriamo un elemento in testa o in mezzo a due altri elementi, il vector è meno performante di altri container perchè gli elementi successivi a quello inserito devono essere tutti spostati di un posto verso la coda, e questo richiede tempo. La stessa cosa vale per la cancellazione di elementi in testa o in mezzo, che comporta lo spostamento di un posto verso la testa di ciascun elemento a partire da quello eliminato.

vediamo i costruttori e i metodi del vector, ma più in generale della maggior parte dei container, a parte casi specifici di alcuni container.

il vector ha una size , ovvero il numero di elementi realmente contenuti al suo interno, e una capacity, ovvero il numero massimo di elementi che si possono inserire prima che il vector si ridimensioni  (di norma del doppio dell’attuale capacità).

costruttori di un vector:

vector<int> v; // costruttore senza parametri, istanzia un vector di interi (<int>) di size = 0 e capacity = 0

vector<int> v[5];  // istanzia un vector in cui vengono inseriti 5 elementi inizializzati chiamando il loro costruttore di default  in base al tipo specificato

vector<int> v[5,2]; // istanzia un vettore di 5 elementi interi di valore 2

vector<int> v[begin,end]; // istanzia un vettore copiando elementi compresi tra due puntatori o due posizioni di iteratore (equivalenti di fatto a puntatori) che fanno da indirizzi di inizio e fine da cui copiare gli elementi. Da notare che l’indice indicato come inizio è compreso nella copia degli elementi, mentre l’indice di fine è escluso

metodi di un vector:

.size() // numero di elementi contenuti

.capacity // numero di elementi che può contenere senza doversi ridimensionare

.push_back() // aggiunge un elemento in coda

.back() // restituisce l’ultimo elemento

.front() //restituisce il primo elemento

.reserve(int) // imposta la capacity, utile per controllare manualmente la memoria allocata dal vector

.pop_back() // toglie un elemento in coda

.remove() // rimuove un elemento, ma la memoria rimane allocata. se l’elemento è in mezzo, vengono spostati gli elementi dalla coda alla testa per riempire i vuoti, e gli slot in coda rimangono allocati

.erase(index) // cancella effettivamente l’elemento, liberando anche la memoria.

.clear() elimina tutti gli elementi del vettore, la capacity rimane ovviamente uguale

.at[index] restituisce l’elemento presente alla posizione indicata con index, lancia un’eccezione se l’indice non è compreso tra i limiti del vector, ovvero tra 0 e .size()-1

2.Deque

Deque sta per double-ended queue, ovvero coda a due estremi. Anch’esso sequenziale, è ottimizzato per inserire e rimuovere elementi sia in testa che in coda. Quando un deque è pieno, viene allocata ulteriore memoria sia in testa che in coda, di cui viene tenuta traccia con un array di puntatori, per passare da un blocco all’altro di memoria nelle operazioni di lettura e scrittura.
Un vantaggio del deque rispetto al vector è negli inserimenti in testa, perchè il deque non deve spostare tutti gli elementi verso la coda perchè li salva in un nuovo blocco di memoria, salvandosi anche il percorso che deve fare per saltare da un blocco all’altro in modo ordinato.
Un altro vantaggio rispetto al vector è che rimuovendo elementi dal deque, quando un intero blocco di memoria si libera, viene deallocato e quindi rilasciato dalla memoria, a differenza del vector che non si restringe mai una volta espanso.

Il deque aggiunge principalmente due metodi a quelli già visti nel vector:

.push_front() // inserisce un elemento in testa

.pop_front() // rimuove un elemento in testa

3.List

La list è un insieme sequenziale di elementi, ciascuno dei quali ha un puntatore al precedente e al successivo. Questo comporta la possibilità di poter salvare gli elementi non necessariamente in posizioni di memoria contigue, perchè in qualsiasi posto si trovino, ogni elemento sa dove si trova il suo prev e il suo next.
Il vantaggio di questa gestione della memoria è che l’inserimento in mezzo a due elementi è il più efficiente tra i container sequenziali, in quanto non serve nessuno spostamento degli elementi successivi, né in inserimento né in cancellazione, ma si vanno a modificare solo i puntatori a prev e next degli elementi coinvolti.
Lo svantaggio è che ogni elemento occupa, a parte la memoria necessaria per se stesso, anche lo spazio per i puntatori al next e al prev.
Non è inoltre possibile accedere tramite indice a un elemento.

Per quanto riguarda i metodi, i fondamentali della list sono quelli già visti per il vector e il deque.

4.Map

La map è un container associativo, ed è paragonabile ad un dizionario di coppie chiave/valore. In pratica ogni elemento è formato da un oggetto pair, che ha come membri “first” che contiene la chiave di ricerca e “second” che contiene l’elemento vero e proprio da conservare. Lo scopo di una map è quello di rendere molto efficiente l’accesso a un elemento a partire dalla sua chiave. Gli elementi di una map vengono ordinati in base ad un albero binario, che ad ogni inserimento o rimozione viene bilanciato per minimizzarne la complessità durante le ricerche. In una map non è possibile aggiungere elementi con la stessa chiave. E’ possibile invece farlo con la multimap, che è identica alla map ma accetta chiavi duplicate.

Questo vuol dire che mentre una map è molto efficiente per accedere frequentemente ad un elemento, è molto meno efficiente l’inserimento e la rimozione. Ne consegue che se si prevede di inserire e cancellare elementi di frequente, probabilmente la map non è la scelta giusta.

E’ stimato che la map sia più efficiente di un vector soltanto superati i 10 elementi, per cui anche questo è da tener presente scegliendo il tipo di container da usare.

A differenza degli altri container, per istanziare una map bisogna indicare due tipi invece che uno, che saranno il tipo della chiave e il tipo dell’elemento. Ad esempio per fare una map che come chiave abbia un numero e come elemento una stringa, possiamo scrivere map<int, string>.

Per costruire l’albero binario, del valore che verrà passato come chiave verrà calcolato l’hash, la cui efficienza è tanto maggiore quanto più semplice è la chiave. Specificando ad esempio come chiave un intero, avremo che l’hash di un intero è l’intero stesso, ed è quindi molto efficiente. Se specifichiamo invece un tipo complesso, il calcolo dell’hash sarà più lento. Abbiamo detto comunque che la map ha senso se ho un set di elementi che cambiano pochissimo nel tempo o non cambiano affatto, per cui l’eventuale hash iniziale per il calcolo dell’albero binario potrebbero non incidere cosi tanto sulle performance finali.

Il modo più esplicito per inserire valori in una map è quello di fare un pair, assegnare chiave e valore ai membri first e second del pair, e aggiungerlo quindi alla map, come segue:

map<int, string> m;

pair<first k, second v> v;

v.first = key

v.second = value;

m.insert(v);

// oppure

pair<int, int> p = make_pair(3,5);

m.insert(p);

5. Set

Il set è simile alla map, con la differenza che la chiave e il valore coincidono. ne consegue che, essendo anch’esso ordinato in modo binario, gli elementi sono automaticamente ordinati ad ogni inserimento e cancellazione in seguito al bilanciamento dell’albero binario.

dichiarando un set, oltre a specificare il tipo come tutti gli altri container, possiamo indicare un ordinamento diverso da quello di default, che è crescente.

Altra particolarità del set è che non accetta valori duplicati, in quanto essi stessi fanno da chiave di ricerca. E’ possibile inserire valori duplicati utilizzando il multiset al posto del set, che ha le stesse caratteristiche del set, salvo accettare anche valori duplicati.

6. Stack

Lo stack non è considerato propriamente un container puro, ma viene detto adattatore, perchè in effetti nella pratica non implementa un modo diverso di salvare dati, ma sfrutto un container esistente per ridefinire delle logiche specifiche di lettura e scrittura dati.

Uno stack è una PILA, ovvero un modo di immagazzinare dati in modalità LIFO (Last in, First Out). In una pila, come in una coda, gli elementi possono essere inseriti solo da un lato, e rimossi solo dallo stesso lato da cui vengono inseriti, da questo deriva che il primo elemento che entra nella pila sia per forza di cose l’ultimo ad uscirne, perchè dovendo uscire dallo stesso lato da cui è entrato, non può uscire finchè tutti quelli inseriti dopo di lui siano usciti.

Per default, lo stack utilizza un deque come base per il salvataggio dei dati, ma possiamo specificare noi che container usare in fase di dichiarazione, ad esempio con stack<int, vector<int>> dichiariamo uno stack di interi, indicando che al posto di deque vogliamo utilizzare un vector.

Gli unici metodi implementati per lo stack sono:

push() // inserisce un elemento in testa

pop() // rimuove un elemento dalla testa, senza restituire nessun esito o valore rimosso

top() // legge l’ultimo valore inserito, ovvero quello in testa in quel dato momento.

7.Queue

La queue implementa il concetto di coda, o di fila, per cui il primo elemento che entra nella coda è anche il primo ad uscirne, ovvero l’opposto dello stack. Anche la queue è un adattatore, e sfrutta di default un deque, ma possiamo indicare in fase di dichiarazione quale container usare, come per lo stack. 

I metodi implementati per la queue sono:

front() // restituisce il primo elemento entrato (quello in testa)

back()  // restituisce l’ultimo elemento entrato (quello in coda)

push_back() // inserisce un elemento in coda

pop_front() // rimuove in testa

 

Annunci
  1. Lascia un commento

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: