MindView Inc.

 

[ Suggerimenti per la visualizzazione ] [ Soluzioni degli esercizi ] [ Volume 2 ] [ Newsletter gratuita ]
[ Seminari ] [ Seminari su CD ROM ] [ Consulenza ]

Pensare in C++, seconda ed. Volume 1

©2000 by Bruce Eckel

[ Capitolo precedente ] [ Indice generale ] [ Indice analitico ] [ Capitolo successivo ]

traduzione italiana e adattamento a cura di Barbara Colaiocco

16: Introduzione ai Template

Ereditarietà e composizione forniscono un modo di riutilizzare il codice oggetto. La caratteristica template in C++ fornisce un modo di riutilizzare il codice sorgente.

Nonostante i template C++ siano un tool di programmazione per tutti gli usi, quando furono introdotti nel linguaggio, sembrarono scoraggiare l’uso di gerarchie di classi-contenitore basate sugli oggetti (dimostrate alla fine del Capitolo 15). Per esempio, i contenitori e gli algoritmi Standard C++ (spiegati in due capitoli del Volume 2 di questo libro, scaricabile da www.BruceEckel.com) sono costituiti esclusivamente da template e sono relativamente facili da usare per il programmatore.

Questo capitolo non solo spiega i concetti base dei template, ma è anche un’introduzione ai contenitori, che sono componenti fondamentali della progammazione orientata agli oggetti e sono quasi completamente realizzati attraverso i contenitori nella Libreria Standard C++. Si capirà che nel libro sono stati usati esempi di contenitori – lo Stash e lo Stack – , apposta per rendere il lettore avvezzo all’idea dei contenitori; in questo capitolo sarà anche aggiunto il concetto di iteratore. Nonostante i contenitori siano esempi ideali di uso di template, nel Volume 2 (in cui c’è un capitolo avanzato sui template) si imparerarà che esistono anche molti altri loro usi.

Container (Contenitori)

Si supponga di voler creare uno stack, come abbiamo fatto nel libro. Questa classe stack conserverà int, tanto per farla semplice:

//: C16:IntStack.cpp
// Semplice stack di interi
//{L} fibonacci
#include "fibonacci.h"
#include "../require.h"
#include <iostream>
using namespace std;

class IntStack {
  enum { ssize = 100 };
  int stack[ssize];
  int top;
public:
  IntStack() : top(0) {}
  void push(int i) {
    require(top < ssize, "Troppi inserimenti eseguiti chiamando push( )");
    stack[top++] = i;
  }
  int pop() {
    require(top > 0, "Troppe chiamate alla funzione pop( )");
    return stack[--top];
  }
};

int main() {
  IntStack is;
  // Aggiunge qualche numero di Fibonacci, per renderlo più interessante:
  for(int i = 0; i < 20; i++)
    is.push(fibonacci(i));
  // Li recupera & li stampa:
  for(int k = 0; k < 20; k++)
    cout << is.pop() << endl;
} ///:~

La classe IntStack è un esempio banale di stack push-down (implementa, cioè, una pila, che usa la tecnica Last In First Out: l’ultimo elemento inserito è il primo ad essere recuperato, ndt). Qui per semplicità è stato creato di dimensioni fisse, ma è possibile anche modificarlo espandendolo automaticamente allocando memoria fuori dall’heap, come nella classe Stack che è stata esaminata nel libro.

main( ) aggiunge qualche intero allo stack , e li restituisce anche. Per rendere l’esempio più interessante, gli interi sono creati con la funzione di fibonacci( ), che genera numeri secondo la tradizionale “rabbit-reproduction”. Qui c’è l’ header file che dichiara la funzione:

//: C16:fibonacci.h
// Generatore di numeri di Fibonacci
int fibonacci(int n); ///:~

Qui c’è l'implementazione:

//: C16:fibonacci.cpp {O}
#include "../require.h"

int fibonacci(int n) {
  const int sz = 100;
  require(n < sz);
  static int f[sz]; // Initializzato a zero
  f[0] = f[1] = 1;
  // cerca elementi dell'array ancora settati a zero:
  int i;
  for(i = 0; i < sz; i++)
    if(f[i] == 0) break;
  while(i <= n) {
    f[i] = f[i-1] + f[i-2];
    i++;
  }
  return f[n];
} ///:~

Questa è un’implementazione ragionevolmente efficiente , poichè non genera mai due numeri uguali. Usa un array static di int, e conta sul fatto che il compilatore inizializzerà un array static a zero. Il primo ciclo for incrementa l’indice i fino a che non si raggiunge il primo elemento nullo dell'array, quindi un ciclo while aggiunge i numeri di Fibonacci all’array finchè non viene raggiunto l’elemento desiderato. Ma si noti che se i numeri di Fibonacci fino all'elemento n-simo sono già inizializzati, il ciclo while viene saltato del tutto.

La necessità di contenitori

Ovviamente, uno stack di interi (siffatto) non è un di grande utilità. Il bisogno reale di contenitori viene quando si iniziano a creare oggetti sulla heap usando new e li si distrugge con delete. In un problema di programmazione generale, , non si sa di quanti oggetti si avrà bisogno nel corso della stesura del programma. Per esempio, in un sistema di controllo del traffico aereo non si vuole limitare il numero di aerei che il sistema può controllare. Non si vuole che il programma termini soltanto perchè abbiamo superato qualche numero. In un sistema CAD (computer-aided design) , si ha a che fare con molte figure, ma solo l’utente determina (a tempo di esecuzione) esattamente di quante figure stiamo per aver bisogno. Dopo aver notato questa tendenza, il lettore scoprirà un gran numero di esempi nelle sue situazioni di programmazione.

I programmatori C che fanno affidamento sulla memoria virtuale per la loro “gestione della memoria” spesso trovano fastidiosa l'idea di new, delete e delle classi contenitore. Apparentemente, una pratica in C è creare un enorme array globale, più grande di qualsiasi cosa di cui il programma sembrerebbe necessitare. Questo può non richiedere molti pensieri (o la consapevolezza di malloc( ) e free( )), ma produce programmi che non funzionano bene e che nascondono bachi sottili.

Inoltre, se si crea un enorme array di oggetti in C++, l’overhead (il dispendio di risorse) del costruttore e del distruttore può rallentare significativamente le cose. L’approccio C++ lavora molto meglio: quando si ha bisogno di un oggetto, lo si crea con new, e si inserisce il suo puntatore in un contenitore. Più tardi, lo si ripesca e ci si fa qualcosa. In questo modo, si creano soltanto gli oggetti di cui si ha assoluto bisogno. E usualmente all'avvio del programma non si hanno a disposizione tutte le condizioni di inizializzazione. new consente di aspettare finchè qualcosa accada nell'ambiente prima che si possa di fatto creare l'oggetto.

