Standard Template Library: differenze tra le versioni

Versione delle 23:33, 16 mag 2020

Versione attuale delle 14:40, 1 ago 2024

(4 versioni intermedie di 4 utenti non mostrate)

Riga 1:

La '''Standard Template Library''' ('''STL''') è una [[libreria software]] inclusaper nellail librerialinguaggio standarddi del linguaggioprogrammazione [[C++]] eche definisce [[strutturaquattro dati|strutturecomponenti dati]]principali: generichecontenitori, [[iteratore|iteratori]] e, [[algoritmo|algoritmi]] genericie [[Funtore (programmazione)|funtori]].

STL offre un insieme di [[classe (informatica)|classi]] C++. quali ad esempio i contenitori e gli [[Array associativo|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.

== Descrizione ==

La ''Standard Template Library'' (STL) è una [[Libreria (software)|libreria software]] per il [[linguaggio di programmazione]] [[C++]] che ha avuto una grande influenza nella realizzazione della C++ Standard Library. Fornisce quattro componenti: ''algorithms'' ([[Algoritmo|algoritmi]]), ''containers'' (contenitori), ''functions'' ([[Funzione (informatica)|funzioni]]) e ''iterators'' ([[Iteratore|iteratori]] - una generalizzazione dei [[Puntatore (programmazione)|puntatori]]).

STL è bastabasata sui [[template]], un approccio che permette il [[Polimorfismo (informatica)|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 (informatica)|astrazione]] senza perdita di efficienza, [[Architettura di von Neumann|modello di elaborazione]] di [[John von Neumann|Von Neumann]] e semantica dei valori.

STL offre un insieme di [[classe (informatica)|classi]] C++. quali ad esempio i contenitori e gli [[Array associativo|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.

Le STL (''Standard Template Library'') sonoè statestata progettateprogettata e sviluppatesviluppata presso la [[Hewlett-Packard]] da Alexander Stepanov e Meng Lee e sono state incluse nello standard ANSI/ISO nel 1995.

STL è basta sui [[template]], un approccio che permette il [[Polimorfismo (informatica)|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 (informatica)|astrazione]] senza perdita di efficienza, [[Architettura di von Neumann|modello di elaborazione]] di [[John von Neumann|Von Neumann]] e semantica dei valori.

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.

==Storia==

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 ==

=== Contenitori ===

I [[container (informatica)|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''.

{| class="wikitable" style="margin: 1em auto 1em auto"

Line 20 ⟶ 18:

! colspan="2"| Sequenziali

|-

|'''[[vector (STL)|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 <math>(O(1))</math>. L'inserimento e la rimozione all'inizio o nel centro e la ricerca vengono effettuate in tempo lineare <math>(O(n))</math>.

|-

|'''[[list (STL)|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 <math>(O(n))</math> così come la ricerca, tuttavia le operazioni di inserimento e cancellazione vengono effettuate in tempo costante <math>(O(1))</math>.

|-

! colspan="2"| Associativi

|-

|'''[[set (STL)|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 (STL)|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 <math>(O(log \ n))</math>. Non consente di assegnare più chiavi ad un singolo valore.

|-

|'''multimap'''

|come per la map, ma consente la presenza di chiavi duplicate.

|-

|'''hash_set'''<br />

'''hash_multiset'''<br />hash_map<br />hash_multimap

'''hash_map'''<br />

'''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]] <code>__gnu_cxx</code> o nel namespace std_ext di Visual Studio. Potrebbero essere incluse nelle estensioni future dello standard C++.

|}

Line 49 ⟶ 45:

=== 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 [[iteratore|iteratori]]. Molti di questi algoritmi operano su un intervallo del container definito dall'utente tramite due iteratori che indicano gli estremi dell'intervallo.

{{C++}}

{{portale|informatica}}

[[Categoria:Standard Template Library| ]]