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.

Descrizione[modifica | modifica wikitesto]

La Standard Template Library costituisce uno strato software ormai divenuto fondamentale per i programmatori C++, cui fornisce un set precostituito di classi comuni, come diverse implementazioni di contenitori, la classe string, iteratori, cioè una generalizzazione dei puntatori e oltre 70 potenti algoritmi per lavorare su tali strutture. Inoltre, sono disponibili i (multi)set e le (multi)map (array associativi).

Storia[modifica | modifica wikitesto]

Le STL (Standard Template Library) sono state progettate e sviluppate presso la Hewlett-Packard da Alexander Stepanov e Meng Lee e sono state incluse nello standard ANSI/ISO nel 1995.

Contenuti[modifica | modifica wikitesto]

Contenitori[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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.