Così nella maggior parte delle situazioni comuni si farà un contenitore che conserva i puntatori a qualche oggetto di interesse. Si creeranno questi oggetti usando new ed inserendo il puntatore risultante nel contenitore (potenzialmente facendo su esso un casting all'insù nel processo), tirandolo fuori dopo nel momento in cui si vuole fare qualcosa con l'oggetto. Questa tecnica produce la maggior parte dei tipi flessibili, generali di programma.

Panoramica sui template

Ora si solleva un problema. Abbiamo un IntStack, che conserva interi. Ma vorremmo uno stack che conservi figure o velivoli o piante o qualsiasi altra cosa. Reinventare il nostro codice sorgente ogni volta non sembra essere un approccio molto intelligente con un linguaggio che procaccia la riusabilità. Ci dev’essere un modo migliore.

Ci sono tre tecniche per il riuso del codice sorgente in questa situazione: la strada del C, presentata qui per contrasto; l’approccio Smalltalk, che ha influenzato pesantemente il C++ e l’approccio C++: i template.

La soluzione C. Naturalmente state provando a tirarvi fuori dall’approccio C poichè è incasinato ed incline agli errori e completamente inelegante. In questo approccio, si copia il codice sorgente di Stack e si fanno le modifiche a mano, introducendo nuovi errori nel processo. Questa è certamente una tecnica non molto produttiva.

La soluzione Smalltalk. Smalltalk (e il Java, che segue il suo esempio) ha impiegato un approccio semplice e diretto: se si vuole riusare del codice, allora si usi l’ereditarietà. Per implementare ciò, ciascuna classe contenitore conserva gli elementi della classe base generica Object (simile all’esempio alla fine del Capitolo 15). Ma poichè la libreria in Smalltalk è di importanza fondamentale, non si crea mai una classe da zero. Al contrario, si deve sempre ereditarla da una classe esistente. Si trova una classe prossima il più possibile a quella voluta, si eredita da essa, e si fanno pochi cambiamenti. Ovviamente, questo è un un beneficio perché minimizza il nostro sforzo (e spiega perchè si spende molto tempo ad imparare la libreria della classe prima di diventare un effiente programmatore Smalltalk).

Ma significa anche che tutte le classi in Smalltalk finiscono con l’essere parte di un singolo albero di ereditarietà. Si deve ereditare da un ramo di questo albero quando si sta creando una nuova classe. La maggior parte dell'albero c’è già (è la libreria della classe Smalltalk), e alla radice dell'albero c’è una classe chiamata Object – la stessa classe che ciascun contenitore Smalltalk conserva.

Questo è un raggiro ordinato poichè significa che ogni classe nella gerarchia di classe Smalltalk (e Java[59]) è derivata da Object, così ogni classe può essere conservata in ogni contenitore (incluso quel contenitore stesso). Questo tipo di gerarchia ad albero singolo basata su un tipo generico fondamentale (spesso chiamato Object, anche in Java) è detta “gerarchia basata sugli oggetti .” E’ possibile che si sia sentito questo termine e lo si sia interpretato come qualche nuovo concetto fondamentale nella OOP, come il polimorfismo. Semplicemente si riferisce ad una gerarchia di classe con Object (o qualche nome simile) alla sua radice e a classi contenitore che conservano Object.

Poichè la libreria della classe Smalltalk ha una storia ed un’esperienza molto più lunga rispetto al C++, e poichè i compilatori C++ originali non avevano librerie di classi contenitore, sembrò una buona idea duplicare la libreria Smalltalk in C++. Questo fu fatto come esperimento con un'iniziale implementazione del C++ [60], e poichè rappresentava un porzione significativa di codice, molta gente ha cominciato usando questa implementazione. Provando ad usare le classi contenitore, scoprirono un problema.

Il problema era che in Smalltalk (e nella maggior parte degli altri linguaggi OOP di cui sia a conoscenza), tutte le classi sono automaticamente derivate da una singola gerarchia, ma questo non è vero in C++. Si poteva avere la propria bella gerarchia basata sugli oggetti con le sue classi contenitore, ma si poteva comperare un insieme di classi figura o di classi velivolo da un altro fornitore che non usava questa gerarchia. (Usare questa gerarchia impone overhead, che i programmatori C evitano.) Come fare ad inserire un albero di classe separato nella classe contenitore nella propria gerarchia basata sugli oggetti? Ecco come appare il problema:


Poichè il C++ supporta gerarchie indipendenti multiple, Smalltalk è una gerarchia basata sugli oggetti che non lavora così bene.

La soluzione è sembrata ovvia. Se si possono avere molte gerarchie di ereditarietà, allora si dovrebbe essere in grado di ereditare da più di una sola classe: l’ereditarietà multipla risolverà il problema. Così si fa quanto segue (un esempio simile era stato dato alla fine del Capitolo 15):


Ora OShape ha caratteristiche e comportamenti di Shape, ma poichè è anche derivata da Object può essere messa in Container. L'eredità extra in OCircle, OSquare, ecc. è necessaria affinchè queste classi possano essere castate all'insù verso OShape e quindi mantengano il comportamento corretto. Si può vedere le cose stanno ingarbugliandosi rapidamente.

I fornitori di compilatori hanno inventato ed incluso le proprie gerarchie di classi contenitore basate sugli oggetti, la maggior parte delle quali son state da allora rimpiazzate dalle versioni template. Si può arguire che per risolvere problemi di programmazione generale è stato necessario ricorrere all’ereditarietà multipla, ma si vedrà nel secondo volume di questo libro che la sua complessità è meglio evitarla eccetto in casi speciali.

La soluzione template

Nonostante una gerarchia basata sugli oggetti con l'eredità multipla sia concettualmente semplice, risulta essere penosa da usare. Nel suo libro originale [61] Stroustrup ha dimostrato che cosa abbia considerato quale alternativa preferibile alla gerarchia basata sugli oggetti. Le classi contenitore sono state create come vaste macro del preprocessore con argomenti che potrebbero essere sostituiti con il tipo desiderato. Quando si voleva creare un contenitore che conservasse un tipo particolare, si facevano due chiamate macro.

Sfortunatamente, questo approccio era confuso da tutta l’esistente letteratura Smalltalk e dall'esperienza di programmazione, ed era un tantino poco maneggevole. Fondamentalmente, nessuno lo possedeva.

Nel frattempo, Stroustrup ed il team C++ dei Laboratori Bell avevano modificato il loro originale approccio con le macro, semplificandolo e spostandolo dal dominio del preprocessore a quello del compilatore. Questo nuovo dispositivo di sostituzione del codice è chiamato template[62], e rappresenta un modo completamente diverso di riusare il codice. Invece di riusare il codice oggetto, come l’ereditarietà e la composizione, un template riusa il codice sorgente. Il contenitore non conserva più una classe base generica detta Object, al contrario conserva un parametro non specificato. Quando si usa un template, il parametro è sostituito dal compilatore, come nel vecchio approccio con le macro, ma è più chiaro e semplice da usare.

Ora, invece di preoccuparsi dell'ereditarietà o della composizione quando si vuole usare una classe contenitore, si prende la versione template del contenitore e si caratterizza così da ottenerne una specifica versione per il proprio particolare problema, come questo:


Il compilatore fa il lavoro per noi, e alla fine il risultato è che abbiamo esattamente il contenitore che ci serve per il nostro lavoro, invece di una gerarchia di ereditarietà poco maneggevole. In C++, il template implementa il concetto di tipo parametrizzato. Un altro benefico dell'approccio dei template è che il programmatore principiante che può essere poco familiare o trovare poco facile l’ereditarietà può ancora usare le classi contenitore incapsulate da subito. (come abbiamo fatto con vector nel libro).

La sintassi di template

La parola chiave template dice al compilatore che la definizione di classe che segue manipolerà uno o più tipi non specificati. Nel momento in cui il codice della classe reale è generato dal template, questi tipi devono essere specificati, cosicchè il compilatore possa sostituirli.

Per dimostrare la sintassi, qui c’è un piccolo esempio che produce un array bounds-checked (si controlla che l’indice non cada al di fuori delle dimensioni dell’array, ndt) :

//: C16:Array.cpp
#include "../require.h"
#include <iostream>
using namespace std;

template<class T>
class Array {
  enum { size = 100 };
  T A[size];
public:
  T& operator[](int index) {
    require(index >= 0 && index < size,
      "Indice fuori dal range");
    return A[index];
  }
};

int main() {
  Array<int> ia;
  Array<float> fa;
  for(int i = 0; i < 20; i++) {
    ia[i] = i * i;
    fa[i] = float(i) * 1.414;
  }
  for(int j = 0; j < 20; j++)
    cout << j << ": " << ia[j]
         << ", " << fa[j] << endl;
} ///:~

Si può vedere che appare come una classe normale eccetto per la linea

template<class T> 

che dice che T è il parametro della sostituzione , e che rappresenta un nome di tipo. Inoltre, si vede che T è usato nella classe ovunque si vorrebbe normalmente vedere il tipo specifico che conserva il contenitore.

In Array, gli elementi sono inseriti e estratti con la stessa funzione: la sovraccaricata operator [ ] . Questa ritorna un riferimento, così tale valore di ritorno può essere usato in entrambi i lati di un segno di uguaglianza (cioè, sia come un lvalue che un rvalue). Si noti che se l’indice è fuori dai confini, è usata la funzione require( ) per stampare un messaggio. Poichè operator[] è una funzione inline, si portebbe usare questo approccio per garantire che non si verifichino violazioni dei limiti dell’array, rimuovendo quindi la funzione require( ) per la portabilità del codice.

In main( ), si può vedere come sia facile creare Arrays che conservino differenti tipi di oggetti. Quando si dice

Array<int> ia;
Array<float> fa;

il compilatore espande il template Array (questa è detta istanziazione) due volte, per creare due nuove classi generate, che si possono pensare come Array_int e Array_float. (Compilatori differenti possono decorare i nomi in modi diversi.) Queste classi sono proprio quelle che si sarebberero create se si fosse compiuta la sostituzione a mano, eccetto per il fatto che è il compilatore a crearle per noi quando definiamo gli oggetti ia e fa. Si noti anche che le definizioni di classe duplicate sono o evitate dal compilatore o fuse dal linker.

Definizioni di funzioni non inline

Naturalmente, ci sono delle volte in cui desidereremo avere definizioni di funzioni membro non inline . In tal caso, il compilatore ha bisogno di vedere la dichiarazione template prima della definizione della funzione membro. Qui c’è l’esempio sopra, modificato per mostrare la definizione non inline di una funzione membro:

//: C16:Array2.cpp
// Definizione di template non inline
#include "../require.h"

template<class T>
class Array {
  enum { size = 100 };
  T A[size];
public:
  T& operator[](int index);
};

template<class T>
T& Array<T>::operator[](int index) {
  require(index >= 0 && index < size,
    "Indice fuori dal range");
  return A[index];
}

int main() {
  Array<float> fa;
  fa[0] = 1.414;
} ///:~

Qualsiasi riferimento ad un nome di classe template dev’essere accompagnato dalla sua lista di argomenti template, come in Array<T>::operator[]. Si può immaginare che internamente, si stia decorando il nome della classe con gli argomenti nella lista degli argomenti template per produrre un identificatore di nome di classe unico per ogni istanziazione di template.

Header files

Anche se si creano definizioni non inline di funzioni, usualmente si vorrà inserire tutte le dichiarazioni e tutte le definizioni per un template in un header file. Questa può apparire come una violazione della normale regola dell’header file “non inserire alcunchè che allochi memoria,” (la quale previene errori di definizioni multiple al momento del linkaggio), ma le definizioni template sono speciali. Qualsiasi cosa preceduta da template<...> significa che il compilatore non allocherà memoria per essa in quel punto, ma aspetterà finchè sia chiamata (da un’istanziazione di template), e che da qualche parte nel compilatore e nel linker c’è un meccanismo per la rimozione di definizioni multiple di un identico template. Così si metteranno quasi sempre nell’header file sia la dichiarazione sia la definizione dell’intero template, per la facilità d’uso.

A volte si può avere bisogno di mettere le definizioni template in un file cpp separato per soddisfare necessità particolari (per esempio, forzare le istanziazioni template ad esistere solamente in un singolo file Windows dll). La maggior parte dei compilatori ha qualche meccanismo che lo consente; si dovrà studiare la documentazione del proprio particolare compilatore per usarlo.

Alcuni ritengono che mettere tutto il codice sorgente per la propria implementazione in un header file, esponga alla possibilità che la gente rubi o modifichi il codice se acquista la nostra libreria. Questa può essere un’obiezione, ma probabilmente dipende dal modo in cui si osserva il problema: sta acquistando un prodotto od un servizio? Se è un prodotto, allora si deve fare tutto il possibile per proteggerlo, e probabilmente non si vorrà fornire il codice sorgente, ma solo il codice compilato. Ma molta gente vede il software come un servizio, e ancor più di questo, un servizio di abbonamento. Il cliente vuole la consulenza (del creatore del software), vuole che egli continui la manutenzione di questo pezzo di codice riusabile, cosicchè non debba farlo lui – così può focalizzarsi sull’acquisire il suo lavoro fatto. Personalmente penso che la maggior parte dei clienti tratterà il creatore del software come una valida risorsa e non vorranno compromettere il loro rapporto con lui. Per quanto riguarda i pochi che desiderino rubare piuttosto che comprare o fare un lavoro originale, probabilmente non possono continuare comunque con lui.

IntStack come un template

Qui ci sono il contenitore e l’iteratore di IntStack.cpp, implementati come una classe contenitore generica usando i template:

//: C16:StackTemplate.h
// Semplice stack template
#ifndef STACKTEMPLATE_H
#define STACKTEMPLATE_H
#include "../require.h"

template<class T>
class StackTemplate {
  enum { ssize = 100 };
  T stack[ssize];
  int top;
public:
  StackTemplate() : top(0) {}
  void push(const T& i) {
    require(top < ssize, "Troppi inserimenti eseguiti chiamando push( )");
    stack[top++] = i;
  }
  T pop() {
    require(top > 0, "Troppe chiamate alla funzione pop()");
    return stack[--top];
  }
  int size() { return top; }
};
#endif // STACKTEMPLATE_H ///:~

Si noti che un template fa certe assunzioni riguardo agli oggetti che sta conservando. Per esempio, StackTemplate assume che ci sia un qualche tipo di operazione di assegnamento per T dentro la funzione push( ). Si potrebbe dire che un template “implichi un’interfaccia” per i tipi che è capace di conservare.

Un altro modo per dire questo è che i template forniscono un tipo di meccanismo di tipizzazione debole per il C++, che è ordinariamente un linguaggio fortemente tipizzato. Invece di insistere affinchè un oggetto sia di un qualche tipo esatto allo scopo di essere accettabile, la tipizzazione debole richiede solo che le funzioni membro che esso vuole chiamare siano disponibili per un particolare oggetto. Allora, il codice debolmente tipizzato può essere applicato a qualsiasi ogegtto che possa accettare quelle chiamate a funzione, ed è quindi molto più flessibile.[63].

Qui c’è l’esempio rivisto per testare il template:

//: C16:StackTemplateTest.cpp
// Test sul semplice stack template
//{L} fibonacci
#include "fibonacci.h"
#include "StackTemplate.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

int main() {
  StackTemplate<int> is;
  for(int i = 0; i < 20; i++)
    is.push(fibonacci(i));
  for(int k = 0; k < 20; k++)
    cout << is.pop() << endl;
  ifstream in("StackTemplateTest.cpp");
  assure(in, "StackTemplateTest.cpp");
  string line;
  StackTemplate<string> strings;
  while(getline(in, line))
    strings.push(line);
  while(strings.size() > 0)
    cout << strings.pop() << endl;
} ///:~

La sola differenza è la creazione di is. Dentro la lista degli argomenti template si specifica il tipo di oggetto che lo stack e l’iteratore dovrebbero conservare. Per dimostrare la genericità del template, è creato anche uno StackTemplate per conservare string. Questo è testato leggendo linee dal file del codice sorgente.

Le costanti nei template

Gli argomenti dei template non si limitano ai tipi di classe; si possono usare anche tipi built-in. I valori di questi argomenti diventano allora costanti a tempo di compilazione per quella particolare istanziazione del template. Si possono usare inoltre i valori di default per questi argomenti. L’esempio seguente consente di settare le dimensioni della classe Array durante l’istanziazione, ma fornisce anche un valore di default:

//: C16:Array3.cpp
// Tipi built-in come argomenti di template
#include "../require.h"
#include <iostream>
using namespace std;

template<class T, int size = 100>
class Array {
  T array[size];
public:
  T& operator[](int index) {
    require(index >= 0 && index < size,
      "Indice fuori dal range");
    return array[index];
  }
  int length() const { return size; }
};

class Number {
  float f;
public:
  Number(float ff = 0.0f) : f(ff) {}
  Number& operator=(const Number& n) {
    f = n.f;
    return *this;
  }
  operator float() const { return f; }
  friend ostream&
    operator<<(ostream& os, const Number& x) {
      return os << x.f;
  }
};

template<class T, int size = 20>
class Holder {
  Array<T, size>* np;
public:
  Holder() : np(0) {}
  T& operator[](int i) {
    require(0 <= i && i < size);
    if(!np) np = new Array<T, size>;
    return np->operator[](i);
  }
  int length() const { return size; }
  ~Holder() { delete np; }
};

int main() {
  Holder<Number> h;
  for(int i = 0; i < 20; i++)
    h[i] = i;
  for(int j = 0; j < 20; j++)
    cout << h[j] << endl;
} ///:~

Come prima, Array è un array controllato di oggetti e fa in modo di prevenire che si indicizzi al di fuori dei limiti. La classe Holder è molto simile a Array eccetto per il fatto che ha un puntatore ad un Array invece di includere un oggetto di tipo Array. Questo puntatore non è inizializzato nel costruttore; l’inizializzazione è ritardata fino al primo accesso. Questa è detta lazy initialization (inizializzazione pigra); si può usare una tecnica come questa se si stanno creando molti oggetti, ma non si accede a tutti, e si vuole salvare memoria.

Si noterà che il valore di size in entrambi i template non è mai immagazzinato internamente nella classe, ma è usato come se fosse un dato membro all’interno delle funzioni membro.

Stack e Stash
come template

I ricorrenti problemi di “apparteneza” con le classi contenitore Stash e Stack che sono stati rivisitati durante questo libro vengono dal fatto che questi contenitori non erano in grado di sapere esattamente che tipi conservassero. L’ultimo arrivato è il “contenitore di ObjectStack che è stato visto alla fine del Capitolo 15 in OStackTest.cpp.

Se il programmatore cliente non rimuove esplicitamente tutti i puntatori agli oggetti che sono conservati nel contenitore, allora il contenitore dovrebbe essere in grado di cancellare correttamente questi puntatori. Cioè, il contenitore “possiede” qualsiasi oggetto che non sia stato rimosso, ed è quindi responsabile per la loro pulizia. L’ostacolo è stato che la pulizia richiede la conoscenza del tipo dell’oggetto, e la creazione di una classe contenitore generica richiede di non conoscere il tipo dell’oggetto. Con i template, tuttavia, si può scrivere codice che non conosce il tipo dell’oggetto, e istanziare facilmente una nuova versione di quel contenitore per ogni tipo che si desidera esso contenga. I contenitori istanziati individuali conoscono il tipo di oggetti che essi conservano e possono così chiamare il corretto distruttore (assumendo, nel caso tipico in cui sia incluso il polimorfismo, che sia stato fornito un distruttore virtuale).

Per lo Stack ciò risulta essere abbastanza semplice poiché tutte le funzioni membro possono essere ragionevolmente messe inline:

//: C16:TStack.h
// Lo Stack come un template
#ifndef TSTACK_H
#define TSTACK_H

template<class T>
class Stack {
  struct Link {
    T* data;
    Link* next;
    Link(T* dat, Link* nxt): 
      data(dat), next(nxt) {}
  }* head;
public:
  Stack() : head(0) {}
  ~Stack(){ 
    while(head)
      delete pop();
  }
  void push(T* dat) {
    head = new Link(dat, head);
  }
  T* peek() const {
    return head ? head->data : 0; 
  }
  T* pop(){
    if(head == 0) return 0;
    T* result = head->data;
    Link* oldHead = head;
    head = head->next;
    delete oldHead;
    return result;
  }
};
#endif // TSTACK_H ///:~

Se si confronta questo listato con l’esempio OStack.h alla fine del Capitolo 15, si vedrà che Stack è virtualmente identica, eccetto Object che è stato sostituito da T. Anche il programma di test è quasi identico, a parte che è stata eliminata la necessità della ereditarietà multipla da string e Object (ed allo stesso tempo per Object stesso). Ora non c’è la classe MyString ad annunciare la sua distruzione, così si è aggiunta una nuova piccola classe per mostrare un contenitore Stack che fa pulizia dei suoi oggetti:

//: C16:TStackTest.cpp
//{T} TStackTest.cpp
#include "TStack.h"
#include "../require.h"
#include <fstream>
#include <iostream>
#include <string>
using namespace std;

class X {
public:
  virtual ~X() { cout << "~X " << endl; }
};

int main(int argc, char* argv[]) {
  requireArgs(argc, 1); // Il nome del file è un argomento
  ifstream in(argv[1]);
  assure(in, argv[1]);
  Stack<string> textlines;
  string line;
  // Legge il  file e immagazzina le linee nello Stack:
  while(getline(in, line))
    textlines.push(new string(line));
  // Recupera qualche linea dallo stack:
  string* s;
  for(int i = 0; i < 10; i++) {
    if((s = (string*)textlines.pop())==0) break;
    cout << *s << endl;
    delete s; 
  } // Il distruttore cancella le altre stringhe.
  // Mostra che avviene la corretta distruzione:
  Stack<X> xx;
  for(int j = 0; j < 10; j++)
    xx.push(new X);
} ///:~

Il distruttore per X è virtuale, non perchè sia necessario qui, ma perchè xx potrebbe essere usato dopo per conservare oggetti derivati da X.

Si noti quanto sia facile creare differenti tipi di Stack per string e per X. A causa del template, si ottiene il meglio di entrambi i mondi: la facilità d’uso della classe Stack assieme ad una adeguata pulizia.

Il puntatore Stash templatizzato

Riorganizzare il codice di PStash in un template non è proprio così semplice perchè ci sono diverse funzioni membro che dovrebbero essere non inline. Tuttavia, come template quelle definizioni di funzioni appartengono ancora all’header file (il compilatore ed il linker si prendono cura di qualsiasi problema di definizioni multiple). Il codice appare abbastanza simile all’ordinario PStash solo che si noterà che la dimensione dell’incremento (usato da inflate( )) è stata templatizzata come un parametro non di classe con un valore di default, cosicchè la dimensione dell’incremento possa essere modificata nel punto di istanzazione (si noti che questo significa che la dimensione dell’incremento è fissata; si può anche dedurre che la dimensione dell’incremento dovrebbe essere modificabile durante il tempo di vita dell’oggetto):

//: C16:TPStash.h
#ifndef TPSTASH_H
#define TPSTASH_H

template<class T, int incr = 10>
class PStash {
  int quantity; // Numbero di celle di memoria
  int next; // Prossima cella libera
  T** storage;
  void inflate(int increase = incr);
public:
  PStash() : quantity(0), next(0), storage(0) {}
  ~PStash();
  int add(T* element);
  T* operator[](int index) const; // Fetch
  // Rimuove il riferimento da questo PStash:
  T* remove(int index);
  // Numero di elementi in Stash:
  int count() const { return next; }
};

template<class T, int incr>
int PStash<T, incr>::add(T* element) {
  if(next >= quantity)
    inflate(incr);
  storage[next++] = element;
  return(next - 1); // Indice
}

// Appartenenza dei puntatori restanti:
template<class T, int incr>
PStash<T, incr>::~PStash() {
  for(int i = 0; i < next; i++) {
    delete storage[i]; // Puntatori NULL OK
    storage[i] = 0; // Solo per essere sicuro
  }
  delete []storage;
}

template<class T, int incr>
T* PStash<T, incr>::operator[](int index) const {
  require(index >= 0,
    "PStash::operator[] indice negativo");
  if(index >= next)
    return 0; // Per indicare la fine
  require(storage[index] != 0, 
    "PStash::operator[] ha restituito un puntatore NULL");
  // Produce il puntatore all’elemento desiderato:
  return storage[index];
}

template<class T, int incr>
T* PStash<T, incr>::remove(int index) {
  // operator[] effettua controlli di validità:
  T* v = operator[](index);
  // "Rimuove" il puntatore:
  if(v != 0) storage[index] = 0;
  return v;
}

template<class T, int incr>
void PStash<T, incr>::inflate(int increase) {
  const int psz = sizeof(T*);
  T** st = new T*[quantity + increase];
  memset(st, 0, (quantity + increase) * psz);
  memcpy(st, storage, quantity * psz);
  quantity += increase;
  delete []storage; // Vecchia memoria
  storage = st; // Punta alla nuova memoria
}
#endif // TPSTASH_H ///:~

La dimensione di default dell’incremento usata qui è piccola al fine di garantire che si verifichino le chiamate ad inflate( ) . In tal modo possiamo essere sicuri che lavori correttamente.

Per testare il controllo di appartenenza del PStash templatizzato, la seguente classe descriverà le creazioni e distruzioni di se stessa, e garantirà anche che tutti gli oggetti che sono stati creati siano stati anche distrutti. AutoCounter consentirà soltanto agli oggetti del suo tipo di essere creati sullo stack:

//: C16:AutoCounter.h
#ifndef AUTOCOUNTER_H
#define AUTOCOUNTER_H
#include "../require.h"
#include <iostream>
#include <set> // Contenitore della Libreria Standard C++ 
#include <string>

class AutoCounter {
  static int count;
  int id;
  class CleanupCheck {
    std::set<AutoCounter*> trace;
  public:
    void add(AutoCounter* ap) {
      trace.insert(ap);
    }
    void remove(AutoCounter* ap) {
      require(trace.erase(ap) == 1,
        "Si sta tentando di cancellare due volte AutoCounter");
    }
    ~CleanupCheck() {
      std::cout << "~CleanupCheck()"<< std::endl;
      require(trace.size() == 0,
       "Non tutti gli oggetti AutoCounter sono stati cancellati");
    }
  };
  static CleanupCheck verifier;
  AutoCounter() : id(count++) {
    verifier.add(this); // Registrazione di se stesso
    std::cout << "creato[" << id << "]" 
              << std::endl;
  }
  // Prevennzione dell’assegnamento e della costruzione di copia:
  AutoCounter(const AutoCounter&);
  void operator=(const AutoCounter&);
public:
  // Si possono solo creare oggetti con con questo:
  static AutoCounter* create() { 
    return new AutoCounter();
  }
  ~AutoCounter() {
    std::cout << "distruzione di[" << id 
              << "]" << std::endl;
    verifier.remove(this);
  }
  // Stampa sia oggetti che puntatori:
  friend std::ostream& operator<<(
    std::ostream& os, const AutoCounter& ac){
    return os << "AutoCounter " << ac.id;
  }
  friend std::ostream& operator<<(
    std::ostream& os, const AutoCounter* ac){
    return os << "AutoCounter " << ac->id;
  }
}; 
#endif // AUTOCOUNTER_H ///:~

La classe AutoCounter fa due cose. Primo, numera sequenzialmente ogni istanza di AutoCounter: il valore di questo numero è conservato in id, ed il numero è generato usando il dato membro static count.

Secondo, e più complesso, una istanza static (detta verifier) della classe annidata CleanupCheck conserva una traccia di tutti gli oggetti AutoCounter che sono stati creati e distrutti, e segnala se non si sono cancellati tutti (cioè se c’è una falla di memoria). Questo comportamento è realizzato usando una classe set della libreria Standard C++, che è un meraviglioso esempio di come template ben progettati possano rendere facile la vita (si possono imparare tutti i contenitori nella libreria Standard C++ nel Volume 2 di questo libro, disponibile online).

La classe set è templatizzata sul tipo che essa conserva; qui è istanziata a conservare puntatori AutoCounter. Un set consentirà solo una istanza per ciascun distinto oggetto da aggiungere; si può vedere che questo si compie in add( ) con la funzione set::insert( ). insert( ) in realtà ci informa con il suo valore di ritorno se stiamo provando ad aggiungere qualcosa che è già stato aggiunto; tuttavia, poichè si stanno aggiungendo gli indirizzi degli oggetti possiamo contare sulla garanzia del C++ che tutti gli oggetti abbiano indirizzi unici.

In remove( ), set::erase( ) è usata per rimuovere un puntatore AutoCounter dal set. Il valore di ritorno ci dice quante istanze dell’elemento sono state rimosse; nel nostro caso ci aspettiamo solo o zero o uno. Se il valore è zero, tuttavia, significa che questo oggetto è stato già cancellato dal set e stiamo provando a cancellarlo una seconda volta, cosa che costituisce un errore di programmazione che sarà segnalato tramite require( ).

Il distruttore per CleanupCheck fa un controllo finale assicirandosi che la dimensione del set sia zero – questo significa che tutti gli oggetti sono stati cancellati correttamente. Se è diverso da zero, abbiamo una falla di memoria, segnalata attraverso require( ).

Il costruttore ed il distruttore di AutoCounter registrano and cancellano se stessi con l’oggetto verifier . Si noti che il costruttore, il costruttore di copia, e l’operatore di assegnamento sono private, così il solo modo per noi di creare un oggetto è con la funzione membro static create( ) – questo è un semplice esempio di una fabbrica, ed essa garantisce che tutti gli oggetti siano creati nella heap, così verifier non si confonderà riguardo agli assegnamenti e alle costruzioni di copia.

Poichè tutte le funzioni membro sono state messe inline, la sola ragione per cui esiste il file di implementazione è quella di contenere le definizioni dei dati membro statici:

//: C16:AutoCounter.cpp {O}
// Definizione dei membri di classe statici
#include "AutoCounter.h"
AutoCounter::CleanupCheck AutoCounter::verifier;
int AutoCounter::count = 0;
///:~ 

Con AutoCounter in mano, possiamo ora testare le facilità di PStash. L’esempio seguente non solo mostra che distruttore di PStash cancella tutti gli oggetti che esso possiede correntemente, ma dimostra anche come la classe AutoCounter rilevi gli oggetti che non sono stati cancellati:

//: C16:TPStashTest.cpp
//{L} AutoCounter
#include "AutoCounter.h"
#include "TPStash.h"
#include <iostream>
#include <fstream>
using namespace std;

int main() {
  PStash<AutoCounter> acStash;
  for(int i = 0; i < 10; i++)
    acStash.add(AutoCounter::create());
  cout << "Rimuovine 5 manualmente:" << endl;
  for(int j = 0; j < 5; j++)
    delete acStash.remove(j);
  cout << "Rimuovine due senza cancellarli:"
       << endl;
  // ... per generare il messaggio di errore di cancellazione.
  cout << acStash.remove(5) << endl;
  cout << acStash.remove(6) << endl;
  cout << "Il distruttore cancella il resto:"
       << endl;
  // Ripeti il test dei capitoli precedenti: 
  ifstream in("TPStashTest.cpp");
  assure(in, "TPStashTest.cpp");
  PStash<string> stringStash;
  string line;
  while(getline(in, line))
    stringStash.add(new string(line));
  // Stampa le stringhe:
  for(int u = 0; stringStash[u]; u++)
    cout << "stringStash[" << u << "] = "
         << *stringStash[u] << endl;
} ///:~

Quando gli elementi 5 e 6 di AutoCounter sono rimossi dal PStash, essi diventano responsabilità del chiamante, ma poichè questo non li cancella mai essi causano una falla di memoria, individuata da AutoCounter a run time.

Se si fa girare il programma, si vedrà che il messaggio di errore non è così specifico come potrebbe essere. Se si usa lo schema presentato in AutoCounter per scoprire falle di memoria nel proprio sistema, probabilmente si vorrà avere una versione di quello schema che stampi informazioni più dettagliate sugli oggetti che non sono stati cancellati. Il Volume 2 di questo libro mostra modi più sofisticati di fare questo.

Accendere e spegnere l’appartenenza

Ritorniamo al problema dell’appartenenza. I contenitori che conservano oggetti per valore usualmente non si sbagliano sull’appartenenza, poichè essi posseggono chiaramente gli oggetti che contengono. Ma se il nostro contenitore conserva puntatori (che è più comune in C++, specialmente con il polimorfismo), allora è molto probabile che questi puntatori possano anche essere usati da qualche altra parte nel programma, e noi non vogliamo necessariamente cancellare l’oggetto perchè allora gli altri puntatori nel programma si riferirebbero ad un oggetto ditrutto. Per evitare che questo accada, si deve considerare l’appartenenza quando si progetta e si usa un contenitore.

Molti programmi sono molto più semplici di questo, e non si incontra il problema dell’appartenenza: un contenitore conserva puntatori ad oggetti che sono usati solo da quel contenitore. In questo caso l’appartenenza è molto semplice: il contenitore possiede i suoi oggetti.

Il miglior approccio per trattare il problema dell’appartenenza è dare al programmatore cliente una scelta. Questo si realizza spesso tramite un argomento del costruttore che di default indica l’appartenenza (il caso più semplice). In più ci possono essere funzioni “get” e “set” per conoscere lo stato dell’appartenenza del contenitore e modificarlo. Se il contenitore ha funzioni che rimuovono un oggetto, lo stato di appartenenza usualmente influenza questa rimozione, così si possono anche trovare opzioni per controllare la distruzione nella funzione di rimozione. In teoria si sarebbero potuti aggiungere i dati di appartenenza per ciascun elemento nel contenitore, così ogni posizione avrebbe saputo se avesse avuto bisogno di essere distrutta; questa è una variante del conteggio del riferimento, ad eccezione del fatto che il contenitore e non l’oggetto sa il numero di riferimenti che puntano ad un oggetto.

//: C16:OwnerStack.h
// Stack con appartenenza controllabile a runtime
#ifndef OWNERSTACK_H
#define OWNERSTACK_H

template<class T> class Stack {
  struct Link {
    T* data;
    Link* next;
    Link(T* dat, Link* nxt) 
      : data(dat), next(nxt) {}
  }* head;
  bool own;
public:
  Stack(bool own = true) : head(0), own(own) {}
  ~Stack();
  void push(T* dat) {
    head = new Link(dat,head);
  }
  T* peek() const { 
    return head ? head->data : 0; 
  }
  T* pop();
  bool owns() const { return own; }
  void owns(bool newownership) {
    own = newownership;
  }
  // Conversione di tipo in stesso tipo: vero se non vuoto:
  operator bool() const { return head != 0; }
};

template<class T> T* Stack<T>::pop() {
  if(head == 0) return 0;
  T* result = head->data;
  Link* oldHead = head;
  head = head->next;
  delete oldHead;
  return result;
}

template<class T> Stack<T>::~Stack() {
  if(!own) return;
  while(head)
    delete pop();
}
#endif // OWNERSTACK_H ///:~

Il comportamento di default del contenitore è di distrugegre i suoi oggetti, ma lo si può cambiare o modificando l’argomento del costruttore o usando le funzioni membro di lettura/scrittura owns( ).

Come con la maggior parte dei template che probabilmente si vedono, l’intera implementazione è contenuta nell’header file. Qui c’è un piccolo test che esercita le abilità di appartenenza:

//: C16:OwnerStackTest.cpp
//{L} AutoCounter 
#include "AutoCounter.h"
#include "OwnerStack.h"
#include "../require.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

int main() {
  Stack<AutoCounter> ac; // Appartenenza attiva
  Stack<AutoCounter> ac2(false); // Convertita in non attiva
  AutoCounter* ap;
  for(int i = 0; i < 10; i++) {
    ap = AutoCounter::create();
    ac.push(ap);
    if(i % 2 == 0)
      ac2.push(ap);
  }
  while(ac2)
    cout << ac2.pop() << endl;
  // La distruzione è superflua poichè
  // ac "possiede" tutti gli oggetti
} ///:~

L’oggetto ac2 non possiede gli oggetti che vengono in esso inseriti, così ac è il contenitore “master” che prende la responsabilità dell’appartenenza. Se si vuole cambiare, in parte nel corso del tempo di vita di un contenitore, il fatto che un contenitore possegga o meno i suoi oggetti, lo si può fare usando owns( ).

Sarebbe anche possibile cambiare la granulosità dell’appartenenza in modo tale che essa sia basata su un oggetto-da-oggetto, ma questo renderebbe probabilmente la soluzione al problema dell’appartenenza più complessa del problema stesso.

Conservare oggetti per valore

In realtà creare una copia degli oggetti all’interno di un generico contenitore è un problema complesso se non si hanno a disposizione i template. Con i template, le cose sono relativamente semplici – si dice solo che si stanno conservando oggetti invece che puntatori:

//: C16:ValueStack.h
// Conservare oggetti per valore in uno Stack
#ifndef VALUESTACK_H
#define VALUESTACK_H
#include "../require.h"

template<class T, int ssize = 100>
class Stack {
  // Il costruttore di default compie l’inizializzazione 
  // dell’oggetto per ciascun elemento nell’array:
  T stack[ssize];
  int top;
public:
  Stack() : top(0) {}
  // Il costruttore di copia copia l’oggetto nell’array:
  void push(const T& x) {
    require(top < ssize, "Troppi inserimenti eseguiti chiamando push( )");
    stack[top++] = x;
  }
  T peek() const { return stack[top]; }
  // L’oggetto esiste ancora quando lo si recupera; 
  // da questo momento esso semplicemente non è più disponibile:
  T pop() {
    require(top > 0, "Troppe chiamate alla funzione pop()");
    return stack[--top];
  }
};
#endif // VALUESTACK_H ///:~

Il costruttore di copia fa la maggior parte del lavoro per gli oggetti contenuti passando e ritornando gli oggetti per valore. Dentro push( ), la memorizzazione dell’oggetto dentro l’array Stack è compiuta con T::operator=. Per garantire che lavori, una classe detta SelfCounter tiene traccia delle creazioni dell’oggetto e delle copie fatte col costruttore di copia:

//: C16:SelfCounter.h
#ifndef SELFCOUNTER_H
#define SELFCOUNTER_H
#include "ValueStack.h"
#include <iostream>

class SelfCounter {
  static int counter;
  int id;
public:
  SelfCounter() : id(counter++) {
    std::cout << "Creato: " << id << std::endl;
  }
  SelfCounter(const SelfCounter& rv) : id(rv.id){
    std::cout << "Copiato: " << id << std::endl;
  }
  SelfCounter operator=(const SelfCounter& rv) {
    std::cout << "Assegnato " << rv.id << " to " 
              << id << std::endl;
    return *this;
  }
  ~SelfCounter() {
    std::cout << "Distrutto: "<< id << std::endl;
  }
  friend std::ostream& operator<<( 
    std::ostream& os, const SelfCounter& sc){
    return os << "SelfCounter: " << sc.id;
  }
};
#endif // SELFCOUNTER_H ///:~

//: C16:SelfCounter.cpp {O}
#include "SelfCounter.h"
int SelfCounter::counter = 0; ///:~

//: C16:ValueStackTest.cpp
//{L} SelfCounter
#include "ValueStack.h"
#include "SelfCounter.h"
#include <iostream>
using namespace std;

int main() {
  Stack<SelfCounter> sc;
  for(int i = 0; i < 10; i++)
    sc.push(SelfCounter());
  // OK a peek(), il risultato è un(a variabile) temporanea:
  cout << sc.peek() << endl;
  for(int k = 0; k < 10; k++)
    cout << sc.pop() << endl;
} ///:~

Quando un contenitore Stack viene creato, è chiamato il costruttore di default dell’oggetto contenuto per ogni oggetto nell’array. Inizialmente si vedranno 100 oggetti SelfCounter creati senza un’apparente ragione, ma questa è solo l’inizializzazione dell’array. Questo può essere un pò costoso, ma non c’è altro modo in un progetto semplice come questo. Una situazione effettivamente più complessa si presenta se si rende Stack più generico consentendo alle dimensioni di crescere dinamicamente, poichè nell’implementazione mostrata sopra questo includerebbe la creazione di un nuovo (più grande) array, copiare il vecchio array sul nuovo, e distruggere il vecchio array (questo è, appunto, quello che fa la classe vector della libreria Standard C++).

Introduzione agli iteratori

Un iteratore è un oggetto che si muove attraverso un contenitore di altri oggetti e li seleziona uno alla volta, senza fornire un accesso diretto all’implementazione di quel contenitore. Gli iteratori forniscono un modo standard di accedere agli elementi, che un contenitore fornisca un modo di accedere agli elementi direttamente o meno. Si vedranno gli iteratori usati più spesso in associazione con le classi contenitore, e gli iteratori sono un concetto fondamentale nel progetto e nell’uso dei contenitori Standard C++, completamente descritti nel Volume 2 di questo libro (scaricabile da www.BruceEckel.com). Un iteratore è anche un tipo di design pattern, che è il soggetto di un capitolo nel Volume 2.

In molti modi, un iteratore è un “puntatore astuto,” e infatti si noterà che gli iteratori usualmente mimano la maggior parte delle operazioni dei puntatori. Diversamente da un puntatore, tuttavia, l’iteratore è progettato per essere sicuro, così si farà con molta meno probabilità l’equivalente del varcare il limite delle dimensioni di un array (o se succede, si accerta più facilmente).

Si consideri il primo esempio in questo capitolo. Qui è mostrato con l’aggiunta di un semplice iteratore:

//: C16:IterIntStack.cpp
// Semplice stack di interi con iteratori
//{L} fibonacci
#include "fibonacci.h"
#include "../require.h"
#include <iostream>
using namespace std;

class IntStack {
  enum { ssize = 100 };
  int stack[ssize];
  int top;
public:
  IntStack() : top(0) {}
  void push(int i) {
    require(top < ssize, "Troppi inserimenti eseguiti chiamando push( )");
    stack[top++] = i;
  }
  int pop() {
    require(top > 0, "Troppe chiamate alla funzione pop()");
    return stack[--top];
  }
  friend class IntStackIter;
};

// Un iteratore è come un puntatore "astuto":
class IntStackIter {
  IntStack& s;
  int index;
public:
  IntStackIter(IntStack& is) : s(is), index(0) {}
  int operator++() { // Prefisso
    require(index < s.top, 
      "iteratore mosso fuori dal range");
    return s.stack[++index];
  }
  int operator++(int) { // Postfisso
    require(index < s.top, 
      "iteratore mosso fuori dal range");
    return s.stack[index++];
  }
};

int main() {
  IntStack is;
  for(int i = 0; i < 20; i++)
    is.push(fibonacci(i));
  // Attraversamento con un iteratore:
  IntStackIter it(is);
  for(int j = 0; j < 20; j++)
    cout << it++ << endl;
} ///:~

L’ IntStackIter è stato creato per lavorare solo con un IntStack. Si noti che IntStackIter è un friend di IntStack, che gli da l’accesso a tutti gli elementi private di IntStack.

Come un puntatore, il lavoro di IntStackIter è di muoversi attraverso un IntStack e recuperare valori. In questo semplice esempio, l’IntStackIter può muoversi solo in avanti (usando sia la forma pre- che postfissa dell’operator++). Tuttavia, non ci sono confini al modo in cui un iteratore possa essere definito, se non quelli imposti dalle restrizioni del contenitore con cui lavora. E’ perfettamente accettabile per un iteratore (nei limiti del contenitore sottostante) che si muova in qualsiasi modo nell’attraversare il suo contenitore associato e che causi la modifica dei valori contenui.

E’ consueto che un iteratore sia creato con un costruttore che lo unisce ad un singolo oggetto contenitore, e che l’iteratore non sia connesso a diversi contenitori durante il suo tempo di vita. (Gli iteratori sono usualmente piccoli e poco costosi, così si può facilmente farne un altro.)

Con l’iteratore, possiamo attraversare gli elementi dello stack senza recuperarli, proprio come un puntatore può spostarsi lungo gli elementi di un array. Tuttavia, l’iteratore conosce la sottostante struttura dello stack e come attraversare gli elementi, così anche se ci stiamo muovendo attraverso essi all’apparenza “incrementando un puntatore,” ciò che succede sotto sotto è più complicato. Questa è la chiave dell’iteratore: sta astraendo il complicato processo del movimento da un elemento del contenitore al successivo in qualcosa che sembra un puntatore. L’obiettivo è avere per ogni iteratore nel nostro programma la stessa interfaccia cosicchè qualsiasi codice che usi l’iteratore non si preoccupi di che cosa esso stia puntando – sa solo che può riposizionare tutti gli iteratori nello stesso modo, così non ha alcuna importanza il contenitore al quale l’iteratore punta. In questo modo è possibile scrivere codice più generico. Tutti i contenitori e gli algoritmi nell libreria Standard C++ Library sono basati su questo principio degli iteratori.

Per aiutare a rendere le cose più generiche, sarebbe carino essere in grado di dire “ogni contenitore ha una classe associata chiamata iteratore,” ma questo tipicamente causerà problemi con il dare i nomi. La soluzione è aggiungere una classe iterator annidata a ciascun contenitore (si noti che in questo caso, “iterator” inizia con una lettera minuscola cosicchè sia conforme allo stile della libreria Standard C++). Qui c’è IterIntStack.cpp con un iterator annidato:

//: C16:NestedIterator.cpp
// Annidare un iteratore all’interno del contenitore
//{L} fibonacci
#include "fibonacci.h"
#include "../require.h"
#include <iostream>
#include <string>
using namespace std;

class IntStack {
  enum { ssize = 100 };
  int stack[ssize];
  int top;
public:
  IntStack() : top(0) {}
  void push(int i) {
    require(top < ssize, "Troppi inserimenti eseguiti chiamando push( )");
    stack[top++] = i;
  }
  int pop() {
    require(top > 0, "Troppe chiamate alla funzione pop()");
    return stack[--top];
  }
  class iterator;
  friend class iterator;
  class iterator {
    IntStack& s;
    int index;
  public:
    iterator(IntStack& is) : s(is), index(0) {}
    // Per creare l’iteratore "sentinella della fine":
    iterator(IntStack& is, bool) 
      : s(is), index(s.top) {}
    int current() const { return s.stack[index]; }
    int operator++() { // Prefisso
      require(index < s.top, 
        "iteratore mosso fuori dal range");
      return s.stack[++index];
    }
    int operator++(int) { // Postfisso
      require(index < s.top, 
        "iteratore mosso fuori dal range");
      return s.stack[index++];
    }
    // Salta un iteratore avanti
    iterator& operator+=(int amount) {
      require(index + amount < s.top,
        "IntStack::iterator::operator+=() "
        "provato a muovere fuori dai confini");
      index += amount;
      return *this;
    }
    // Per vedere se sei alla fine:
    bool operator==(const iterator& rv) const {
      return index == rv.index;
    }
    bool operator!=(const iterator& rv) const {
      return index != rv.index;
    }
    friend ostream& 
    operator<<(ostream& os, const iterator& it) {
      return os << it.current();
    }
  };
  iterator begin() { return iterator(*this); }
  // Crea la "sentinella della fine":
  iterator end() { return iterator(*this, true);}
};

int main() {
  IntStack is;
  for(int i = 0; i < 20; i++)
    is.push(fibonacci(i));
  cout << "Attraversa l’intero IntStack\n";
  IntStack::iterator it = is.begin();
  while(it != is.end())
    cout << it++ << endl;
  cout << "Attraversa una porzione dell’IntStack\n";
  IntStack::iterator 
    start = is.begin(), end = is.begin();
  start += 5, end += 15;
  cout << "start = " << start << endl;
  cout << "end = " << end << endl;
  while(start != end)
    cout << start++ << endl;
} ///:~

Quando si crea una classe friend annidata, si deve fare attraverso il processo di dichiarare, prima, il nome della classe, quindi dichiararla come una friend, infine definire la classe. Altrimenti , il compilatore andrà in confusione.

E’ stata aggiunta qualche nuova distorsione all’iteratore. La funzione membro current( ) produce l’elemento nel contenitore che l’iteratore sta selezionando correntemente. Si può (far) “saltare” un iteratore in avanti di un arbitrario numero di elementi usando operator+=. Inoltre, si vedranno due operatori sovraccaricati: == and != che confronteranno un iteratore con un altro. Questi possono confrontare qualsiasi due IntStack::iterators, ma sono progettati soprattutto come test per vedere se l’iteratore è alla fine della sequenza nello stesso modo in cui fanno i “reali” iteratori della libreria Standard C++. L’idea è che due iteratori definiscono un range, che va dal primo elemento puntato dal primo iteratore incluso fino all’ultimo elemento puntato dal secondo iteratore non incluso. Così se ci vogliamo muovere attraverso il range definito dai due iteratori, diciamo qualcosa del genere:

  while(start != end)
  cout << start++ << endl;

dove start e end sono i due iteratori nel range. Si noti che l’iteratore end, al quale spesso ci riferiamo come la sentinella della fine, non sia deferenziato e sia là solo per dire che siamo alla fine della sequenza. Allora rappresenta “uno oltre la fine.”

Gran parte del tempo vorremo muoverci attraverso l’intera sequenza in un contenitore, così il contenitore ha bisogno di un qualche modo per produrre gli iteratori che indichino l’inizio della sequenza e la sentinella della fine. Qui, come nella libreria Standard C++, questi iteratori sono prodotti dalle funzioni membro del contenitore begin( ) e end( ). begin( ) usa il primo costruttore di iterator che di default punta all’inizio del contenitore (questo è il primo elemento inserito nello stack). Tuttavia, un secondo costruttore, usato da end( ), è necessario per creare l’iteratore sentinella della fine. Essere “alla fine” significa puntare alla cima (top) dello stack, poichè top indica sempre il prossimo spazio disponibile – ma non usato – sullo stack. Questo costruttore di iterator prende un secondo argomento di tipo bool, che è una variabile fittizia (che serve solo) per distinguere i due costruttori.

I numeri di Fibonacci sono usati ancora per riempire l’IntStack in main( ), e gli iteratori sono usati per muoversi attraverso l’intero IntStack e anche all’interno di un range ristretto della sequenza.

Il prossimo passo, naturalmente, è rendere il codice generico templatizzandolo sul tipo che conserva, cosicchè invece di essere forzati a conservare solo ints possiamo conservare qualsiasi tipo:

//: C16:IterStackTemplate.h
// Semplice stack template con iteratore annidato
#ifndef ITERSTACKTEMPLATE_H
#define ITERSTACKTEMPLATE_H
#include "../require.h"
#include <iostream>

template<class T, int ssize = 100>
class StackTemplate {
  T stack[ssize];
  int top;
public:
  StackTemplate() : top(0) {}
  void push(const T& i) {
    require(top < ssize, "Troppi inserimenti eseguiti chiamando push( )");
    stack[top++] = i;
  }
  T pop() {
    require(top > 0, "Troppe chiamate alla funzione pop()");
    return stack[--top];
  }
  class iterator; // Dichiarazione richiesta
  friend class iterator; // Lo rende un friend
  class iterator { // Ora lo definiamo
    StackTemplate& s;
    int index;
  public:
    iterator(StackTemplate& st): s(st),index(0){}
    // Per creare l’iteratore "sentinella della fine":
    iterator(StackTemplate& st, bool) 
      : s(st), index(s.top) {}
    T operator*() const { return s.stack[index];}
    T operator++() { // Forma prefissa
      require(index < s.top, 
        "iteratore mosso fuori dal range");
      return s.stack[++index];
    }
    T operator++(int) { // Forma postfissa
      require(index < s.top, 
        "iteratore mosso fuori dal range");
      return s.stack[index++];
    }
    // Salta un iteratore in avanti
    iterator& operator+=(int amount) {
      require(index + amount < s.top,
        " StackTemplate::iterator::operator+=() "
        "provato a muovere fuori dai confini");
      index += amount;
      return *this;
    }
    // Per vedere se sei alla fine:
    bool operator==(const iterator& rv) const {
      return index == rv.index;
    }
    bool operator!=(const iterator& rv) const {
      return index != rv.index;
    }
    friend std::ostream& operator<<(
      std::ostream& os, const iterator& it) {
      return os << *it;
    }
  };
  iterator begin() { return iterator(*this); }
  // Crea la "sentinella della fine":
  iterator end() { return iterator(*this, true);}
};
#endif // ITERSTACKTEMPLATE_H ///:~

Si può vedere che la trasformazione da una classe regolare ad un template è ragionevolmente trasparente. Questo approccio di creare e debaggare prima una classe ordinaria, e poi di renderla un template, è generalmente considerato essere più semplice che creare il template da zero.

Si noti che invece di dire solo:

friend iterator; // Lo rende un friend

Questo codice ha:

friend class iterator; // Lo rende un friend

Questo è importante poichè il nome “iterator” è già nello scope, da un file incluso.

Invece della funzione membro current( ), l’ iterator ha un operator* per selezionare l’elemento corrente, che fa l’iterator molto più simile ad un puntatore ed è una pratica comune.

Qui c’è l’esempio modificato per testare il template:

//: C16:IterStackTemplateTest.cpp
//{L} fibonacci
#include "fibonacci.h"
#include "IterStackTemplate.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

int main() {
  StackTemplate<int> is;
  for(int i = 0; i < 20; i++)
    is.push(fibonacci(i));
  // Attraversa con un iteratore:
  cout << "Attraversa l’intero StackTemplate\n";
  StackTemplate<int>::iterator it = is.begin();
  while(it != is.end())
    cout << it++ << endl;
  cout << "Attraversa una porzione\n";
  StackTemplate<int>::iterator 
    start = is.begin(), end = is.begin();
  start += 5, end += 15;
  cout << "start = " << start << endl;
  cout << "end = " << end << endl;
  while(start != end)
    cout << start++ << endl;
  ifstream in("IterStackTemplateTest.cpp");
  assure(in, "IterStackTemplateTest.cpp");
  string line;
  StackTemplate<string> strings;
  while(getline(in, line))
    strings.push(line);
  StackTemplate<string>::iterator 
    sb = strings.begin(), se = strings.end();
  while(sb != se)
    cout << sb++ << endl;
} ///:~

Il primo uso dell’iteratore lo fa soltanto marciare dall’inizio alla fine (e mostra che la sentinella della fine lavora correttamente). Nel secondo uso, si può vedere come gli iteratori ci consentano di specificare facilmente un range di elementi (i contenitori e gli iteratori nella libreria Standard C++ usano questo concetto di range quasi ovunque). La funzione sovraccaricata operator+= sposta gli iteratori start e end alle posizioni nella metà del range degli elementi in is, e questi elementi sono stampati. Si noti nell’uscita che la sentinella della fine non è inclusa nel range, allora può essere uno oltre la fine del range per consentire a noi di sapere che abbiamo superato la fine – ma non si deferenzia la sentinella della fine, altrimenti si può finire per deferenziare un puntatore null. (io ho inserito un guardiano nel StackTemplate::iterator, ma nei contenitori e negli iteratori della libreria Standard C++ tale codice non c’è – per ragioni di efficienza – così è necessario prestare attenzione.)

Infine, per verificare che lo StackTemplate lavora con oggetti di classe, ne è istanziato uno per string e riempito con le linee del file del codice sorgente, che sono quindi stampate in uscita.

Stack con iteratori

Noi possiamo ripetere il processo con la classe Stack dinamicamente dimensionata che è stata usata come esempio nel libro. Qui c’è la classe Stack con un iteratore annidato mescolato nella miscela:

//: C16:TStack2.h
// Stack templatizzato con iteratore annidato
#ifndef TSTACK2_H
#define TSTACK2_H

template<class T> class Stack {
  struct Link {
    T* data;
    Link* next;
    Link(T* dat, Link* nxt)
      : data(dat), next(nxt) {}
  }* head;
public:
  Stack() : head(0) {}
  ~Stack();
  void push(T* dat) {
    head = new Link(dat, head);
  }
  T* peek() const { 
    return head ? head->data : 0;
  }
  T* pop();
  // Classe iteratore annidato:
  class iterator; // Dichiarazione richiesta
  friend class iterator; // Lo rende un friend
  class iterator { // Ora lo definiamo
    Stack::Link* p;
  public:
    iterator(const Stack<T>& tl) : p(tl.head) {}
    // Costruttore di copia:
    iterator(const iterator& tl) : p(tl.p) {}
    // L’iteratore sentinella della fine:
    iterator() : p(0) {}
    // operator++ ritorna un valore booleano che indica la fine:
    bool operator++() {
      if(p->next)
        p = p->next;
      else p = 0; // Indica la fine della lista
      return bool(p);
    }
    bool operator++(int) { return operator++(); }
    T* current() const {
      if(!p) return 0;
      return p->data;
    }
    // Operatore di deferenziazione di puntatore:
    T* operator->() const { 
      require(p != 0, 
        "PStack::iterator::operator->returns 0");
      return current(); 
    }
    T* operator*() const { return current(); }
    // conversione di bool per test condizionale:
    operator bool() const { return bool(p); }
    // Confronto per testare la fine:
    bool operator==(const iterator&) const {
      return p == 0;
    }
    bool operator!=(const iterator&) const {
      return p != 0;
    }
  };
  iterator begin() const { 
    return iterator(*this); 
  }
  iterator end() const { return iterator(); }
};

template<class T> Stack<T>::~Stack() {
  while(head)
    delete pop();
}

template<class T> T* Stack<T>::pop() {
  if(head == 0) return 0;
  T* result = head->data;
  Link* oldHead = head;
  head = head->next;
  delete oldHead;
  return result;
}
#endif // TSTACK2_H ///:~

Si noterà anche che la classe è stata cambiata per supporatre l’appartenenza, che ora lavora poichè la classe conosce il tipo esatto (o almeno il tipo base, che lavorerà assumendo che siano usati distruttori virtuali). Di default il contenitore distrugge i suoi oggetti ma noi siamo responsabili per qualsiasi puntatore che inseriamo (tramite pop( )).

L’iteratore è semplice, e fisicamente molto piccolo – ha le dimensioni di un singolo puntatore. Quando creiamo un iteratore, esso è inizializzato alla testa della lista collegata, e possiamo solo incrementarlo in avanti attraverso la lista. Se vogliamo cominciare sopra all’inizio, creiamo un nuovo iteratore, e se vogliamo ricordare un punto nella lista, creiamo un nuovo iteratore dall’iteratore esistente che punta in quel punto (usando il costruttore di copia dell’iteratore).

Per chiamare funzioni per l’oggetto cui si riferisce l’iteratore, si può usare la funzione current( ), l’ operator*, o l’operatore di deferenziazione del puntatore operator-> (una vista comune negli iteratori). L’ultimo ha un’implementazione che sembra identica a quella di current( ) poichè restituisce un puntatore all’oggetto corrente, ma è diversa perchè l’operatore di deferenziazione di puntatore compie livelli extra di deferenziazione (vedere il Capitolo 12).

La classe iterator segue la forma che abbiamo visto nell’esempio precedente. class iterator è annidato all’interno della classe contenitore, contiene i costruttori per creare sia un iteratore che punti ad un elemento nel contenitore che un iteratore “sentinella della fine”, e la classe contenitore ha i metodi begin( ) e end( ) per produrre questi iteratori. (Quando impareremo di più circa la libreria Standard C++ , vedremo che i nomi iterator, begin( ), e end( ) che sono usati qui sono stati chiaramente elevati a classi contenitore standard. Alla fine di questo capitolo, si vedrà che questo consente a queste classi contenitore di essere usate come se fossero classi contenitore della libreria Standard C++.)

L’intera implementazione è contenuta nell’header file, quindi non c’è un file cpp separato. Qui c’è un piccolo test che esercita l’iteratore:

//: C16:TStack2Test.cpp
#include "TStack2.h"
#include "../require.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

int main() {
  ifstream file("TStack2Test.cpp");
  assure(file, "TStack2Test.cpp");
  Stack<string> textlines;
  // Legge il file e carica le linee nello Stack:
  string line;
  while(getline(file, line))
    textlines.push(new string(line));
  int i = 0;
  // Usa l’iteratore per stampare linee dalla lista:
  Stack<string>::iterator it = textlines.begin();
  Stack<string>::iterator* it2 = 0;
  while(it != textlines.end()) {
    cout << it->c_str() << endl;
    it++;
    if(++i == 10) // Ricorda la decima linea
      it2 = new Stack<string>::iterator(it);
  }
  cout << (*it2)->c_str() << endl;
  delete it2;
} ///:~

Uno Stack è istanziato per conservare oggetti string e riempito con linee prese da un file. Quindi è creato un iteratore e usato per muoversi attraverso la sequenza. La decima linea è memorizzata da un secondo iteratore generato dal primo dal costruttore di copia; in seguito questa linea è stampata e l’iteratore – creato dinamicamente – è distrutto. Qui, la creazione dinamica di un oggetto è usata per controllare il tempo di vita dell’oggetto.

PStash con iteratori

Per la maggior parte delle classi contenitore ha senso avere un iteratore. Qui c’è un iteratore aggiunto alla classe PStash :

//: C16:TPStash2.h
// PStash templatizzata con iteratore annidato
#ifndef TPSTASH2_H
#define TPSTASH2_H
#include "../require.h"
#include <cstdlib>

template<class T, int incr = 20>
class PStash {
  int quantity;
  int next;
  T** storage;
  void inflate(int increase = incr);
public:
  PStash() : quantity(0), storage(0), next(0) {}
  ~PStash();
  int add(T* element);
  T* operator[](int index) const;
  T* remove(int index);
  int count() const { return next; }
  // Classe iteratore annidata:
  class iterator; // Dichiarazione richiesta
  friend class iterator; // Lo rende un friend
  class iterator { // Ora lo definiamo
    PStash& ps;
    int index;
  public:
    iterator(PStash& pStash)
      : ps(pStash), index(0) {}
    // Per creare la sentinella della fine:
    iterator(PStash& pStash, bool)
      : ps(pStash), index(ps.next) {}
    // Costruttore di copia:
    iterator(const iterator& rv)
      : ps(rv.ps), index(rv.index) {}
    iterator& operator=(const iterator& rv) {
      ps = rv.ps;
      index = rv.index;
      return *this;
    }
    iterator& operator++() {
      require(++index <= ps.next,
        "PStash::iterator::operator++ "
        "muove l’indice oltre i confini");
      return *this;
    }
    iterator& operator++(int) {
      return operator++();
    }
    iterator& operator--() {
      require(--index >= 0,
        "PStash::iterator::operator-- "
        "muove l’indice oltre i confini");
      return *this;
    }
    iterator& operator--(int) { 
      return operator--();
    }
    // Fa saltare l’iteratore avanti o indietro:
    iterator& operator+=(int amount) {
      require(index + amount < ps.next && 
        index + amount >= 0, 
        "PStash::iterator::operator+= "
        "tentativo di indicizzare oltre i limiti");
      index += amount;
      return *this;
    }
    iterator& operator-=(int amount) {
      require(index - amount < ps.next && 
        index - amount >= 0, 
        "PStash::iterator::operator-= "
        "tentativo di indicizzare oltre i limiti");
      index -= amount;
      return *this;
    }
    // Crea un nuovo iteratore che è mosso in avanti
    iterator operator+(int amount) const {
      iterator ret(*this);
      ret += amount; // op+= fa un controllo sui limiti
      return ret;
    }
    T* current() const {
      return ps.storage[index];
    }
    T* operator*() const { return current(); }
    T* operator->() const { 
      require(ps.storage[index] != 0, 
        "PStash::iterator::operator->returns 0");
      return current(); 
    }
    // Rimuove l’elemento corrente:
    T* remove(){
      return ps.remove(index);
    }
    // Test di confronto per la fine:
    bool operator==(const iterator& rv) const {
      return index == rv.index;
    }
    bool operator!=(const iterator& rv) const {
      return index != rv.index;
    }
  };
  iterator begin() { return iterator(*this); }
  iterator end() { return iterator(*this, true);}
};

// Distruzione degli oggetti contenuti:
template<class T, int incr>
PStash<T, incr>::~PStash() {
  for(int i = 0; i < next; i++) {
    delete storage[i]; // Puntatori Null OK
    storage[i] = 0; // Solo per essere sicuri
  }
  delete []storage;
}

template<class T, int incr>
int PStash<T, incr>::add(T* element) {
  if(next >= quantity)
    inflate();
  storage[next++] = element;
  return(next - 1); // Indice
}

template<class T, int incr> inline
T* PStash<T, incr>::operator[](int index) const {
  require(index >= 0,
    "PStash::operator[] indice negativo");
  if(index >= next)
    return 0; // Per indicare la fine
  require(storage[index] != 0, 
    "PStash::operator[] ha restituito un puntatore nullo");
  return storage[index];
}

template<class T, int incr>
T* PStash<T, incr>::remove(int index) {
  // operator[] attua controlli di validità:
  T* v = operator[](index);
  // "Rimuove" il puntatore:
  storage[index] = 0;
  return v;
}

template<class T, int incr>
void PStash<T, incr>::inflate(int increase) {
  const int tsz = sizeof(T*);
  T** st = new T*[quantity + increase];
  memset(st, 0, (quantity + increase) * tsz);
  memcpy(st, storage, quantity * tsz);
  quantity += increase;
  delete []storage; // Vecchia memoria
  storage = st; // Punta alla nuova memoria
}
#endif // TPSTASH2_H ///:~

La maggior parte di questo file è una traslazione chiaramente semplice di entrambi i precedenti PStash e dell’iterator annidato in un template. Questa volta, tuttavia, gli operatori restituiscono riferimenti all’iteratore corrente, che è il più tipico e flessibile approccio da prendere.

Il distruttore chiama delete per tutti i puntatori contenuti, e poichè il tipo è catturato dal template, avrà luogo la distruzione corretta. Si dovrebbe essere a conoscenza del fatto che se il contenitore conserva puntatori ad un tipo della classe base, questo tipo dovrebbe avere un distruttore virtuale per assicurare la cancellazione corretta degli oggetti derivati i cui indirizzi sono stati castati all’insù nel momento in cui sono stati inseriti nel contenitore.

Il PStash::iterator segue il modello dell’iteratore di legare l’oggetto per il suo tempo di vita ad un singolo contenitore. In più, il costruttore di copia ci consente di fare un nuovo iteratore che punta alla stessa locazione dell’iteratore esistente da cui è creato, realizzando effettivamente un segnalibro nel contenitore. Le funzioni membro operator+= e operator-= consentono di muovere un iteratore di un numero di punti, rispettando i confini del contenitore. Gli operatori sovraccaricati di incremento e decremento muovono l’iteratore di una posizione. L’operator+ produce un nuovo iteratore che è mosso in avanti dell’ammontare dell’addendo. Come nel precedente esempio, gli operatori di deferenzazione del puntatore sono usati per operare sull’elemento al quale si riferisce l’iteratore, e remove( ) distrugge l’oggetto corrente chiamando il remove( ) del contenitore.

Lo stesso tipo di codice visto sopra (a la i contenitori della Libreria Standard C++) è usato per creare la sentinella della fine: un secondo costruttore, la funzione membro end( ) del contenitore e gli operatori operator== e operator!= per il confronto.

Il seguente esempio crea e testa due diversi tipi di oggetti Stash, uno per una nuova classe chiamata Int che annuncia la sua costruzione e la sua distruzione e una che conserva oggetti della classe string della Libreria Standard.

//: C16:TPStash2Test.cpp
#include "TPStash2.h"
#include "../require.h"
#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Int {
  int i;
public:
  Int(int ii = 0) : i(ii) {
    cout << ">" << i << ' ';
  }
  ~Int() { cout << "~" << i << ' '; }
  operator int() const { return i; }
  friend ostream&
    operator<<(ostream& os, const Int& x) {
      return os << "Int: " << x.i;
  }
  friend ostream&
    operator<<(ostream& os, const Int* x) {
      return os << "Int: " << x->i;
  }
};

