Template CPP

Template

Programmazione generica

Nello sviluppo di questo corso, siamo "passati" attraverso vari tipi di "programmazione", che in realtà perseguono sempre lo stesso obiettivo (suddivisione di un progetto in porzioni indipendenti, allo scopo di minimizzare il rapporto costi/benefici nella produzione e manutenzione del software), ma che via via tendono a realizzare tale obiettivo a livelli sempre più profondi:

programmazione procedurale: è la programmazione caratteristica del linguaggio C (e di tutti gli altri linguaggi precedenti al C++). L'interesse principale è focalizzato sull'elaborazione e sulla scelta degli algoritmi più idonei a massimizzarne l'efficienza. Ogni algoritmo lavora in una funzione, a cui si passano argomenti e da cui si ottiene un valore di ritorno. Le funzioni sono implementate con gli strumenti tipici del linguaggio (tipi, variabili, puntatori, costrutti vari ecc...). Dal punto di vista dell'utente ogni funzione è una "scatola nera" e i suoi argomenti e valore di ritorno sono gli unici canali di comunicazione.

programmazione modulare: l'attenzione si sposta dal progetto delle procedure all'organizzazione dei dati. Ogni gruppo formato da dati logicamente correlati e dalle procedure che li utilizzano costituisce un modulo, in cui i dati sono "occultati" (data hiding). I moduli sono il più possibile indipendenti. Le interfacce costituiscono l'unico canale di comunicazione fra i moduli e i loro utenti. I namespace sono gli strumenti che il C++ mette a disposizione per realizzare questo tipo di programmazione.

programmazione a oggetti: l'attenzione si sposta ulteriormente dai moduli ai singoli oggetti. Attraverso le classi, esiste la possibilità di definire nuovi tipi. I membri di ogni classe possono essere sia dati che funzioni e solo alcuni di essi possono essere accessibili dall'esterno. Il data hiding si trasferisce dentro gli oggetti, che diventano entità attive e autosufficienti e comunicano con gli utenti solo attraverso i propri membri pubblici. Ogni nuovo tipo può essere corredato di un insieme di operazioni (overload degli operatori) e ulteriormente espanso e specializzato in modo incrementale e indipendente dal codice già scritto, grazie all'eredità e al polimorfismo.

Un ulteriore "salto di qualità" è rappresentato dalla cosidetta "programmazione generica", la quale consente di applicare lo stesso codice a tipi diversi, cioè di definire template (modelli) di classi e funzioni parametrizzando i tipi utilizzati: nelle classi, si possono parametrizzare i tipi dei dati-membro; nelle funzioni (e nelle funzioni-membro delle classi) si possono parametrizzare i tipi degli argomenti e del valore di ritorno. In questo modo si raggiunge il massimo di indipendenza degli algoritmi dai dati a cui si applicano: per esempio, un algoritmo di ordinamento può essere scritto una sola volta, qualunque sia il tipo dei dati da ordinare.
I template sono risolti staticamente (cioè a livello di compilazione) e pertanto non comportano alcun costo aggiuntivo in fase di esecuzione; sono invece di enorme utilità per il programmatore, che può scrivere del codice "generico", senza doversi preoccupare di differenziarlo in ragione della varietà dei tipi a cui tale codice va applicato. Ciò è particolarmente vantaggioso quando si possono creare classi strutturate identicamente, ma differenti solo per i tipi dei membri e/o per i tipi degli argomenti delle funzioni-membro.
La stessa Libreria Standard del C++ mette a disposizione strutture precostituite di classi template, dette classi contenitore (liste concatenate, mappe, vettori ecc...) che possono essere utilizzate specificando, nella creazione degli oggetti, i valori reali da sostituire ai tipi parametrizzati.

Definizione di una classe template

Una classe (o struttura) template è identificata dalla presenza, davanti alla definizione della classe, dell'espressione:
template<class T>
dove T (che è un nome e segue le normali regola di specifica degli identificatori) rappresenta il parametro di un tipo generico che verrà utilizzato nella dichiarazione di uno o più membri della classe. In questo contesto la parola-chiave class non ha il solito significato: indica che T è il nome di un tipo (anche nativo), non necessariamente di una classe. L'ambito di visibilità di T coincide con quello della classe. Se però una funzione-membro non è definita inline ma esternamente, bisogna, al solito, qualificare il suo nome: in questo caso la qualificazione completa consiste nel ripetere il prefisso template<class T> ancora prima del tipo di ritorno (che in particolare può anche dipendere da T) e inserire <T> dopo il nome della classe. Esempio:

