Quinta lezione

Utilità delle strutture di dati standard

Abbiamo sicuramente familiarità con la nozione di insieme di oggetti, di vettore (magari solo di numeri o di caratteri, finora...), ma hanno utilità generale in informatica, e sono utilizzati praticamente da sempre, anche altri tipi di "contenitore". Ad esempio la lista:

Per quale ragione una lista di oggetti può essere più utile e conveniente di un vettore immagazzinato in un'area contigua di memoria? Quale è invece un possibile svantaggio ?

Se volessimo abbandonare questo modello a una dimensione (l'unico al momento supportato nella libreria standard C++) entreremmo nel magico mondo dei grafi, ai quali i colleghi informatici dedicano un intero corso teorico...
Quali sono le ragioni fondamentali che spingono a dedicare tanta cura alle strutture dati astratte, e ad inventare linguaggi (OO) che le concretizzano in oggetti/classi e vi associano le corrette procedure/metodi? Eccone alcune, tratte sostanzialmente dai volumi della serie Mastering Algorithms, di O'Reilly:

Efficienza. La scelta di una particolare struttura di dati dipende in primo luogo dall'utilizzo previsto. Quando ad esempio si raccoglie una grande quantità di dati al solo scopo di effettuare operazioni di ricerca (data mining), faremo meglio ad organizzare i dati in modo da permettere un'efficiente ricerca, utilizzando per esempio multilinked lists oppure alberi. Ha un impatto sull'efficienza anche la scelta della giusta associazione di dati nelle strutture: ha senso mettere assieme i dati che vengono letti o trasferiti assieme.
Astrazione. L'uso di strutture il cui funzionamento è ben compreso dalla maggior parte degli sviluppatori consente di concentrarsi solo sulle operazioni fondamentali "di alto livello" connesse al tipo di struttura (per esempio l'inserzione in una lista), e non sulla meccanica della singola operazione.
Possibilità di riutilizzo. La natura di una struttura dati non dipende dal suo contenuto. Una lista o un albero vengono implementati nello stesso modo, indipendentemente dai dati contenuti in ogni elemento.

Già in questa breve descrizione, si nota come la definizione di una struttura dati porti alla definizione di alcune operazioni standard per quel tipo di dati (inserzione e rimozione in una lista o in un grafo, attraversamento della lista o del grafo, eccetera). Queste operazioni sono talmente connaturate alla struttura dei dati che risulta opportuno associarle ai dati stessi, e considerarle una loro specifica "funzionalità". Come abbiamo visto, questo concetto viene fatto proprio ed esteso nei fondamenti della programmazione orientata agli oggetti.
Ma quali sono le buone ragioni per standardizzare una procedura, in modo che possa applicarsi a varie circostanze ed al mutare del tipo di dati considerato?