int main() {
  { // Per forzare la chiamata del distuttore
    PStash<Int> ints;
    for(int i = 0; i < 30; i++)
      ints.add(new Int(i));
    cout << endl;
    PStash<Int>::iterator it = ints.begin();
    it += 5;
    PStash<Int>::iterator it2 = it + 10;
    for(; it != it2; it++)
      delete it.remove(); // Rimozione di default
    cout << endl;
    for(it = ints.begin();it != ints.end();it++)
      if(*it) // Remove() causa "buchi"
        cout << *it << endl;
  } // qui è chiamato il distruttore di "ints" 
  cout << "\n-------------------\n";  
  ifstream in("TPStash2Test.cpp");
  assure(in, "TPStash2Test.cpp");
  // Istanzazione per String:
  PStash<string> strings;
  string line;
  while(getline(in, line))
    strings.add(new string(line));
  PStash<string>::iterator sit = strings.begin();
  for(; sit != strings.end(); sit++)
    cout << **sit << endl;
  sit = strings.begin();
  int n = 26;
  sit += n;
  for(; sit != strings.end(); sit++)
    cout << n++ << ": " << **sit << endl;
} ///:~

Per convenienza, Int ha un ostream operator<< associato sia per un Int& che per un Int*.

Il primo blocco di codice in main( ) è circondato dalle parentesi graffe per forzare la distruzione del PStash<Int> e quindi la pulizia automatica operata da quel distruttore. Un range di elementi è rimosso e cancellato a mano per mostrare che PStash cancella il resto.

