C++ - template e programmazione generica

Come scrivere codice che funziona per qualsiasi tipo: la classe vector costruita finora contiene solo double, ma la stessa logica serve per int, string, Month, vector<vector<Record>>. I template sono lo strumento (programmazione generica) e sono alla base della STL (STL - sequenze, iteratori e container (vector, list, string)La STL (Standard Template Library) fornisce contenitori (vector, list, map, ...) e algoritmi generici (sort, find, accumulate, ...) tenuti insieme da una interfaccia unificata: la sequenza, un intervallo [begin, end) di elementi gestito tramite iteratori (oggetti che identificano un elemento: * dereferenzia, ++ avanza, == e != confrontano; end è il primo elemento dopo l'ultimo, quindi una sequenza vuota ha begin == end). Gli algoritmi conoscono solo gli iteratori e i contenitori espongono solo iteratori, così i due mondi sono disaccoppiati e cambiare contenitore non cambia l'algoritmo. Un iteratore di lista è una classe annidata con un puntatore al nodo; auto deduce il tipo dell'iteratore. vector (contiguo, [] e at(), insert/erase costosi e che invalidano gli iteratori), string (un vector di char con + e +=), list (nodi concatenati, insert/erase senza spostare gli altri elementi, niente []) e char[] (array C: dimensione fissa, niente iteratori, == confronta i puntatori) a confronto.STL - sequenze, iteratori e container (vector, list, string) →, STL - algoritmi, predicati e lambdaLa STL ha circa 80 algoritmi generici (header e ) che lavorano su sequenze [first, last) di qualunque contenitore tramite iteratori: find/find_if, count/count_if, sort, copy/copy_if/unique_copy, merge, equal_range, equal, accumulate, inner_product. find cerca un valore e restituisce l'iteratore alla prima occorrenza o end(); find_if verifica un predicato (funzione che restituisce bool) passato come puntatore a funzione, function object (classe con operator()) o lambda expression. Una variabile globale per passare la soglia al predicato è da evitare; il function object la memorizza in un dato membro. Una lambda cattura -> tipo { corpo } definisce la funzione sul posto e può catturare le variabili locali per valore ([=], [x]) o per riferimento ([&], [&x]). sort(b, e) ordina con < e sort(b, e, cmp) con un criterio, solo su iteratori random access; copy richiede spazio a destinazione.STL - algoritmi, predicati e lambda →). Il prerequisito è la classe con memoria dinamica di C++ - allocazione dinamica della memoria con new e deletela memoria dinamica si prende dal free store (heap) con new, che restituisce un puntatore all'oggetto o al primo elemento dell'array (new T, new T[n], con inizializzatori {}), e si restituisce con delete (per new) e delete[] (per new[]); il puntatore non sa quanti elementi ci sono, la memoria non ha nome e non ha controllo dei limiti; in C++ non c'è garbage collector (scelta per efficienza e controllo), quindi un'area che perde ogni riferimento diventa garbage e produce un memory leak, e gli errori tipici sono la doppia cancellazione e il dangling pointer (si mette il puntatore a nullptr dopo delete); il distruttore ~T() è chiamato dal compilatore quando l'oggetto esce dallo scope o con delete e libera le risorse, per cui una classe come vector acquisisce la memoria nel costruttore e la rilascia nel distruttore; new alloca e chiama il costruttore, delete chiama il distruttore e libera; operator[] con due versioni (T& e const) dà accesso in lettura e scrittura al buffer; si alloca dinamicamente solo se serve davvero (memoria grande, dimensione nota a run-time, durata controllata).C++ - allocazione dinamica della memoria con new e delete → e C++ - costruttori, inizializzazione, copia e spostamentouna buona interfaccia è completa e minimale, ha i costruttori giusti, supporta o proibisce la copia, usa tipi adeguati, dichiara const ciò che non modifica e libera le risorse nel distruttore; il costruttore di default (senza argomenti) esiste quando c'è un valore iniziale sensato, si ottiene con valori di default nei membri (in-class initializer) o argomenti di default, e explicit vieta la conversione implicita da un argomento; initializer_list permette la lista {a, b, c} e con le graffe ha la precedenza sul costruttore a un intero (vector{3} è un elemento, vector(3) sono tre); la copia di default è membro a membro (shallow copy) e con un puntatore a un buffer duplica il puntatore invece del contenuto (due oggetti che condividono i dati e una doppia delete), quindi servono il costruttore di copia e l'assegnamento di copia che fanno la deep copy (l'assegnamento prima alloca e copia, poi libera i vecchi dati, e deve tollerare l'auto-assegnamento); this è il puntatore all'oggetto corrente, parametro implicito delle funzioni membro; il costruttore e l'assegnamento di spostamento (T&&, rvalue reference) rubano il buffer della sorgente lasciandola vuota ma valida, il compilatore li sceglie da solo (con la copy elision a volte non servono nemmeno); i cinque (distruttore, copia, spostamento) vanno definiti insieme.C++ - costruttori, inizializzazione, copia e spostamento →; l'esercizio che porta a termine il lavoro è Esercizio - MyVector 2.0 con template (laboratorio 5). Il confronto con il polimorfismo a run-time (che risolve lo stesso problema in un altro modo) è in C++ - polimorfismoPolimorfismo = abilità di associare comportamenti diversi a un'unica notazione generica. In C++ ci sono due forme principali: dinamico (ereditarietà più funzioni virtuali: vincolato dall'interfaccia della classe base, binding a run-time, permette collezioni eterogenee) e statico (template: svincolato, basta che i tipi abbiano la stessa sintassi, binding a tempo di compilazione, nessun costo a run-time ma una funzione per ogni tipo); il polimorfismo statico è lo strumento della programmazione generica. Anche l'overloading di funzioni e di operatori può essere visto come polimorfismo. Nella gerarchia si naviga con l'upcasting (implicito, sempre lecito) e il downcasting con dynamic_cast, l'unico cast con verifica a run-time: su un puntatore dà nullptr se non lecito, su un riferimento lancia bad_cast.C++ - polimorfismo →; i generics di Java sono in Java - generics, reflection e passaggio dei parametriIn Java ogni dato ha una propria identità a tempo di esecuzione (il cast è controllato e può lanciare ClassCastException, a differenza del C) e i parametri si passano sempre per valore (di un riferimento, per gli oggetti: si può modificare l'oggetto ma non riassegnare il riferimento del chiamante); i generics (CodaG) spostano i controlli di tipo a tempo di compilazione ma sono cancellati dalla type erasure, quindi non sono i template del C++; la riflessione (Class, Constructor, Method, Field) permette di caricare classi per nome, creare oggetti, chiamare metodi e leggere o scrivere campi a tempo di esecuzione, con eccezioni specifiche (ClassNotFoundException, InvocationTargetException, IllegalAccessException) e il costo di aggirare il controllo statico.Java - generics, reflection e passaggio dei parametri →.

