Esercizio - Template di classe (quarto appello 2022-23, teoria)

Esame

In questa pagina 3

Domanda aperta 2 del quarto appello 2022-23 del corso di Laboratorio di Programmazione, Ing. Informatica UniPD. Teoria: C++ - template e programmazione generica. Per le funzioni template e la specializzazione vedi Esercizio - Template, specializzazione e deduzione degli argomenti (quarto appello 2021-22, teoria).

Testo. Descrivere il concetto di template in C++ e la notazione utilizzata per definire una classe template. Riportare il codice C++ di una classe che sfrutti opportunamente il concetto di template.

Il concetto

Un template permette di usare un tipo come parametro di una classe o di una funzione: il compilatore genera il codice per ogni tipo per cui il template è specializzato (template instantiation), a tempo di compilazione. Un class template si chiama anche type generator, parametrized type o parametrized class: vector<double>, vector<int>, vector<Window*> sono specializzazioni di vector. Serve a scrivere una volta una classe come Stack o vector che funziona per int, string o qualunque altro tipo, senza copiare il codice né perdere il controllo dei tipi (a differenza di void*), e senza costo a run-time (a differenza del polimorfismo dinamico).

Notazione

cpp

template <typename T>              // oppure: template <class T>  (equivalenti)
class Stack {
    // T e' un tipo qualunque: si usa dentro la classe come un tipo normale
    T* data_;
public:
    void push(const T& value);     // dichiarazione
};

template <typename T>              // ogni funzione membro definita FUORI ripete il prefisso...
void Stack<T>::push(const T& value) { /* ... */ }    // ...e si qualifica con Stack<T>::

Stack<int> si;                     // specializzazione: il compilatore genera Stack<int>
Stack<std::string> ss;             // e Stack<std::string>

template <typename T> introduce il parametro; typename è più chiaro (si capisce che vanno bene anche i tipi built-in), class è più corto: equivalenti.
Si possono avere più parametri, anche interi: template <typename T, int N> (C++ - template e programmazione generica).
Per usare la classe si scrive il tipo fra <>: Stack<int>. Non c'è deduzione automatica del tipo dalla dichiarazione di una variabile (da C++17 in alcuni casi si deduce dal costruttore).
Le definizioni vanno negli header: il compilatore deve vederle quando istanzia. Se si vuole separare interfaccia e implementazione, si usa il .hpp incluso in coda al .h.
Requisiti impliciti su T: qui costruttore di default e assegnamento (per new T[n] e per le copie). Se T non li ha, l'errore è lungo e compare all'istanza.

Una classe template: una pila

Stack<T> gestisce una pila di elementi di tipo T con un buffer dinamico che raddoppia quando è pieno. Le funzioni sono definite fuori dalla classe, come richiesto dalla notazione; size() e empty(), brevissime, restano in classe.

stack_template.cppcpp

#include <cstddef>
#include <iostream>
#include <string>
#include <utility>
using namespace std;

// CLASS TEMPLATE: una pila di elementi di tipo T. "template <typename T>" davanti alla classe.
template <typename T>
class Stack {
public:
    Stack() : size_{0}, capacity_{0}, data_{nullptr} {}
    ~Stack() { delete[] data_; }
    Stack(const Stack&) = delete;                         // per semplicita': non copiabile
    Stack& operator=(const Stack&) = delete;

    void push(const T& value);                            // definite FUORI dalla classe (sotto)
    T pop();
    const T& top() const;
    bool empty() const { return size_ == 0; }
    size_t size() const { return size_; }

private:
    void cresci();
    size_t size_;
    size_t capacity_;
    T* data_;
};

// Fuori dalla classe: ogni funzione ha template <typename T> e il nome Stack<T>::
template <typename T>
void Stack<T>::cresci()
{
    size_t nuova = capacity_ == 0 ? 4 : 2 * capacity_;
    T* nuovo = new T[nuova];
    for (size_t i = 0; i < size_; ++i) nuovo[i] = data_[i];
    delete[] data_;
    data_ = nuovo;
    capacity_ = nuova;
}