Definizione della classe template A

template<class T> class A {

   T mem ;    dato-membro di tipo parametrizzato

public:

   A(const T& m) : mem(m) { }    costruttore inline con un argomento di
tipo parametrizzato

   T get( );    dichiarazione di funzione-membro con
valore di ritorno di tipo parametrizzato

........ };

Definizione esterna della funzione-membro get( )

template<class par> par A<par>::get( )    notare che il nome del parametro può

{    anche essere diverso da quello usato nella

   return mem ;    definizione della classe

}

NOTA
Nella definizione della funzione get la ripetizione del parametro par nelle espressioni template<class par> e A<par> potrebbe sembrare ridondante. In realtà le due espressioni hanno significato è diverso:

template<class par> introduce, nel corrente ambito di visibilità (in questo caso della funzione get), il nome par come parametro di template;

A<par> indica che la classe A è un template con parametro par.

In generale, ogni volta che una classe template è riferita al di fuori del proprio ambito (per esempio come argomento di una funzione), è obbligatorio specificarla seguita dal proprio parametro fra parentesi angolari.

I parametri di un template possono anche essere più di uno, nel qual caso, nella definizione della classe e nelle definizioni esterne delle sue funzioni-membro, tutti i parametri vanno specificati con il prefisso class e separati da virgole. Esempio:
template<class par1,class par2,class par3>
I template vanno sempre definiti in un namespace, o nel namespace globale o anche nell'ambito di un'altra classe (template o no). Non possono essere definiti nell'ambito di un blocco. Non è inoltre ammesso definire nello stesso ambito due classi con lo stesso nome, anche se hanno diverso numero di parametri oppure se una classe è template e l'altra no (in altre parole l'overload è ammesso fra le funzioni, non fra le classi).

Definizione della classe template A
template<class T> class A {
T mem ;	dato-membro di tipo *parametrizzato*
public:
A(const T& m) : mem(m) { }	costruttore inline con un argomento di tipo *parametrizzato*
T get( );	dichiarazione di funzione-membro con valore di ritorno di tipo *parametrizzato*
........ };

Definizione esterna della funzione-membro get( )
template<class par> par A<par>::get( )	notare che il nome del *parametro* può
{	anche essere diverso da quello usato nella
return mem ;	definizione della classe
}

Istanza di un template

Un template è un semplice modello (come dice la parola stessa in inglese) e non può essere usato direttamente. Bisogna prima sostituirne i parametri con tipi già precedentemente definiti (che vengono detti argomenti). Solo dopo che è stata fatta questa operazione si crea una nuova classe (cioè un nuovo tipo) che può essere a sua volta istanziata per la creazione di oggetti.
Il processo di generazione di una classe "reale" partendo da una classe template e da un argomento è detto: istanziazione di un template (notare l'analogia: come un oggetto si crea istanziando un tipo, così un tipo si crea istanziando un template). Se una stessa classe template viene istanziata più volte con argomenti diversi, si dice che vengono create diverse specializzazioni dello stesso template. La sintassi per l'istanziazione di un template è la seguente (riprendiamo l'esempio della classe template A):
A<tipo>
dove tipo è il nome di un tipo (nativo o definito dall'utente), da sostituire al parametro della classe template A nelle dichiarazioni (e definizioni) di tutti i membri di A in cui tale parametro compare. Quindi la classe "reale" non è A, ma A<tipo>, cioè la specializzazione di A con argomento tipo. Ciò rende possibili istruzioni, come per esempio la seguente:
A<int> ai(5);
che costruisce (mediante chiamata del costruttore con un argomento, di valore 5) un oggetto ai della classe template A, specializzata con argomento int.

[p73]

Parametri di default

Come gli argomenti delle funzioni, anche i parametri dei template possono essere impostati di default. Riprendendo l'esempio precedente, modifichiamo il prefisso della definizione della classe A in:
template<class T = double>
ciò comporta che, se nelle istanziazioni di A si omette l'argomento, questo è sottinteso double; per esempio:
A<> ad(3.7); equivale a A<double> ad(3.7);
(notare che le parentesi angolari vanno specificate comunque).
Se una classe template ha più parametri, quelli di default possono anche essere espressi in funzione di altri parametri. Supponiamo per esempio di definire una classe template B nel seguente modo:
template<class T, class U = A<T> > class B { ........ };
in questa classe i parametri sono due: T e U; ma, mentre l'argomento corrispondente a T deve essere sempre specificato, quello corrispondente a U può essere omesso, nel qual caso viene sostituito con il tipo generato dalla classe A specializzata con l'argomento corrispondente a T. Così:
B<double,int> crea la specializzazione di B con argomenti double e int, mentre:
B<int> crea la specializzazione di B con argomenti int e A<int>

[p74]

Funzioni template

Analogamente alle funzioni-membro di una classe, anche le funzioni non appartenenti a una classe possono essere dichiarate (e definite) template. Esempio di dichiarazione di una funzione template:
template<class T> void sort(int n, T_* p);
Come si può notare, uno degli argomenti della funzione sort è di tipo parametrizzato. La funzione ha lo scopo di ordinare un array p di n elementi di tipo T, e dovrà essere istanziata con argomenti di tipi "reali" da sostituire al parametro T (vedremo più avanti come si fa). Se un argomento è di tipo definito dall'utente, la classe che corrisponde a T dovrà anche contenere tutti gli overload degli operatori necessari per eseguire i confronti e gli scambi fra gli elementi dell'array.
Seguitando nell'esempio, allo scopo di evidenziare tutta la "potenza" dei template confrontiamo ora la nostra funzione con un'analoga funzione di ordinamento, tratta dalla Run Time Library (che è la libreria standard del C). Il linguaggio C, che ovviamente non conosce i template nè l'overload degli operatori, può rendere applicabile lo stesso algoritmo di ordinamento a diversi tipi facendo ricorso agli "strumenti" che ha, e cioè ai puntatori a void (per generalizzare il tipo dell'array) e ai puntatori a funzione (per dar modo all'utente di fornire la funzione di confronto fra gli elementi dell'array). Inoltre, nel codice della funzione, dovrà eseguire il casting da puntatori a void (che non sono direttamente utilizzabili) a puntatori a byte (cioè a char) e quindi, non potendo usare direttamente l'aritmetica dei puntatori, dovrà anche conoscere il size del tipo utilizzato (come ulteriore argomento della funzione, che si aggiunge al puntatore a funzione da usarsi per i confronti). In definitiva, la funzione "generica" sort del C dovrebbe essere dichiarata nel seguente modo:
typedef int (_*CMP)(const void_*, const void_*);
void sort(int n, void_* p, int size, CMP cmp);
l'utente dovrà provvedere a fornire la funzione di confronto "vera" da sostituire a cmp, e dovrà pure preoccuparsi di eseguire, in detta funzione, tutti i necessari casting da puntatore a void a puntatore al tipo utilizzato nella chiamata.
Risulta evidente che la soluzione con i template è di gran lunga preferibile: è molto più semplice e concisa (sia dal punto di vista del programmatore che da quello dell'utente) ed è anche più veloce in esecuzione, in quanto non usa puntatori a funzione, ma solo chiamate dirette (di overload di operatori che, oltretutto, si possono spesso realizzare inline).

Differenze fra funzioni e classi template

Le funzioni template differiscono dalle classi template principalmente sotto tre aspetti:

Le funzioni template non ammettono parametri di default .

Come le classi, anche le funzioni template sono utilizzabili soltanto dopo che sono state istanziate; ma, mentre nelle classi le istanze devono essere sempre esplicite (cioè gli argomenti non di default devono essere sempre specificati), nelle funzioni gli argomenti possono essere spesso dedotti implicitamente dal contesto della chiamata. Riprendendo l'esempio della funzione sort, la sequenza:

double a[10] = { .........};

sort(10, a);

crea automaticamente un'istanza della funzione template sort, con argomento double dedotto dalla stessa chiamata della funzione.

Quando invece un argomento non può essere dedotto dal contesto, deve essere specificato esplicitamente, nello stesso modo in cui lo si fa con le classi. Esempio:

template<class T> T_* create( ) { .........}

int_* p = create<int>( ) ;

In generale un argomento può essere dedotto quando corrisponde al tipo di un argomento della funzione e non può esserlo quando corrisponde al tipo del valore di ritorno.

Se una funzione template ha più parametri, dei quali corrispondenti argomenti alcuni possono essere dedotti e altri no, gli argomenti deducibili possono essere omessi solo se sono gli ultimi nella lista (esattamente come avviene per gli argomenti di default di una funzione). Esempio (supponiamo che la variabile d sia stata definita double):

FUNZIONE CHIAMATA NOTE

template<class T,class U>
T fun1(U); int m = fun1<int>(d); Il secondo argomento è dedotto di tipo double

template<class T,class U>
U fun2(T); int m =
fun2<double,int>(d); Il primo argomento non si può omettere,
anche se è deducibile

Analogamente alle funzioni tradizionali, e a differenza dalle classi, anche le funzioni template ammettono l'overload (compresi overload di tipo "misto", cioè fra una funzione tradizionale e una funzione template). Nel momento della "scelta" (cioè quando una funzione in overload viene chiamata), il compilatore applica le normali regole di risoluzione degli overload, alle quali si aggiungono le regole per la scelta della specializzazione che meglio si adatta agli argomenti di chiamata della funzione. Va precisato, tuttavia, che tali regole dipendono dal tipo di compilatore usato, in quanto i template rappresentano un aspetto dello standard C++ ancora in "evoluzione". Nel seguito, ci riferiremo ai criteri applicati dal compilatore gcc 3.3 (che è il più "moderno" che conosciamo):

a)
fra due funzioni template con lo stesso nome viene scelta quella "più specializzata" (cioè quella che corrisponde più esattamente agli argomenti della chiamata); per esempio, date due funzioni:
template<class T> void fun(T); e template<class T> void fun(A<T>);
(dove A è la classe del nostro esempio iniziale), la chiamata:
fun(5); selezionerà la prima funzione, mentre la chiamata:
fun(A<int>(5)); selezionerà la seconda funzione;

b)
se un argomento è dedotto, non sono ammesse conversioni implicite di tipo, salvo quelle "banali", cioè le conversioni fra variabile e costante e quelle da classe derivata a classe base; in altre parole, se uno stesso argomento è ripetuto più volte, tutti i tipi dei corrispondenti argomenti nella chiamata devono essere identici (a parte i casi di convertibilità sopra menzionati);

c)
come per l'overload fra funzioni tradizionali, le funzioni in cui la corrispondenza fra i tipi è esatta sono preferite a quelle in cui la corrispondenza si ottiene solo dopo una conversione implicita;

d)
a parità di tutte le altre condizioni, le funzioni tradizionali sono preferite alle funzioni template;