Il concetto di template

Definizione. Un template è un meccanismo che permette al programmatore di usare un tipo come parametro per una classe o una funzione. Il compilatore genera il codice necessario per ogni tipo per cui il template è specializzato.

vector<double>   vector<int>   vector<Month>   vector<char>
vector<vector<Record>>   vector<Window*>

Un class template si chiama anche type generator, parametrized type o parametrized class. Il processo di generazione di una classe per un tipo specifico è la specializzazione (specialization) o template instantiation: vector<char> è una specializzazione di vector. Questo processo avviene a tempo di compilazione.

La notazione

template <typename T> e template <class T> sono perfettamente equivalenti. typename è più chiaro e rende evidente che si possono usare anche tipi built-in; class è più corto e in questo contesto significa semplicemente "tipo".

Class template

Si sostituisce un tipo generico T a double e si aggiunge il prefisso che introduce il template:

template <typename T>
class vector {
    int sz;
    T* elem;
public:
    vector() : sz{0}, elem{nullptr} {}
    explicit vector(int s) : sz{s}, elem{new T[s]} { for (int i = 0; i < sz; ++i) elem[i] = 0; }
    // ...
};

Le funzioni membro seguono la stessa specializzazione. Se esiste push_back, in

void vct(vector<string>& v)
{
    int n = v.size();
    v.push_back("Norah");
}