Efficienza. Alcuni problemi (esempio tipico: la ricerca e l'ordinamento dei dati) si ripresentano più e più volte in varie forme. E' forte la tentazione di scrivere una soluzione "leggermente diversa" in ogni caso, ma l'esperienza dimostra che la soluzione trovata analizzando il problema in modo isolato e formale, con il giusto tempo a disposizione, è sempre migliore e funziona in modo più economico.
Astrazione. Ancora, note le proprietà di una certa procedura (ad esempio: verificato che una procedura di ordinamento funziona per davvero) è sufficiente usarla, concentrandosi sui problemi a monte e a valle.
Possibilità di riutilizzo. La soluzione di problemi semplici è una buona base di partenza per la soluzione di problemi complessi, ed è inutile fornire una nuova implementazione per una soluzione già trovata. La possibilità di riutilizzo di dati e procedure viene ampiamente esplorata nella programmazione a oggetti, con vari risultati.

Ad una procedura che venga ben definita per operare su un problema "standard", con una struttura di dati "standard", in modo ripetibile e riutilizzabile, attribuiamo il nome generico di algoritmo. Obiettivo principale della STL (Standard Template Library) è rendere applicabili algoritmi generici (strutture dati + procedure) ad oggetti qualsiasi.

Template

L'accorgimento sintattico del C++ che consente di applicare algoritmi generici ad oggetti qualsiasi è quello del template, che permette di definire classi e metodi dove i tipi di alcuni dati non sono determinati a priori. Questo si può applicare alla definizione sia di classi

template<typename TNUM> class measurement {

  public:

    typedef TNUM value_type;

    // Creator
    measurement(const TNUM& value, std::string date, std::string observer) :
      m_value(value), m_date(date), m_observer(observer) {}

    // Destructor
    ~measurement() {}

    TNUM  value() const { return m_value; } // Use as 'rvalue';
    TNUM& value()       { return m_value; } // Use as 'lvalue';
    void  value(const TNUM& new_value) { m_value = new_value; } // Value assignment

    const std::string &get_date()     const { return m_date; }
    const std::string &get_observer() const { return m_observer; }

  private:

    TNUM m_value;
    std::string m_date;
    std::string m_observer;

};

che di metodi e funzioni:

template<typename TNUM>
  std::ostream &operator<< (std::ostream &s, const measurement<TNUM> meas)
   {
     return os << meas.get_date() << " - " << meas.get_observer()
               << " - Value: " << meas.value() << std::endl;
   }

Queste definizioni sono utilizzate in questo

Avevamo già visto di sfuggita un esempio di template nel caso di char_traits, il cui template è dichiarato ma non definito in termini del tipo generico, dunque deve essere specializzato per ogni caso.

Contenitori di STL

Fatte queste premesse, ecco una breve panoramica sui contenitori definiti in STL, che è parte integrante della libreria standard del C++, e sulle proprietà che consentono di scegliere il contenitore più adatto alla propria applicazione:

`std::list`	`#include <list>`	Contenitore sequenziale che permette inserimenti e cancellazioni rapidi (vedi figura), ma non permette l'accesso diretto agli elementi se si conosce il numero in sequenza (gli elementi non sono immagazzinati in aree di memoria contigue).
`std::vector`	`#include <vector>`	Contenitore sequenziale dal comportamento simile agli array intrinseci del linguaggio, ma con capacità di espansione automatica. L'aggiunta e la rimozione di elementi è rapida solo in coda, e più lenta nelle altre posizioni (gli elementi sono immagazzinati in aree di memoria contigue).
`std::deque`	`#include <deque>`	Double ended queue. Contenitore sequenzale che permette inserzioni e rimozioni rapide in testa ed in coda. L'inserzione e la rimozione di elementi in altre posizioni è più lenta ma l'indicizzazione degli elementi conoscendo il loro numero di sequenza è veloce, anche se gli elementi non sono immagazzinati in un'area di memoria contigua.
`std::map`, `std::multimap`	`#include <map>`	Array associativo, che permette di associare elementi (valori) a chiavi di vario tipo. Nel caso di `multimap` le chiavi possono essere ripetute (non uniche).
`std::set`, `std::multiset`	`#include <set>`	Array associativo, che permette di associare elementi (valori) a chiavi di vario tipo e immagazzina gli elementi ordinando le chiavi in ordine ascendente. Nel caso di `multiset` le chiavi possono essere ripetute (non uniche).
`std::queue`	`#include <queue>`	"Container Adapter" (contenitore basato su altri contenitori) ottimizzato per il funzionamento in modo FIFO (First in, first out), inserzione in testa e rimozione in coda.
`std::stack`	`#include <stack>`	"Container Adapter" (contenitore basato su altri contenitori) ottimizzato per il funzionamento in modo LIFO (Last in, first out), inserzione e rimozione in testa.
`std::priority_queue`	`#include <queue>`	Coda organizzata in modo che l'elemento più grande sia sempre il primo in testa. Si può operare sul primo elemento.

Non sono elencati nella lista gli pseudo-contenitori, come bitset, string, valarray che non offrono per varie ragioni, (come abbiamo visto nel caso di string) la interfaccia completa dei contenitori STL. Ecco una collezione di metodi usati frequentemente (quelli elencati come "opzionali" sono tipicamente presenti se il contenitore è in grado di rispondere in un tempo non dipendente dal numero di elementi presenti nel contenitore):

`void clear()`	sempre presente	Cancella tutti gli elementi del contenitore.
`bool empty()`	sempre presente	Restituisce `true` se il contenitore è vuoto (`size() == 0`).
`size_type size()`	sempre presente	Restituisce il numero di elementi nel contenitore.
`void push_back(const value_type& x)`	opzionale	Inserisce il valore `x` in coda al contenitore.
`void push_front(const value_type& x)`	opzionale	Inserisce il valore `x` in testa al contenitore.
`void pop_back()`	opzionale	Rimuove l'elemento in coda al contenitore. Il comportamento è indefinito se il contenitore è vuoto.
`void pop_front()`	opzionale	Rimuove l'elemento in testa al contenitore. Il comportamento è indefinito se il contenitore è vuoto.
`(const_)reference back()`	opzionale	Restituisce l'elemento in coda al contenitore. Il comportamento è indefinito se il contenitore è vuoto.
`(const_)reference front()`	opzionale	Restituisce l'elemento in testa al contenitore. Il comportamento è indefinito se il contenitore è vuoto.
`(const_)reference operator[](size_type n)`	opzionale	Restituisce l'elemento nella posizione `n`. Se `n >= size()` il comportamento è indefinito.
`erase(iterator p)` oppure `erase(iterator first, iterator last)`	sempre presente	Cancella l'elemento indicato da `p`, oppure tutti gli elementi da `first` (incluso) a `last` (escluso). (`size() == 0`).
`(const_)iterator (r)begin()`	sempre presente	Restituisce un iteratore che punta al primo elemento di un contenitore. `rbegin` punta all'ultimo elemento, e si utilizza per gli iteratori inversi.
`(const_)iterator (r)end()`	sempre presente	Restituisce un iteratore che punta all'ultimo elemento di un contenitore. `rend` punta al primo elemento, e si utilizza per gli iteratori inversi.
`void insert(iterator p, const value_type& x)`	opzionale	Inserisce un nuovo valore `x` appena prima della posizione dell'iteratore `p`.
`void insert(iterator p, size_type n, const value_type& x)`	opzionale	Inserisce `n` copie del nuovo valore `x` appena prima della posizione dell'iteratore `p`.
`size_type count(const key_type& k)`	opzionale	Nel caso di contenitori associativi, conta il numero di elementi associati alla chiave `k`.
`size_type erase(const key_type& k)`	opzionale	Nel caso di contenitori associativi, cancella gli elementi associati alla chiave `k` e restituisce il numero di elementi cancellati.
`(const_)iterator find(const key_type& k)`	opzionale	Restituisce un iteratore che punta ad un elemento corrispondente alla chiave `k`, o `end()` se non viene trovato.

Iteratori di STL

Per iteratore si intende un oggetto capace di puntare ad un elemento di un contenitore STL, e di passare efficientemente da un elemento all'altro.
Esistono cinque categorie di iteratori, la possibilità di implementare ciascuno dei quali dipende dal tipo di contenitore:

Input	Permette di accedere agli elementi di un contenitore sequenziale in una singola passata. L'operatore di incremento (`++`) permette di passare all'elemento successivo, ma non esiste operatore di decremento. L'operatore di de-referenziazione (``) restituisce un rvalue*, che non consente di modificare l'elemento.
Output	Permette di riempire un contenitore sequenziale in una singola passata. L'operatore di incremento (`++`) permette di passare all'elemento successivo, ma non esiste operatore di decremento. L'operatore di de-referenziazione consente di assegnare un nuovo valore all'elemento, ma non è possibile confrontare fra loro questo tipo di iteratori.
Forward	Permette l'accesso unidirezionale agli elementi di un contenitore, consentendo sia la lettura che l'assegnazione di un elemento: può quindi sostituire sia gli iteratori di input che quelli di output.
Bidirectional	Aggiunge alle funzioni di un iteratore Forward la possibilità di usare l'operatore di decremento (`--`) per arretrare di una posizione.
Random access	Aggiunge alle funzioni di un iteratore Bidirectional la possibilità di usare l'operatore `[]` per accedere direttamente a qualunque elemento del contenitore. Inoltre. sommando e sottraendo numeri interi a un iteratore di questo tipo è possibile "saltare" agli elementi desiderati.

Ciascuno di questi iteratori può essere un const_iterator, che permette di accedere ad un valore costante (rvalue o const lvalue).

Come i puntatori, gli iteratori possono puntare ad elementi cancellati o inesistenti. E' importante ricordare che l'uso di un iteratore che punta all'elemento end() di un contenitore produce risultati indefiniti.

Ogni contenitore di STL fornisce almeno un tipo iterator ed un tipo const_iterator. I contenitori che forniscono accesso bidirezionale o diretto forniscono anche iteratori che permettono di attraversare il contenitore dalla coda alla testa (reverse_iterator, const_reverse_iterator).

Vediamo in quest'altro come si utilizza un contenitore ed iteratore di tipo std::list.
Questo contenitore è la scelta migliore per questa applicazione ?

Esercizio: In questo si mostra come l'oggetto GlutWindowExaminer può essere esteso per consentire di esaminare una sfera. Come si può modificare questo esempio utilizzando un opportuno contenitore STL perché mostri più sfere, magari di colore diverso, inizializzate staticamente ?