Container

Le classi container (contenitore) sono una delle applicazioni più usate del costrutto template in C++.

Una classe contenitore è una struttura dati che si presta alla gestione di oggetti dello stesso tipo, per mezzo di operazioni di inserimento, indicizzazione e cancellazione. Alcuni esempi di strutture dati assimilabili al concetto di contenitore sono liste, alberi e dizionari.

Le modalità di storage e di indicizzazione degli elementi variano in base al tipo di struttura dati. Tuttavia, data la loro funzione di mero contenitore, l'implementazione di queste classi, di norma, non fa uso di dati membro o metodi pubblici del tipo che manipola, ad eccezione di costruttori, costruttori di copia, costruttori di spostamento e distruttori.

Poichè in C++ in virtù del loro ruolo, a tali metodi è assegnato lo stesso nome della classe, ne consegue che il tipo è l'unica informazione strettamente necessaria per la definizione di una classe contenitore. Il loro uso quindi può essere liberamente esteso a qualunque classe definita al di fuori della libreria standard.

Questa caratteristica rende di fatto le classi contenitore il costrutto idiomatico principe della programmazione generica.

La Standard Template Library (STL) contiene l'implementazione di molteplici strutture contenitore che si prestano a vari casi d'uso, raggruppate in tre categorie principali:

• Sequenze che definiscono in maniera esplicita un ordinamento basato sull'uso di indirizzi di memoria degli elementi contenuti. Esempi di questa categoria sono list, vector e array.
• Contenitori associativi o collezioni di coppie chiave-valore ordinate per chiave come set e map, di modo da facilitare l'indicizzazione mediante ricerca basata su confronto.
• Hash table o collezioni di coppie chiave-valore non ordinate nè per indirizzi nè per chiave. Per questa categoria, un hash numerico univoco, calcolato a partire dalla chiave, è usato per calcolare l'indirizzo della locazione di memoria della tabella dove inserire il valore corrispondente. Idealmente, quando non avvengono collisioni di hash, ogni cella della tabella contiene un solo elemento, per cui le operazioni di accesso e lettura sono immediate. Esempi di questa categoria sono le classi unordered_set e unodered_map.

Il listato seguente mostra un esempio dell'uso della classe vector con elementi di una classe custom, e l'uso di metodi membro per la dimensione, il popolamento e l'accesso ai suoi elementi con modalità differenti, che saranno oggetto di approfondimento nelle lezioni successive.

#include <iostream>
    #include <vector>
    #include <algorithm> // std::for_each
     
    class MyElement
    {
        public:
        MyElement(int num) { id = num; }
        int getId() const { return id; }
         
        private:
        int id;
    };
     
    int main()
    {
        std::vector<MyElement> v;
        for (int i=0; i<10; i++)
        {
            v.emplace_back(MyElement(i));
        }
         
        std::cout << "Dimensione: " << v.size() << "\n";
         
        std::cout << "Scansione con ciclo for: ";
        for (int i=0; i<v.size(); i++)
        {
            std::cout << v[i].getId() << ' ';
        }
        std::cout << '\n';
         
        std::cout << "Scansione a ritroso con std::for_each: ";
        std::for_each(v.rbegin(), v.rend(), [] (MyElement& e) {
            std::cout << e.getId() << ' ';
        });
        std::cout << '\n';
         
        return 0;
    }

Requisiti di una classe container

Ogni classe soddisfa un sotto insieme di requisiti definiti dallo standard. Tali requisiti sono astrazioni espresse in forma discorsiva con lo scopo di fornire linea guida per l'implementazione effettiva della libreria standard. Alcuni esempi sono i concetti di sequenzialità, contiguità, accesso casuale e associatività.

Tuttavia, il requisito fondamentale che una classe container deve soddisfare è quello di garantire l'accesso ai suoi elementi mediante una struttura dati ausiliaria detta iteratore.

Ad ogni tipo di container corrisponde una tipologia di iteratori, che espone API per la lettura e scrittura degli elementi. Inoltre, in quanto astrazione del concetto di indice o puntatore, un iteratore definisce anche le operazioni di incremento o decremento, con modalità differenti in base al supporto offerto dal contenitore sottostante a tali operazioni, come vedremo meglio nelle lezioni successive.

API comuni

Contenitori differenti esibiscono prestazioni differenti per le operazioni di inserimento, accesso e ricerca. A seconda dei casi d'uso quindi, l'utilizzo di un contenitore può risultare più vantaggioso di altri.

Come accennato in precedenza, il concetto di contenitore si articola su molteplici livelli di astrazione, con il risultato che le classi container della libreria standard espongono un sotto insieme di API pubbliche identiche per nome e parametri, la cui semantica rispecchia di volta in volta le peculiarità del container specifico.

Allo stesso tempo, la libreria predispone molte funzioni di utilità generiche che consentono di manipolare container differenti. Ne sono esempio le classi adattatore stack e deque e gli algoritmi generici come find, transform e accumulate.

Questa "omogenietà" sul piano concettuale ha anche importanti ricadute pratiche. Ad esempio, consente di minimizzare le modifiche necessarie per passare dall'uso di un container ad un altro. Ciò risulta particolarmente utile quando vi è incertezza sulla scelta della metodologia di indicizzazione più adatta, o quando i requisiti cambiano in corso d'opera.

Innovazioni dello standard C++11 e successivi

L'introduzione dello standard C++11 ha rivoluzionato molti aspetti dell'uso delle classi template in generale, e le classi container della libreria standard non fanno eccezione.

Molte innovazioni riguardano l'uso del costruttore di spostamento al posto di quello di copia per ottimizzare alcune delle operazioni più comuni come, ad esempio, l'inserimento di elementi risultanti da valori temporanei mediante i metodi membro emplace ed emplace_back rispettivamente per le classi list e vector.

Alcune aggiunte vertono sulla predisposizione di strumenti sintattici alternativi ai costrutti di più basso livello, derivanti dal retaggio del linguaggio C. Ad esempio la classe array costituisce un alternativa type-safe all'uso di array a dimensione fissa in stile C.

Altre riguardano sostanziali miglioramenti alla leggibilità e manutenibilità del codice, come la parola chiave auto, le espressioni lambda e i cicli for su intervalli di iteratori. Molti di questi aspetti verranno analizzati nelle lezioni successive in relazione all'uso di classi contenitore.