Per entrambe le istanze di PStash, viene creato un iteratore ed usato per muoversi nel contenitore. Si noti l’eleganza ottenuta usando questi costrutti; non ci si affligga con i dettagli dell’implementazione dell’uso di un array. Si dice agli oggetti contenitore e iteratore cosa fare, non come. Questo rende la soluzione più facile da concettualizzare, da realizzare, e da modificare.

Perchè gli iteratori?

Finora abbiamo visto i meccanismi degli iteratori, ma capire perchè siano così importanti richiede un esempio più complesso.

E’ comune vedere il polimorfismo, la creazione di oggetti dinamici, e i contenitori usati tutti insieme in un vero programma orientato agli oggetti. I contenitori e la creazione di oggetti dinamici risolvono il problema della mancata conoscenza di quanti o di che tipo di oggetti avremo bisogno. E se il contenitore è configurato per conservare puntatori a oggetti di una classe base, avviene un cast all’insù ogni volta che si inserisce un puntatore ad una clase derivata nel contenitore (con i benefici associati di organizzazione e di estensibilità del codice). Come codice finale nel Volume 1 di questo libro, questo esempio forzerà anche insieme diversi aspetti di tutto ciò che abbiamo imparato finora – si si riesce a seguire questo esempio, allora si è pronti per il Volume 2.

