Standard Template Library

La Standard Template Library (STL) è una libreria software per il linguaggio di programmazione C++ che definisce quattro componenti principali: contenitori, iteratori, algoritmi e funtori.

STL offre un insieme di classi C++. quali ad esempio i contenitori e gli array associativi, che possono essere usati con qualunque tipo di dato – sia esso predefinito o costruito dall'utente – che supporti alcune istruzioni elementari (copia, assegnazione, ecc.). Gli algoritmi implementati in STL risultano indipendenti dai container, cosa che riduce significativamente la complessità della libreria.

STL è basata sui template, un approccio che permette il polimorfismo in fase di compilazione, nettamente più efficiente del polimorfismo in fase di esecuzione. STL fu la prima libreria di algoritmi e strutture dati generiche per il C++; si basa su quattro idee di fondo: programmazione generica, astrazione senza perdita di efficienza, modello di elaborazione di Von Neumann e semantica dei valori.

STL è stata progettata e sviluppata presso la Hewlett-Packard da Alexander Stepanov e Meng Lee e sono state incluse nello standard ANSI/ISO nel 1995.

STL e le idee contenute in essa, hanno avuto una notevole influenza nello sviluppo della C++ Standard Library con numerosi programmatori che hanno contribuito allo sviluppo di entrambe le librerie, malgrado ciò le due librerie sono rimaste distinte e nessuna delle due è un super-insieme definito dell'altra.

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 hash_map hash_multimap	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.