Standard Template Library
La Standard Template Library (STL) è una libreria software inclusa nella libreria standard del linguaggio C++ e definisce strutture dati generiche, Iteratori e algoritmi generici.
Descrizione
La Standard Template Library costituisce uno strato software ormai divenuto fondamentale per i programmatori C++, cui fornisce un set precostituito di classi comuni, come, ad esempio, la classe string, iteratori, cioè una generalizzazione dei puntatori e oltre 70 potenti algoritmi per lavorare su tali strutture.
Storia
Le STL (Standard Template Library) sono state progettate e sviluppate presso la Hewlett-Packard da Alexander Stepanov e Meng Lee e cono state incluse nello standard ANSI/ISO nel 1995.
Contenuti
Contenitori
I contenitori della STL si dividono in sequenziali e associativi. A loro volta, una parte dei contenitori sequenziali può essere definita come adattatori, in quanto sono in effetti delle interfacce ridotte e specializzate dei contenitori principali che non implementano iteratori nella loro interfaccia. I contenitori standard sequenziali includono vector, list e deque. E comprendono gli adattatori queue, priority_queue e stack. I contenitori associativi sono set, multiset, 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. Gli elementi sono memorizzati su una porzione di memoria continua. L'inserimento e la rimozione degli elementi nel/dal vector in coda viene effettuato in tempo costante (O(1)). L'inserimento e la rimozione all'inizio o nel centro e la ricerca vengono effettuate in tempo lineare (O(n)). |
| 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 (O(n)) così come la ricerca, tuttavia le operazioni di inserimento e cancellazione vengono effettuate in tempo costante (O(1)). |
| Associativi | |
| set | un insieme ordinato che non consente duplicati; 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 rispetto alla chiave; consente la mappatura di un dato (chiave) associato ad un altro (valore). Entrambi i tipi di dato possono essere definiti dall'utente. Permette ricerche rapide rispetto alla chiave, l'accesso ai dati ha tempo logaritmico(O(log n)). Non consente di assegnare più chiavi ad un singolo valore. |
| multimap | come per la map, 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 o nel namespace std_ext di Visual Studio. Potrebbero essere incluse nelle estensioni future dello standard C++.
|
Algoritmi
Nella STL sono inclusi numerosi algoritmi per eseguire operazioni come la ricerca e l'ordinamento.tali algoritmi sono comunemente utilizzati per la manipolazione dei container in maniera indiretta, cioè solo tramite iteratori. Molti di questi algoritmi operano su un intervallo del container definito dall'utente tramite due iteratori che indicano gli estremi dell'intervallo.