e)
il compilatore segnala errore se, malgrado tutti gli "sforzi", non trova nessuna corrispondenza soddisfacente; come pure segnala errore in caso di ambiguità, cioè se trova due diverse soluzioni allo stesso livello di preferenza.

Per maggior chiarimento, vediamo ora alcuni esempi di chiamate di funzioni e di scelte conseguenti operate dal compilatore, date queste due funzioni in overload, una tradizionale e l'altra template:
void fun(double,double); e template<class T> void fun(T,T);

CHIAMATA RISOLUZIONE NOTE

fun(1,2); fun<int>(1,2);
argomento dedotto, corrispondenza esatta

fun(1.1,2.3); fun(1.1,2.3);
funzione tradizionale, preferita

fun('A',2); fun(double('A'),double(2));
funzione tradizionale, unica possibile

fun<char>(69,71.2); fun<char>(char(69),char(71.2));
argomento esplicito, conversioni ammesse

definite le seguenti variabili: int a = ...; const int c = ...; int_* p = ...;

fun(a,c); fun<int>(a,c); argomento dedotto, conversione "banale"

fun(a,p);
ERRORE
conversione non ammessa da int_* a double

FUNZIONE	CHIAMATA	NOTE
template<class T,class U> T fun1(U);	int m = fun1<int>(d);	Il secondo argomento è dedotto di tipo double
template<class T,class U> U fun2(T);	int m = fun2<double,int>(d);	Il primo argomento non si può omettere, anche se è deducibile

