Standard Template Library: differenze tra le versioni

Versione delle 03:59, 17 gen 2007

Versione attuale delle 19:28, 7 giu 2025

(54 versioni intermedie di 42 utenti non mostrate)

Riga 1:

La '''Standard Template Library''' ('''STL''') è una [[libreria software]] inclusaper nellail [[librerialinguaggio standard]]di del linguaggioprogrammazione [[C++]] eche definisce quattro componenti principali: contenitori, [[struttura datiiteratore|strutture datiiteratori]] generiche, [[Iteratorealgoritmo|Iteratorialgoritmi]] e [[algoritmoFuntore (programmazione)|algoritmifuntori]] generici.

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 STL costituisce uno strato software ormai divenuto fondamentale per i programmatori [[C++]], cui fornisce un set precostituito di [[classe (informatica)|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 [[design by contract|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.

STL è basata 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.

==Contenuti==

===Contenitori===

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.

I [[container (informatica)|contenitori]] della STL sono sequenziali e associativi. I contenitori standard sequenziali includono ''vector'', ''deque'', e ''list''. I contenitori associativi sono ''set'', ''muliset'', ''map'' e ''multimap''.

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 [[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"

!Contenitore || Descrizione

|-

! colspan="2"| sequenzialiSequenziali

|-

|'''[[vector (STL)|vector]]'''

|un [[array dinamico]], simile all'[[array]] del C (per esempio, capace di [[accesso casuale]]) con la capacità di ridimensionarsi automaticamente a causecausa dell'inserimento o della cancellazione di nuovielementi. oggettiGli oelementi dellasono cancellazionememorizzati su una porzione di memoria continua. L'inserimento e la rimozione degli elemetielementi nel/dal vector in coda usaviene uneffettuato in tempo costante amortizzato<math>(O(1))</math>. L'inserimento e la rimozione all'inzioinizio o nel centro èe compiutola 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. LePer caratteristichequesto sonomotivo non è possibile accedere direttamente ad un elemento della lista [[accesso casuale]], ma è necessario farlo tramite l'oppostoutilizzo di quelleun del vector[[iteratore]]. Lento L'accesso (agli elementi viene quindi effettuato con tempo lineare <math>(O(n))</math> così come la ricerca, matuttavia velocele operazioni di inserimento e cancellazione (vengono effettuate in tempo costante <math>(O(1))</math>.

|-

! colspan="2"| associativiAssociativi

|'''deque''' (''double ended [[coda|queue]]'')

|un vector con le operazioni di inserimento e cancellazione all'inizio o alla fine amortizzate in tempo costante.

|-

|[[set (STL)|set]]

! colspan="2"| associativi

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

|'''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 (C++ containerSTL)|map]]'''

|un array associativo ordinato rispetto alla chiave; consente la mappatura di un dato (chiave) eassociato 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 mappamap, ma consente la presenza di chiavi duplicate.

|-

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

'''hash_multiset'''<br />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 esssereessere incluse nelle estensioni future dello standard C++.

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

Numerosi algoritmi per eseguire operazioni come la ricerca e l'ordinamento sono forniti con la STL.

{{C++}}

{{portale|informatica}}

[[Categoria:Programmazione]]

[[deCategoria:Standard Template Library| ]]

[[en:Standard Template Library]]

[[et:CPP-STL]]

[[fr:Standard Template Library]]

[[ja:Standard Template Library]]

[[ko:STL]]

[[nl:Standard Template Library]]

[[pl:Standard Template Library]]

[[pt:Standard Template Library]]

[[ru:Стандартная библиотека шаблонов]]

[[sv:STL]]

[[zh:标准模板库]]