Standard Template Library
Da Wikipedia, l'enciclopedia libera.
La Standard Template Library (STL) è una libreria software inclusa nella libreria standard del linguaggio C++ e definisce strutture dati generiche, Iteratori e algoritmi generici.
Indice |
[modifica] Descrizione
La STL costituisce uno strato software ormai divenuto fondamentale per i programmatori C++, cui fornisce un set precostituito di classi comuni, come container e array associativi, che hanno la caratteristica di poter operare con qualsiasi tipo di dato, sia primitivo che definito dall'utente, richiedendo allo sviluppatore nel contratto il rispetto di pochi vincoli (ad esempio, l'implementazione di operatori o funzioni di assegnamento o confronto) offrendogli in cambio classi complete di tutte le funzioni e operazioni elementari (ad es. in un container, copia, assegnamento, inserimento/rimozione, iterazione tra gli elementi) e pronte all'uso.
[modifica] Contenuti
[modifica] Contenitori
I contenitori della STL sono sequenziali e associativi. A loro volta, una parte dei contenitori sequenziali può essere definita come adattatori, in quanto sono in effetti delle interfaccie ridotte e specializzate dei contenitori principali. I contenitori standard sequenziali includono vector e list con deque, queue, priority_queue e stack come adattatori. I contenitori associativi sono set, muliset, map e multimap.
| Contenitore | Descrizione |
|---|---|
| sequenziali | |
| vector | un array dinamico, simile all'array del C (per esempio, capace di accesso casuale) con la capacità di ridimensionarsi automaticamente a causa dell'inserimento o della cancellazione di elementi. L'inserimento e la rimozione degli elementi nel/dal vector in coda viene effettuato in tempo costante. L'inserimento e la rimozione all'inizio o nel centro è compiuto in tempo lineare. |
| list | una lista bidirezionale; gli elementi non sono memorizzati in una memoria continua. Per questo motivo non è possibile accedere direttamente ad un elemento della lista accesso casuale, ma è necessario farlo tramite l'utilizzo di un iteratore. L'accesso agli elementi viene quindi effettuato con tempo lineare, tuttavia le operazioni di inserimento e cancellazione vengono effettuate in tempo costante. |
| associativi | |
| set | un insieme ordinato; l'inserimento e la cancellazione degli elementi in un insieme non invalida il puntamento degli iteratori nell'insieme. Le operazioni sono l'unione, intersezione, differenza, differenza simmetrica e il test di inclusione. |
| multiset | come per il set, ma consente la presenza di elementi duplicati. |
| map | un array associativo ordinato; consente la mappatura di un dato (chiave) e un'altro (valore). |
| multimap | come per la mappa, ma consente la presenza di chiavi duplicate. |
| hash_set hash_multiset |
simili al set, multiset, map o multimap, rispettivamente, ma implementati usando una tabella hash; le chiavi non sono ordinate, ma una funzione hash deve esistere per ogni tipo di chiave. Questi contenitori non fanno parte della Libreria Standard C++, ma sono inclusi nella estensione SGI della STL, e sono comunemente incluse come per esempio nella libreria del GNU C++, nel namespace __gnu_cxx. Potrebbero essere incluse nelle estensioni future dello standard C++. |
[modifica] Algoritmi
Numerosi algoritmi per eseguire operazioni come la ricerca e l'ordinamento sono forniti con la STL.
