Dal C al C++: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
|||
Riga 666:
== I contenitori standard ==
In linguaggio C, l'unico contenitore di oggetti predefinito è l'array di lunghezza fissa, che può essere multidimensionale.
Praticamente in qualunque programma non banale c'è l'esigenza di organizzare i dati in strutture dinamiche, cioè che occupano uno spazio definito in fase di esecuzione.
La libreria standard del C++ definisce alcune tipologie di contenitori, che possono soddisfare varie esigenze, anche se non tutte.
Si tratta di contenitori tipizzati, cioè, a differenza di molti linguaggi di programmazione orientati agli oggetti, un oggetto contenitore può contenere oggetti di un solo tipo.
Per implementare un contenitore tipizzato si deve usare un template di classe, in cui il parametro del template è il tipo degli oggetti contenuti.
Per esempio la seguente istruzione:
vector<int> a;
definisce la variabile "a" di tipo "vector<int>".
Il tipo "vector<int>" non è definito nella libreria standard. Quest'ultima definisce solo il template di classe "vector", ed è l'istruzione citata che ''istanzia'' il template creando in fase di compilazione la classe "vector<int>".
I contenitori principali definiti dalla libreria standard sono i segneti template di classe:
* '''vector''': è un array dinamico. L'oggetto contenitore contiene un puntatore a un buffer allocato dinamicamente. Gli elementi sono allineati in tale buffer. Aggiungendo oggetti in fondo al vector, vengono posti in tale buffer. Quando lo spazio del buffer è esaurito, automaticamente viene allocato un buffer più grande, l'intero vecchi buffer viene copiato nel nuovo buffer e si dealloca il vecchio buffer. Il suo scopo è permettere accessi indicizzati estremamente veloci e aggiunte di elementi in fondo abbastanza veloci.
* '''list''': è una lista a collegamento doppio (in inglese, "doubly-linked list"). Ogni nodo della lista è allocato autonomamente, e contiene un puntatore all'elemento successivo e un puntatore all'elemento precedente. Aggiungendo un elemento in cima, in fondo o in posizione intermedia, viene allocato un nuovo elemento e si impostano i puntatori in modo da mantenere la struttura di lista. Il suo scopo è permettere aggiunte ed eliminazioni veloci in qualunque punto della sequenza. Non consente accessi diretti, ma solo sequenziali in entrambe le direzioni.
* '''deque''': questa parola è l'abbreviazione dell'espressione inglese "Double-Ended QUEue", cioè coda a due estremità. Il suo scopo è permettere accessi diretti abbastanza veloci, e aggiunte ed eliminazioni veloci all'inizio o alla fine della sequenza.
* '''set''': è un insieme matematico ordinato di oggetti, cioè è una collezione ordinata priva di doppioni. È rappresentato da un albero di ricerca i cui nodi sono gli elementi contenuti. Quando si tenta di inserire un nuovo elemento, questo viene cercato nell'albero; se trovato, non viene in realtà inserito; se non trovato, viene inserito nella posizione che compete al suo valore. La ricerca per valore ha complessità logaritmica, a confronto della complessità libeare dei tre contenitori già presentati. Per poter ordinare gli elementi, è necessario che dati due elementi "a" e "b", sia definita l'espressione "a < b". Per esempio, questo è vero sia per i numeri predefiniti che per le stringhe, ma non per i numeri complessi.
* '''multiset''': è una struttura simile al "set", ma può contenenre più volte lo stesso oggetto. In realtà, per ogni oggetto viene mantenuto un contatore che indica quante volte è stato inserito un oggetto uguale a tale oggetto.
* '''map''': è un array associativo ordinato, chiamato anche "dizionario". Tale template è parametrizzato da due tipi: il tipo della chiave e il tipo del valore. È un "set" di associazioni chiave-valore, in cui il criterio di ricerca e di uguaglianza si basa solo sulla chiave.
* '''multimap''': è una struttura simile al "map", ma per ogni coppia chiave-valore c'è un contatore che indica quante volte è stata inserita tale coppia.
== I canali di ingresso/uscita ==
| |||