Supponiamo di stare creando un programma che consenta all’utente di editare e di produrre diversi tipi di disegni. Ciascun disegno è un oggetto che contiene una collezione di oggetti Shape:

//: C16:Shape.h
#ifndef SHAPE_H
#define SHAPE_H
#include <iostream>
#include <string>

class Shape {
public:
  virtual void draw() = 0;
  virtual void erase() = 0;
  virtual ~Shape() {}
};

class Circle : public Shape {
public:
  Circle() {}
  ~Circle() { std::cout << "Circle::~Circle\n"; }
  void draw() { std::cout << "Circle::draw\n";}
  void erase() { std::cout << "Circle::erase\n";}
};

class Square : public Shape {
public:
  Square() {}
  ~Square() { std::cout << "Square::~Square\n"; }
  void draw() { std::cout << "Square::draw\n";}
  void erase() { std::cout << "Square::erase\n";}
};

class Line : public Shape {
public:
  Line() {}
  ~Line() { std::cout << "Line::~Line\n"; }
  void draw() { std::cout << "Line::draw\n";}
  void erase() { std::cout << "Line::erase\n";}
};
#endif // SHAPE_H ///:~

Questo usa la classica struttura di funzioni virtuali nella classe base che sono riscritte nella classe derivata. Si noti che la classe Shape include un distruttore virtuale , qualcosa che dovremmo automticamente aggiungere ad ogni classe con funzioni virtuali. Se un contenitore conserva puntatori o riferimenti ad oggetti Shape, allora quando sono chiamati i distruttori virtuali per questi oggetti ogni cosa sarà cancellata correttamente.

