Introduzione alla Standard Template Library

Un programmatore C++ ha come prima necessità il poter utilizzare dei pacchetti di strutture dati preconfezionati che può utilizzare per gestire vettori, liste, stack e code. MFC di Microsoft contiene questi strumenti, ma il più delle volte non si ha bisogno di utilizzare questa enorme libreria di classi, per questo viene in soccorso una libreria che ha raccolto molto successo perché ottimizzata per la gestione delle strutture dati. STL ( Standard Template Library ) è il tentativo di affrontare i problemi di gestione delle strutture dati in C++, scritta originariamente da Alexander Stepanov e Meng Lee nei laboratori della Hewlett Packard di Palo Alto la libreria si è guadagnata in pochi anni un’adesione sempre maggiore da parte dei programmatori C++. Nonostante il suo utilizzo non sia per nulla immediato, il suo utilizzo è stato accettato dal linguaggio C++ standard nel 1994 ed alla libera implementazione originaria si stanno affermando delle versioni commerciali aggiornate; in questa serie di articoli sulla libreria, tutti gli esempi di codice saranno sviluppati con il Visual Studio di Microsoft.
I componenti principali della libreria sono:

• contenitori, come i vettori e liste, cioé classi che contengono collezioni di oggetti
• iteratori che servono a percorrere il contenuto delle classi contenitore
• algoritmi che definiscono procedure generiche come il sort o il binary search
• oggetti funzione che incapsulano appunto le funzioni
• allocatori che incapsulano diverse strategie di allocazione della memoria

Gli algoritmi di STL sono definiti generici poiché è possibile utilizzarli sia su strutture dati STL che su quelle primitive del C come array e stream. Per ottenere questo risultato gli algoritmi non agiscono direttamente sulle strutture dati, ma tramite delle entità chiamate iteratori che sono come i puntatori del C ed infatti gli algoritmi di STL possono operare su una lista tramite un iteratore e su un array tramite un puntatore. Alcuni contenitori di STL utilizzano dei semplici puntatori come iteratori. Gli allocatori di STL infine consentono di rendere indipendenti gli iteratori dalla dimensione dei puntatori ed offrono un sistema per gestire l’allocazione dinamica dei contenitori STL.
Una strategia per costruire un insieme di strutture dati in C++ è quella di utilizzare classi base polimorfiche e classi iteratore corrispondenti. Questo approccio implica però l’uso di molte funzioni virtuali inserite nelle classi che derivano da una classe comune, come ad esempio CObject per le librerie MFC di Microsoft, questo tipo di approccio si può etichettare come un tipo “monolitico”, utilizzato da molte altre librerie. Il problema principale di un approccio monolitico è la fragilità a fronte di errori di casting e performance, anche se quest’ultima in maniera inferiore. Alcune librerie di classi hanno risolto il problema del casting attraverso l’uso dei template, però in questo modo non è possibile utilizzare comunque librerie diverse da quella con sui si è partiti nello sviluppo dell’applicazione, in parole povere il riuso del codice. La libreria STL invece risolve il problema dell’overhead delle funzioni virtuali attraverso l’uso di classi contenitore come classi template, in modo da risultare sicure al typing e riusabili perché non è necessaria alcuna classe base. STL include classi template per due tipi di contenitore:

• contenitori sequenziali che contengono una collezione di oggetti in ordine lineare, abbiamo i template vector, list e deque. I vector sono i classici array dinamici, le liste sono liste di valori doppiamente linkate e le deque sono un compromesso tra array e liste, in pratica è concesso l’inserimento e la rimozione rapida in testa ed in coda.
• i contenitori associativi permettono la ricerca veloce sugli elementi secondo una chiave, abbiamo le classi set, multiset, map e multimap. I set ed i multiset implementano sequenze ordinate ad accesso associativo rapido con la differenza che i primi non ammettono elementi ripetuti, mentre i secondi ammettono chiavi ripetute. I map ed i multimap contengono coppie chiave-valore univoche per il primo ed anche ripetute per il secondo.

Con il passare del tempo la libreria si è sempre più accresciuta di contenitori e funzioni, per esempio sono state inserite le hash per i contenitori come set e map, per maggiori informazioni vi invito a leggere la guida di STL.
Giusto per tastare il terreno vi inserisco un semplice esempio di codice nell’utilizzo del contenitore vector di STL, inseriamo qualche valore e poi lo scorriamo.

#include <iostream>
#include <vector>
#include <iterator>

using namespace std;

int main(int argc, char* argv[])
{
   char c;

   vector e; // età delle persone
   e.push_back(12);
   e.push_back(6);
   e.push_back(24);
   e.push_back(2);

   vector::iterator i;
   for(i = e.begin(); i < e.end(); i++)
      cout << *i << endl;    cin >> c;

   return 0;
}

Per quanto riguarda questo articolo introduttivo ci fermiamo qui, ma in futuro approfondiremo lo studio e l’uso di questa fantastica libreria.