si usa vector<string>::push_back, che il compilatore genera dalla definizione

template <typename T>
void vector<T>::push_back(const T& d) { /* ... */ }

producendo void vector<string>::push_back(const string& d) { /* ... */ }. Quando una funzione membro è definita fuori dalla classe, ognuna ha il prefisso template <typename T> e il nome Classe<T>::. (Il lab 5 impone proprio questo: tutte le funzioni fuori dalla classe, membri public prima dei private.)

Nota sul codice elem[i] = 0;: va bene per double ma non per ogni T (una string non si inizializza a 0). Si scrive T{}: il valore di default di T (0 per i numeri, stringa vuota per string). Un template pone requisiti nascosti sul tipo T: qui deve avere un costruttore di default e l'assegnamento.

Un esempio completo su più file

Il template Vector<T> con dichiarazione in vector.h, definizioni in vector.hpp (incluso in coda al .h) e un main che lo usa con double, string e Vector<int>:

#ifndef VECTOR_H
#define VECTOR_H

// Interfaccia: dichiarazioni della classe
template <typename T>
class Vector {
public:
    Vector() : sz{0}, elem{nullptr} {}
    explicit Vector(int s);
    Vector(const Vector& a);
    Vector& operator=(const Vector& a);
    ~Vector();

    int size() const { return sz; }
    T& operator[](int n);
    const T& operator[](int n) const;
    void push_back(const T& d);

private:
    int sz;
    T* elem;
};

#include "vector.hpp"      // le definizioni vanno in coda all'header, non in un .cpp da compilare a parte

#endif // VECTOR_H

#ifndef VECTOR_HPP
#define VECTOR_HPP

// Implementazione: definizioni delle funzioni membro. Ognuna comincia con template <typename T>
template <typename T>
Vector<T>::Vector(int s) : sz{s}, elem{new T[s]}
{
    for (int i = 0; i < sz; ++i) elem[i] = T{};       // T{}: 0 per i numeri, stringa vuota per string
}

template <typename T>
Vector<T>::Vector(const Vector& a) : sz{a.sz}, elem{new T[a.sz]}
{
    for (int i = 0; i < sz; ++i) elem[i] = a.elem[i];
}

template <typename T>
Vector<T>& Vector<T>::operator=(const Vector& a)
{
    T* p = new T[a.sz];
    for (int i = 0; i < a.sz; ++i) p[i] = a.elem[i];
    delete[] elem;
    elem = p;
    sz = a.sz;
    return *this;
}

template <typename T>
Vector<T>::~Vector() { delete[] elem; }

template <typename T>
T& Vector<T>::operator[](int n) { return elem[n]; }

template <typename T>
const T& Vector<T>::operator[](int n) const { return elem[n]; }

template <typename T>
void Vector<T>::push_back(const T& d)
{
    T* p = new T[sz + 1];                              // semplice: rialloca a ogni inserimento
    for (int i = 0; i < sz; ++i) p[i] = elem[i];
    p[sz] = d;
    delete[] elem;
    elem = p;
    ++sz;
}

#endif // VECTOR_HPP

#include <iostream>
#include <string>
#include "vector.h"
using namespace std;

void vct(Vector<string>& v)
{
    int n = v.size();
    v.push_back("Norah");                  // Vector<string>::push_back(const string&)
    cout << "prima " << n << ", dopo " << v.size() << '\n';
}