Ciascun diverso tipo di disegno nel seguente esempio fa uso di un diverso tipo di classe contenitore teplatizzata: la PStash e la Stack che sono state definite in questo capitolo, e la classe vector dalla Libreira C++. L’“uso”’ dei contenitori è estremamente semplice, ed in generale l’ereditarietà potrebbe non essere l’approccio migliore (la composizione potrebbe avere più senso), ma in questo caso l’ereditarietà è un approccio semplice e non riduce il valore del punto fatto nell’esempio.

//: C16:Drawing.cpp
#include <vector> // Usa anche vettori Standard!
#include "TPStash2.h"
#include "TStack2.h"
#include "Shape.h"
using namespace std;

// Un disegno (Drawing) è innanzitutto un contenitore di figure (Shapes):
class Drawing : public PStash<Shape> {
public:
  ~Drawing() { cout << "~Drawing" << endl; }
};

// Un piano (Plan) è un contenitore diverso di figure:
class Plan : public Stack<Shape> {
public:
  ~Plan() { cout << "~Plan" << endl; }
};

// Uno Schema (Schematic) è un contenitore diverso di figure:
class Schematic : public vector<Shape*> {
public:
  ~Schematic() { cout << "~Schematic" << endl; }
};

// Una funzione template:
template<class Iter>
void drawAll(Iter start, Iter end) {
  while(start != end) {
    (*start)->draw();
    start++;
  }
}