CHIAMATA	RISOLUZIONE	NOTE
fun(1,2);	fun<int>(1,2);	argomento dedotto, corrispondenza esatta
fun(1.1,2.3);	fun(1.1,2.3);	funzione tradizionale, preferita
fun('A',2);	fun(double('A'),double(2));	funzione tradizionale, unica possibile
fun<char>(69,71.2);	fun<char>(char(69),char(71.2));	argomento esplicito, conversioni ammesse
definite le seguenti variabili: int a = ...; const int c = ...; int_* p = ...;
fun(a,c);	fun<int>(a,c);	argomento dedotto, conversione "banale"
fun(a,p);	ERRORE	conversione non ammessa da int_* a double

Template e modularità

In relazione alla ODR (One-Definition-Rule), le funzioni template (e le funzioni-membro delle classi template) appartengono alla stessa categoria delle funzioni inline e delle classi (vedere capitolo: Tipi definiti dall'utente, sezione: Strutture), cioè in pratica la definizione di una funzione template può essere ripetuta identica in più translation units del programma.
Nè potrebbe essere diversamente. Infatti, come si è detto, i template sono istanziati staticamente, cioè a livello di compilazione, e quindi il codice che utilizza un template deve essere nella stessa translation unit del codice che lo definisce. In particolare, se un stesso template è usato in più translation units, la sua definizione, non solo può, ma deve essere inclusa in tutte (in altre parole, non sono ammesse librerie di template già direttamente in codice binario, ma solo header-files che includano anche il codice di implementazione in forma sorgente).
Queste regole, però, contraddicono il principio fondamentale della programmazione modulare, che stabilisce la separazione e l'indipendenza del codice dell'utente da quello delle procedure utilizzate: l'interfaccia comune non dovrebbe contenere le definizioni, ma solo le dichiarazioni delle funzioni (e delle funzioni-membro delle classi) coinvolte, per modo che qualunque modifica venga apportata al codice di implementazione di dette funzioni, quello dell'utente non ne venga influenzato. Con le funzioni template questo non è più possibile.
Per ovviare a tale grave carenza, e far sì che la programmazione generica costituisca realmente "un passo avanti" nella direzione dell'indipendenza fra le varie parti di un programma, mantenendo nel contempo tutte le "posizioni" acquisite dagli altri livelli di programmazione, è stata recentemente introdotta nello standard una nuova parola-chiave: "export", che, usata come prefisso nella definizione di una funzione template, indica che la stessa definizione è accessibile anche da altre translation units. Spetterà poi al linker, e non al compilatore, generare le eventuali istanze richieste dall'utente. In questo modo "tutto si rimette a posto", e in particolare:

le funzioni template possono essere compilate separatamente;

nell'interfaccia comune si possono includere solo le dichiarazioni, come per le funzioni tradizionali.

Tutto ciò sarebbe molto "bello", se non fosse che ... putroppo (secondo quello che ci risulta) nessun compilatore a tutt'oggi implementa la parola-chiave export! E quindi, per il momento, bisogna ancora includere le definizioni delle funzioni template nell'interfaccia comune.

[p75][p75] [p75]

[p76][p76] [p76]

	template<class T> T_* create( ) { .........}
	int_* p = create<int>( ) ;

a)	fra due funzioni template con lo stesso nome viene scelta quella "più specializzata" (cioè quella che corrisponde più esattamente agli argomenti della chiamata); per esempio, date due funzioni: template<class T> void fun(T); e template<class T> void fun(A<T>); (dove A è la classe del nostro esempio iniziale), la chiamata: fun(5); selezionerà la prima funzione, mentre la chiamata: fun(A<int>(5)); selezionerà la seconda funzione;
b)	se un argomento è dedotto, non sono ammesse conversioni implicite di tipo, salvo quelle "banali", cioè le conversioni fra variabile e costante e quelle da classe derivata a classe base; in altre parole, se uno stesso argomento è ripetuto più volte, tutti i tipi dei corrispondenti argomenti nella chiamata devono essere identici (a parte i casi di convertibilità sopra menzionati);
c)	come per l'overload fra funzioni tradizionali, le funzioni in cui la corrispondenza fra i tipi è esatta sono preferite a quelle in cui la corrispondenza si ottiene solo dopo una conversione implicita;
d)	a parità di tutte le altre condizioni, le funzioni tradizionali sono preferite alle funzioni template;
e)	il compilatore segnala errore se, malgrado tutti gli "sforzi", non trova nessuna corrispondenza soddisfacente; come pure segnala errore in caso di ambiguità, cioè se trova due diverse soluzioni allo stesso livello di preferenza.