template <typename T>
void Stack<T>::push(const T& value)
{
    if (size_ == capacity_) cresci();
    data_[size_++] = value;
}

template <typename T>
T Stack<T>::pop()
{
    return data_[--size_];                                // (senza controllo dello stack vuoto: semplificazione)
}

template <typename T>
const T& Stack<T>::top() const { return data_[size_ - 1]; }

int main()
{
    Stack<int> si;                                        // il compilatore genera la classe Stack<int>
    for (int i = 1; i <= 5; ++i) si.push(i * i);
    cout << "Stack<int>: top = " << si.top() << ", size = " << si.size() << '\n';
    cout << "estratti:";
    while (!si.empty()) cout << ' ' << si.pop();
    cout << '\n';

    Stack<string> ss;                                     // e Stack<string>
    ss.push("uno");
    ss.push("due");
    ss.push("tre");
    cout << "Stack<string>: top = " << ss.top() << ", size = " << ss.size() << '\n';
    string estratta = ss.pop();
    cout << "pop = " << estratta << ", size = " << ss.size() << '\n';
    return 0;
}

Stack<int>: top = 25, size = 5
estratti: 25 16 9 4 1
Stack<string>: top = tre, size = 3
pop = tre, size = 2

Stack<int> si; e Stack<string> ss; sono due classi diverse, generate dal compilatore, con lo stesso codice scritto una volta.
Le chiamate a push e pop sono risolte a tempo di compilazione, senza costo a run-time.
La pila è LIFO: gli estratti compaiono nell'ordine inverso (25 16 9 4 1).
Con un tipo senza costruttore di default (per esempio una classe con solo Y(int)) new T[nuova] non compilerebbe: è uno dei requisiti sul tipo.

Vantaggi: codice generico scritto una volta, nessun costo a run-time, controlli di tipo in compilazione. Svantaggi: codice generato per ogni tipo, messaggi di errore lunghi, definizioni negli header, requisiti non dichiarati.

Versione ripasso

Template = tipo (o intero) come parametro di una classe o funzione; il compilatore genera il codice per ogni tipo usato (instantiation) a compile-time. Class template = type generator (vector<double>, vector<int>). Evita di duplicare il codice mantenendo i controlli di tipo e senza costo a run-time. Rimando: C++ - template e programmazione generica.
Notazione: template <typename T> ( $\equiv$ template <class T>) davanti alla classe; funzioni fuori dalla classe: template <typename T> void Stack<T>::push(const T& value) { ... }; uso: Stack<int> si;, Stack<std::string> ss;. Più parametri, anche interi (template <typename T, int N>). Definizioni nell'header (.hpp incluso in coda al .h). Requisiti impliciti su T.

cpp

template <typename T>
class Stack {
public:
    void push(const T& value);  T pop();  const T& top() const;
    bool empty() const { return size_ == 0; }  size_t size() const { return size_; }
private:
    void cresci();  size_t size_, capacity_;  T* data_;
};
template <typename T>
void Stack<T>::push(const T& value) { if (size_ == capacity_) cresci(); data_[size_++] = value; }

Prova: Stack<int> con $1, 4, 9, 16, 25$ : top = 25, size = 5, estratti 25 16 9 4 1 (LIFO); Stack<string> con uno, due, tre: top = tre, pop = tre, size = 2.
Pro e contro: generico, nessun costo a run-time, controlli in compilazione / codice per ogni tipo, errori oscuri, definizioni negli header.
Errori tipici: definire i membri in un .cpp (errore del linker); dimenticare template <typename T> o <T> nelle definizioni fuori classe; usare un tipo senza costruttore di default con new T[n]; credere che Stack<int> e Stack<string> siano la stessa classe.

Esercizi su questo argomento

Teoria collegata

C++ - template e programmazione generica