int main() {
  // Ciascun tipo di contenitore ha
  // una differente interfaccia:
  Drawing d;
  d.add(new Circle);
  d.add(new Square);
  d.add(new Line);
  Plan p;
  p.push(new Line);
  p.push(new Square);
  p.push(new Circle);
  Schematic s;
  s.push_back(new Square);
  s.push_back(new Circle);
  s.push_back(new Line);
  Shape* sarray[] = { 
    new Circle, new Square, new Line 
  };
  // Gli iteratori e la funzione template
  // consentono loro di essere trattati genericamente:
  cout << "Drawing d:" << endl;
  drawAll(d.begin(), d.end());
  cout << "Plan p:" << endl;
  drawAll(p.begin(), p.end());
  cout << "Schematic s:" << endl;
  drawAll(s.begin(), s.end());
  cout << "Array sarray:" << endl;
  // Lavora anche con i puntatori di array:
  drawAll(sarray, 
    sarray + sizeof(sarray)/sizeof(*sarray));
  cout << "Fine di main" << endl;
} ///:~

I diversi tipi di contenitori conservano tutti puntatori a Shape e puntatori a oggetti castati all’insù di classi derivate da Shape. Tuttavia, a causa del polimorfismo, avrà luogo l’appropriato comportamento anche quando sono chiamate le funzioni virtuali.