int main()
{
    Vector<double> vd(3);                  // il compilatore genera la classe Vector<double>
    vd[1] = 2.5;
    vd.push_back(7.0);
    cout << vd.size() << ": " << vd[0] << ' ' << vd[1] << ' ' << vd[3] << '\n';

    Vector<string> vs;                     // e Vector<string>
    vct(vs);
    vs.push_back("Ada");
    Vector<string> vs2 = vs;               // deep copy
    vs2[0] = "Grace";
    cout << vs[0] << ' ' << vs2[0] << ' ' << vs[1] << '\n';

    Vector<Vector<int>> m;                 // un Vector di Vector
    Vector<int> riga(2);
    riga[0] = 4;
    m.push_back(riga);
    cout << m.size() << ' ' << m[0][0] << '\n';
    return 0;
}

Compilato con g++ main.cpp (non c'è alcun .cpp per Vector), stampa:

4: 0 2.5 7
prima 0, dopo 1
Norah Grace Ada
1 4

Il compilatore ha generato tre classi, Vector<double>, Vector<string> e Vector<int>, più Vector<Vector<int>>: ogni push_back copia in profondità perché Vector<T> ha il suo costruttore di copia.

Function template

Anche una funzione si può parametrizzare: function template (o parametrized function, o algorithm: il focus è sull'algoritmo più che sui tipi che usa). Esempio: il massimo di due valori.

template <typename T>
T myMax(T x, T y)
{
    return (x > y) ? x : y;
}

Perché serve un template? Perché la stessa funzione serve per int, double, string; scriverla tre volte è ripetitivo. Che cosa si assume su T? Che supporti l'operatore > e la copia.

Chiamata ed espressione del tipo. Si può indicare il tipo (myMax<int>(i, j)) oppure lasciare che il compilatore lo deduca dagli argomenti: myMax(i, j) è equivalente. È la deduzione degli argomenti template, fatta a tempo di compilazione. Se i parametri si riferiscono a T con tipi diversi, la deduzione fallisce.

#include <cstring>
#include <iostream>
#include <string>
using namespace std;

template <typename T>
T myMax(T x, T y)                    // T e' un tipo qualunque purché supporti l'operatore >
{
    return (x > y) ? x : y;
}

// specializzazione ESPLICITA per const char*: il confronto generico (>) confronterebbe gli indirizzi
template <>
const char* myMax<const char*>(const char* x, const char* y)
{
    return (strcmp(x, y) > 0) ? x : y;
}

struct Punto { int x, y; };          // NON ha operator>

int main()
{
    int i = 3, j = 5;
    cout << myMax<int>(i, j) << '\n';              // T indicato esplicitamente
    cout << myMax(i, j) << '\n';                   // T = int, DEDOTTO dagli argomenti
    cout << myMax(2.5, -1.0) << '\n';              // T = double
    cout << myMax(string("pesca"), string("mela")) << '\n';   // T = string
    cout << myMax("pesca", "mela") << '\n';        // T = const char*: usa la specializzazione
    // myMax(1, 2.5);                              // errore: T sarebbe int e double insieme
    // myMax(Punto{1, 2}, Punto{3, 4});            // errore: Punto non ha operator>
    return 0;
}

5
5
2.5
pesca
pesca

I due errori commentati nel programma, con il compilatore:

error: no matching function for call to 'myMax'      (myMax(1, 2.5))
note: candidate template ignored: deduced conflicting types for parameter 'T' ('int' vs. 'double')

error: invalid operands to binary expression ('Punto' and 'Punto')   (myMax con Punto)
note: in instantiation of function template specialization 'myMax<Punto>' requested here

Il secondo è tipico: l'errore compare dentro il template, ma la causa è il tipo passato (Punto non ha operator>).

Specializzazione esplicita

Un template si può specializzare per un tipo particolare, fornendo un'altra implementazione: template <> const char* myMax<const char*>(...). È utile quando la versione generica sbaglia per quel tipo: per due const char*, x > y confronterebbe gli indirizzi, non i testi; la specializzazione usa strcmp. Qui myMax("pesca", "mela") usa la specializzazione e restituisce pesca.

Interi come parametri template

Finora template su tipi. I parametri template possono anche essere interi noti a tempo di compilazione: per esempio un array con tipo e numero di elementi.

template <typename T, int N>
struct array {
    T elem[N];
    T& operator[](int n);
    const T& operator[](int n) const;
    T* data() { return elem; }
    const T* data() const { return elem; }
    int size() const { return N; }
};
array<int, 256> gb;
array<double, 6> ad = {0.0, 1.1, 2.2, 3.3, 4.4, 5.5};
array<char, n> oops;      // errore se n non è noto a tempo di compilazione

#include <iostream>
using namespace std;

template <typename T, int N>         // due parametri template: un tipo e un INTERO
struct Array {
    T elem[N];                       // N e' noto a tempo di compilazione
    T& operator[](int n) { return elem[n]; }
    const T& operator[](int n) const { return elem[n]; }
    T* data() { return elem; }
    const T* data() const { return elem; }
    int size() const { return N; }
};

template <class T, int N>
void fill(Array<T, N>& b, const T& val)       // T e N sono DEDOTTI dall'argomento
{
    for (int i = 0; i < N; ++i) b[i] = val;
}

int main()
{
    Array<int, 256> gb;                                       // 256 int
    Array<double, 6> ad = {{0.0, 1.1, 2.2, 3.3, 4.4, 5.5}};
    constexpr int max = 1024;
    Array<char, max> loc;
    // int n = 5; Array<char, n> oops;                        // errore: n non e' noto in compilazione

    fill(loc, 'x');                  // T = char, N = 1024, dedotti da loc
    fill(ad, 0.5);                   // T = double, N = 6
    fill<int, 256>(gb, 7);           // la stessa cosa, con i parametri esplicitati

    Array<char, max> loc2 = loc;     // copia di backup (un Array si copia per valore)
    loc[0] = 'y';
    loc = loc2;                      // restore
    cout << loc[0] << ' ' << ad[5] << ' ' << gb[255] << ' ' << loc.size() << ' ' << ad.size() << '\n';
    return 0;
}

x 0.5 7 1024 6

Questi array sono concettualmente simili a quelli C ma meno flessibili (la dimensione è nel tipo): perché usarli?

• Efficienza: il compilatore può ottimizzare meglio; non usano il free store, quindi si possono usare dove l'allocazione dinamica non è disponibile.
• Offrono gli stessi vantaggi di interfaccia e sicurezza dei vector (size(), copia per valore, data()).
• Una dimensione fissa esprime un concetto: array<unsigned char, 3> è la tripletta (R, G, B) di un pixel. In C++ è disponibile come std::array.

Deduzione con parametri interi

template<class T, int N>
void fill(array<T, N>& b, const T& val)
{
    for (int i = 0; i < N; ++i) b[i] = val;
}
fill(buf, 'x');   // T = char, N = 1024 dedotti da buf
fill(b2, 0.0);    // T = double, N = 10 dedotti da b2

equivale a fill<char, 1024>(buf, 'x'); e fill<double, 10>(b2, 0.0);.

Template e file header

I template combinano flessibilità ed efficienza, con due effetti collaterali:

1. poca separazione fra dichiarazione e definizione;
2. errori di compilazione poco comprensibili.

Il compilatore, per generare Vector<int>::push_back, deve vedere la definizione completa della funzione nel punto in cui il template è usato. Se la definizione stesse in un .cpp compilato a parte (come per le classi normali) quel file non saprebbe che T è int, e main.cpp chiamerebbe un simbolo che nessuno ha generato:

undefined symbol: V<int>::push(int const&)       (errore del linker)

Per questo le definizioni di template vanno negli header. (Non lo impone lo standard ma le regole di istanziazione dei compilatori.) Per mantenere la separazione fra interfaccia e implementazione, si divide l'header in due blocchi combinati da un #include atipico:

vector.h termina con #include "vector.hpp" prima del #endif (come nell'esempio sopra); entrambi i file hanno le include guard. L'utente include solo vector.h. Per progetti più grandi vedi C++ - buona interfaccia e progetti su più fileUna classe C++ ben progettata decide esplicitamente le sette operazioni essenziali (costruttore con argomenti, di default, di copia, assegnamento di copia, costruttore e assegnamento di spostamento, distruttore): se serve il distruttore perché si possiede una risorsa, servono quasi sempre anche copia e spostamento; un costruttore a un argomento definisce una conversione implicita, che si blocca con explicit; per capire quando i costruttori e il distruttore vengono chiamati si traccia una struct che stampa ogni chiamata. Un progetto su più file separa interfaccia (header .h con definizioni di classe e dichiarazioni, protetto da include guard) e implementazione (.cpp, compilati uno per uno, mai inclusi); al compilatore si passano solo i .cpp, il main sta in un file a sé; gli errori di compilazione (sintassi, tipi, dichiarazioni mancanti) vengono dal compilatore, quelli di linking (definizione mancante, due main, nessun main) dal linker.C++ - buona interfaccia e progetti su più file → e CMake - build di progetti C++Un progetto C++ non è fatto solo di sorgenti: bisogna dire quali file formano ogni eseguibile e ogni libreria (target), quali librerie linkare, dove stanno gli header e con quale standard compilare. CMake è un meta-sistema di build indipendente da compilatore e piattaforma: si descrive il progetto in un file di testo CMakeLists.txt (cmake_minimum_required, project, add_library, add_executable, target_link_libraries, include directories) e CMake genera i file del sistema di build nativo (Makefile, progetto di IDE). Lato utente si fa una configurazione (mkdir build, cd build, cmake ..) e poi la compilazione (make o cmake --build .) in una cartella di build separata dai sorgenti; le librerie di soli template (header-only) si dichiarano INTERFACE perché non producono codice precompilato.CMake - build di progetti C++ →.

Domande d'esame

1. Cos'è un template e che notazione si usa per una funzione e per una classe? Vantaggi e svantaggi. Traccia. Parametrizzazione di classi o funzioni su un tipo (o intero); template <typename T> davanti; il compilatore genera il codice per ogni tipo usato (a tempo di compilazione). Vantaggi: codice generico senza costo a run-time. Svantaggi: errori poco leggibili, molto codice generato, definizione nell'header. Soluzioni: Esercizio - Template, specializzazione e deduzione degli argomenti (quarto appello 2021-22, teoria), Esercizio - Template di classe (quarto appello 2022-23, teoria).

2. Cosa significa che gli argomenti template sono dedotti dal compilatore? Traccia. Dalla chiamata myMax(i, j) (due int) il compilatore ricava T = int senza scrivere myMax<int>; con fill(buf, 'x') ricava sia T sia N. Se due argomenti dello stesso T hanno tipi diversi, la deduzione fallisce.

3. Una funzione template bool AreEqual(const T& a, const T& b) { return a == b; }: è replicata per ogni tipo? Impone vincoli su T? Compila solo per i built-in? Traccia. Sì, una versione per ogni T usato. Vincoli: T deve avere operator==. Compila per ogni tipo che lo supporta (anche classi con operator==); il costruttore di copia non serve, perché i parametri sono reference.

4. Quando si può usare un intero come parametro template e perché? Traccia. Quando il valore è noto a tempo di compilazione (array<char, 1024>, non array<char, n> con n variabile). Serve per dimensioni fisse senza free store e per esprimere concetti (la tripletta RGB).