Si noti che sarray, l’array di Shape*, può anche essere pensato come un contenitore.

Funzioni template

In drawAll( ) si vede qualcosa di nuovo. Fino ad ora in questo capitolo abbiamo usato solo classi template, che istanziano nuove classi basate su uno o più parametri di tipo. Tuttavia, si può altrettanto facilmente creare funzioni template, che creano nuove funzioni basate su parametri di tipo. La ragione per cui si crea una funzione template è la stessa per cui si usa una classe template: si sta provando a creare un codice generico, e si fa questo ritardando la specifica di uno o più tipi. Abbiamo bisogno di dire soltanto che questi parametri di tipo supportano certe operazioni, non esattamente che tipi siano.

La funzione template drawAll( ) può essere pensata come un algoritmo (e questo è il modo in cui sono chiamate la maggior parte delle funzioni template nella libreria Standard C++). Questo dice solo come fare qualcosa dati gli iteratori che descrivono un range di elementi, a condizione che questi iteratori possano essere deferenziati, incrementati e confrontati. Questi sono esattamente il tipo di iteratori che abbiamo sviluppato in questo capitolo, ed anche – non è una coincidenza – il tipo di iteratori che sono prodotti dai contenitori nella Libreria Standard C++, evidenziati dall’uso di vector in questo esempio.

Ci piacerebbe anche che drawAll( ) sia un algoritmo generico, cosicchè i contenitori possano essere di qualsiasi tipo e noi non dobbiamo scrivere una nuova versione dell’algoritmo per ogni tipo diverso di contenitore. Ecco dove le funzioni template sono essenziali, poichè esse generano automaticamente il codice specifico per ciascun diverso tipo di contenitore. Ma senza l’extra apportato dagli iteratori alla proprietà di essere pianificato non direttamente per qualcosa, questa genericità non sarebbe possibile. Questo è il motivo per cui gli iteratori sono importanti; ci consentono di scrivere un codice general-purpose (progettato o fruibile per più di un solo uso) che includa contenitori senza conoscere la struttura sottostante del contenitore. (Si noti che, in C++, gli iteratori e gli algoritmi generici richiedono le funzioni template per funzionare.)

Si può vedere la dimostrazione di questo in main( ), poichè drawAll( ) lavora senza cambiamenti con ciascun diverso tipo di contenitore. E ancor più interessante, drawAll( ) lavora anche con i puntatori all’inizio e alla fine dell’array sarray. Questa abilità di trattare gli array come contenitori è essenziale per il progetto della Libreria Standard C++, i cui algoritmi assomigliano molto a drawAll( ).

Poichè le classi contenitore template sono raramente soggette all’ereditarietà e al casting all’insù che vediamo con le classi “ordinarie”, non vedremo quasi mai funzioni virtuali nelle classi contenitore. Il riuso delle classi contenitore è implementato con i template, non con l’ereditarietà.

Sommario

Le classi conteniore sono una parte essenziale della programmazione orientata agli oggetti. Esse sono un altro modo di semplificare e nascondere i dettagli di un programma e di velocizzare il processo di sviluppo del programma. Inoltre, forniscono un ampio apporto di sicurezza e flessibilità sostituendo i primitivi array e le tecniche relativamente grezze della struttura di dati scoperti in C.

Poichè il programmatore cliente ha bisogno di contenitori, è essenziale che essi siano facili da usare. Qui ci venono in aiuto i template. Con i template la sintassi per il riuso del codice sorgente (opposto al riuso del codice oggetto fornito dall’ereditarietà e dalla composizione) diventa abbastanza banale (pure) per l’utente inesperto. Infatti, riusare il codice con i template è notevolmente più facile che con l’ereditarietà e la composizione.

Nonostante si sia imparato a creare classi contenitore e iteratore in questo libro, in pratica è molto più conveniente imparare contenitori e iteratori nella Libreria Standard C++ , poichè ci si può aspettare che essi siamo disponibili con ogni compilatore. Come si vedrà nel Volume 2 di questo libro (scaricabile da www.BruceEckel.com), i contenitori e gli algoritmi nella Libreria Standard C++ soddisferanno virtualmente sempre le nostre necessità cos non dovremo crearne di nuovi.

Le questioni connesse alla progettazione di una classe contenitore sono state appena accennate in questo capitolo, ma il lettore può arguire che possono andare ben oltre. Una libreria di classi contenitore complicata può coprire tutti i tipi di questioni aggiuntive, incluso il multithreading, la persistenza e il garbage collection (letteralmente "accumulo di immondizia", riguarda dati non corretti, effetti collaterali, perdita di informazioni e simili, ndt).

Esercizi

Le soluzioni agli esercizi selezionati possono essere trovate nel documento elettronico The Thinking in C++ Annotated Solution Guide, disponibile dietro un piccolo compenso su www.BruceEckel.com.

  1. Implementare la gerarchia di ereditarietà nel diagramma OShape in questo capitolo.
  2. Modificare il risultato dell’Esercizio 1 del Capitolo 15 al fine di usare lo Stack e iterator in TStack2.h al posto di un array di puntatori a Shape. Aggiungere i distruttori alla gerarchia di classe così si potrà vedere che gli oggetti Shape sono distrutti quando lo Stack esce dallo scope.
  3. Modificare TPStash.h cosicchè il valore di incremento usato da inflate( ) possa essere cambiato durante il tempo di vita di un particolare oggetto contenitore.
  4. Modificare TPStash.h cosicchè il valore di incremento usato da inflate( ) ridimensioni automaticamente se stesso per ridurre il numero di volte che esso necessita di essere chiamato. Per esempio, ogni volta che è chiamato potrebbe raddoppiare il valore dell’incremento da usare nella successiva chiamata. Dimostrare questa funzionalità segnalando ogni chiamata di inflate( ), e si scriva un codice di test in main( ).
  5. Templatizzare la funzione di fibonacci( ) sul tipo di valore che essa produce (così può produrre long, float, ecc. invece di soli int).
  6. Usando la Libreria Standard C++ vector come implementazione sottostante, creare una classe template Set che accetti solo uno di ciascun tipo di oggetto che si inserisce in essa. Fare una classe annidata iterator che supporti la “sentinella della fine” concepita in questo capitolo. Scrivere codice di test per il proprio Set in main( ), e quindi sostituire la Libreria Standard C++ set template per verificare che il comportamento sia corretto.
  7. Modificare AutoCounter.h cosicchè possa essere usato come un oggetto membro dentro qualsiasi classe di cui si voglia tracciare la creazione e distruzione. Aggiungere un membro string per conservare il nome della classe. Testare questa applicazione dentro una classe propria.
  8. Creare una versione di OwnerStack.h che usi una Libreria Standard C++ vector come sua implementazione sottostante. Può essere necessario dare uno sguardo a qualche funzione membro di vector allo scopo di fare questo (o solo guardare l’header file di <vector>).
  9. Modificare ValueStack.h cosicchè si espanda automaticamente nel momento in cui si inseriscano con push( ) più oggetti ed esaurisca lo spazio. Cambiare ValueStackTest.cpp per testare la nuova funzionalità.
  10. Ripetere l’Esercizio 9 ma si usi una Libreria Standard C++ vector come rappresentazione interna del ValueStack. Si noti quanto questo sia più facile.
  11. Modificare ValueStackTest.cpp cosicchè usi una Libreria Standard C++ vector invece di uno Stack in main( ). Si noti il comportamento a run-time: vector crea automaticamente un sacco di oggetti di deafult quando è creato?
  12. Modificare TStack2.h cosicchè usi una Libreria Standard C++ vector come sua implementazione sottostante. Accertarsi di non cambiare l’interfaccia, cosicchè TStack2Test.cpp lavori senza cambiamenti.
  13. Ripetere l’ Esercizio 12 usando una Libreria Standard C++ stack invece di un vector (si può aver bisogno di dare uno sguardo alle informazioni sullo stack, o condurre una ricerca sull’header file di <stack> ).
  14. Modificare TPStash2.h cosicchè usi una Libreria Standard C++ vector come sua implementazione sottostante. Accertarsi di non cambiare l’interfaccia, cosicchè TPStash2Test.cpp lavori senza cambiamenti.
  15. In IterIntStack.cpp, modificare IntStackIter per dargli uncostruttore della “sentinella della fine” e aggiungere operator== e operator!=. In main( ), usare un iteratore per muoversi attraverso gli elementi del contenitore finchè si raggiunge la sentinella della fine.
  16. Usando TStack2.h, TPStash2.h, e Shape.h, istanziare i contenitori Stack e PStash per Shape*, riempire ognuno con un assortimento di puntatori a Shape castati all’insù, quindi usare gli iteratori per muoversi attraverso ciascun contenitore e chiamare draw( ) per ciascun oggetto.
  17. Templatizzare la classe Int in TPStash2Test.cpp cosicchè conservi qualsiasi tipo di oggetto (sentirsi liberi di cambiare il nome della classe in qualcos’altro di più appropriato).
  18. Templatizzare la classe IntArray in IostreamOperatorOverloading.cpp del Capitolo 12, templatizzando sia il tipo di oggetto che è contenuto sia le dimensioni dell’array interno.
  19. Convertire ObjContainer in NestedSmartPointer.cpp del Capi in un template. Testarlo con due classi differenti.
  20. Modificare C15:OStack.h e C15:OStackTest.cpp templatizzando class Stack cosicchè automaticamente erediti sia dalla classe contenuta sia Object. Lo Stack generato dovrebbe accettare e produrre solo puntatori del tipo contenuto.
  21. Si ripeta l’Esercizio 20 usando vector al posto di Stack.
  22. Si erediti una classe StringVector da vector<void*> e si ridefiniscano le funzioni membro push_back( ) e operator[] affinchè accettino e producano solo string* (e compiano il casting corretto). Ora si crei un template che automaticamente creerà una classe contenitore per fare la stessa cosa per puntatori a qualsiasi tipo. Questa tecnica è spesso usata per ridurre l’eccesso di codice derivato da troppe istanziazioni di template.
  23. In TPStash2.h, aggiungere e testare un operator- a PStash::iterator, seguendo la logica di operator+.
  24. In Drawing.cpp, aggiungere e testare una funzione template per chiamare le funzioni membro di erase( ).
  25. (Avanzato) Modificare la classe Stack in TStack2.h per consentire una completa granulosità dell’appartenenza: aggiungere un flag a ciascun link che indichi se questo link possieda l’oggetto cui punta, e supportare questa informazione nella funzione push( ) e nel distruttore. Aggiungere funzioni membro per leggere e cambiare lo stato di proprietà per ciascun link.
  26. (Avanzato) Modificare PointerToMemberOperator.cpp del Capitolo 12 cosichhè la FunctionObject e operator->* siano templatizzate per lavorare con qualsiasi tipo di ritorno (per operator->*, si dovranno usare i member template, descritti nel Volume 2). Aggiungere e testare un supporto per zero, uno e due argomenti nelle funzioni membro di Dog.


[59] Con l’eccezione, in Java, dei tipi di dato primitivi. Questi furono resi non-Objects in nome dell’efficienza.

[60] La libreria OOPS, di Keith Gorlen mentre era al NIH.

[61] The C++ Programming Language di Bjarne Stroustrup (I edizione, Addison-Wesley, 1986).

[62] L'ispirazione dei template sembra essere generico ADA .

[63] Tutti i metodi sia in Smalltalk che in Python sono debolmente tipizzati, e così questi linguaggi non hanno bisogno di un meccanismo di template. In effetti, si ottengono i template senza template.

[ Capitolo Precedente ] [ Indice Generale ] [ Indice Analitico ] [ Capitolo Successivo ]
Ultima modifica: 11/03/2003