Esercizio - MyVector 2.0 con template (laboratorio 5)

In questa pagina 3

Quinto laboratorio del corso di Laboratorio di Programmazione, Ing. Informatica UniPD: la classe del Esercizio - MyVector 2.0 con buffer ridimensionabile (laboratorio 4) resa generica sul tipo degli elementi. Teoria: C++ - template e programmazione generica; la STL, di cui MyVector è una versione ridotta, è in STL - sequenze, iteratori e container (vector, list, string).

Testo. Implementare la classe MyVector del laboratorio 4 rendendo generici gli elementi contenuti, cioè sostituendo double con un tipo generico T mediante i template. Tutte le funzioni richieste nel laboratorio 4 devono essere aggiornate. È obbligatorio implementare tutte le funzioni membro esternamente alla classe, quindi le definizioni in-class sono vietate. È inoltre obbligatorio indicare prima i membri public, poi i private. Promemoria: dati gestiti con allocazione dinamica; il buffer è più grande dell'effettivo numero di elementi (servono due valori: elementi salvati e massimo gestibile col buffer corrente); la riallocazione comporta la copia; la politica di gestione della memoria può essere diversa da quella del laboratorio 4. Funzioni: operazioni essenziali, doppio overloading di operator[], at() con eccezione, push_back(), pop_back(), reserve().

Che cosa cambia rispetto al laboratorio 4

aspetto	laboratorio 4 (`double`)	laboratorio 5 (`T`)
dichiarazione	`class MyVector`	`template <typename T> class MyVector`
buffer	`double* buffer_`	`T* buffer_`, allocato con `new T[n]`
elemento nullo	`0.0`	`T{}` (il valore di default di `T`: `0`, stringa vuota, vettore vuoto)
passaggio degli elementi	`double value`	`const T& value`: un `T` può essere grande (una `string`, un vettore)
definizioni	in `myvector.cpp`	nell'header: `myvector.h` + `myvector.hpp`
ogni funzione fuori classe	`MyVector::push_back`	`template <typename T> void MyVector<T>::push_back(const T&)`
tipo restituito	`double&`	`T&`
file	`.h` e `.cpp` (compilato a parte)	niente `.cpp` per la classe

Perché niente .cpp: il compilatore genera MyVector<int>, MyVector<string>, ... solo quando vede un uso, e per farlo deve avere sott'occhio le definizioni; se stessero in un .cpp compilato a parte, ogni uso darebbe un errore del linker (undefined symbol: MyVector<int>::push_back(...)). Il testo chiede però di mantenere la separazione fra interfaccia e implementazione, e lo si ottiene con la tecnica dei due file: myvector.h contiene la classe (solo dichiarazioni) e in coda include myvector.hpp, che contiene le definizioni (C++ - template e programmazione generica). Entrambi hanno le include guard. L'utente include solo myvector.h.

Il codice

myvector.hcpp

#ifndef MYVECTOR_H
#define MYVECTOR_H

#include <cstddef>
#include <initializer_list>

// Vettore generico: T e' il tipo degli elementi.
// Requisiti su T: costruttore di default (new T[n] costruisce n elementi) e assegnamento di copia.
template <typename T>
class MyVector {
public:                                                  // prima i membri public...
    MyVector();
    explicit MyVector(std::size_t n);
    MyVector(std::initializer_list<T> lst);
    MyVector(const MyVector& other);
    MyVector& operator=(const MyVector& other);
    MyVector(MyVector&& other) noexcept;
    MyVector& operator=(MyVector&& other) noexcept;
    ~MyVector();

    T& operator[](std::size_t i);
    const T& operator[](std::size_t i) const;
    T& at(std::size_t i);
    const T& at(std::size_t i) const;

    std::size_t size() const;
    std::size_t capacity() const;
    bool empty() const;
    void push_back(const T& value);
    void pop_back();
    void reserve(std::size_t new_capacity);

private:                                                 // ...poi i private (richiesto dal testo)
    std::size_t size_;
    std::size_t capacity_;
    T* buffer_;
};

#include "myvector.hpp"                                  // le definizioni: in coda all'header

#endif // MYVECTOR_H

myvector.hppcpp

#ifndef MYVECTOR_HPP
#define MYVECTOR_HPP

#include <algorithm>
#include <stdexcept>

// Tutte le funzioni membro sono definite FUORI dalla classe: ognuna ha il suo "template <typename T>"
// e il nome qualificato MyVector<T>::

template <typename T>
MyVector<T>::MyVector() : size_{0}, capacity_{0}, buffer_{nullptr} {}

template <typename T>
MyVector<T>::MyVector(std::size_t n)
    : size_{n}, capacity_{n}, buffer_{n > 0 ? new T[n] : nullptr}
{
    std::fill(buffer_, buffer_ + size_, T{});            // T{}: valore di default del tipo (0, "", ...)
}

template <typename T>
MyVector<T>::MyVector(std::initializer_list<T> lst)
    : size_{lst.size()}, capacity_{lst.size()}, buffer_{lst.size() > 0 ? new T[lst.size()] : nullptr}
{
    std::copy(lst.begin(), lst.end(), buffer_);
}

template <typename T>
MyVector<T>::MyVector(const MyVector& other)
    : size_{other.size_}, capacity_{other.size_}, buffer_{other.size_ > 0 ? new T[other.size_] : nullptr}
{
    std::copy(other.buffer_, other.buffer_ + size_, buffer_);
}

template <typename T>
MyVector<T>& MyVector<T>::operator=(const MyVector& other)
{
    if (this == &other) return *this;
    T* nuovo = other.size_ > 0 ? new T[other.size_] : nullptr;
    std::copy(other.buffer_, other.buffer_ + other.size_, nuovo);
    delete[] buffer_;
    buffer_ = nuovo;
    size_ = capacity_ = other.size_;
    return *this;
}

template <typename T>
MyVector<T>::MyVector(MyVector&& other) noexcept
    : size_{other.size_}, capacity_{other.capacity_}, buffer_{other.buffer_}
{
    other.size_ = 0;
    other.capacity_ = 0;
    other.buffer_ = nullptr;
}

template <typename T>
MyVector<T>& MyVector<T>::operator=(MyVector&& other) noexcept
{
    if (this != &other) {
        delete[] buffer_;
        size_ = other.size_;
        capacity_ = other.capacity_;
        buffer_ = other.buffer_;
        other.size_ = 0;
        other.capacity_ = 0;
        other.buffer_ = nullptr;
    }
    return *this;
}

template <typename T>
MyVector<T>::~MyVector() { delete[] buffer_; }

template <typename T>
T& MyVector<T>::operator[](std::size_t i) { return buffer_[i]; }

template <typename T>
const T& MyVector<T>::operator[](std::size_t i) const { return buffer_[i]; }

template <typename T>
T& MyVector<T>::at(std::size_t i)
{
    if (i >= size_) throw std::out_of_range("MyVector::at: indice fuori dai limiti");
    return buffer_[i];
}

template <typename T>
const T& MyVector<T>::at(std::size_t i) const
{
    if (i >= size_) throw std::out_of_range("MyVector::at: indice fuori dai limiti");
    return buffer_[i];
}

template <typename T>
std::size_t MyVector<T>::size() const { return size_; }

template <typename T>
std::size_t MyVector<T>::capacity() const { return capacity_; }

template <typename T>
bool MyVector<T>::empty() const { return size_ == 0; }

template <typename T>
void MyVector<T>::reserve(std::size_t new_capacity)
{
    if (new_capacity <= capacity_) return;
    T* nuovo = new T[new_capacity];
    std::copy(buffer_, buffer_ + size_, nuovo);
    delete[] buffer_;
    buffer_ = nuovo;
    capacity_ = new_capacity;
}

template <typename T>
void MyVector<T>::push_back(const T& value)
{
    if (size_ == capacity_) reserve(capacity_ == 0 ? 4 : 2 * capacity_);
    buffer_[size_] = value;
    ++size_;
}

template <typename T>
void MyVector<T>::pop_back()
{
    if (size_ == 0) throw std::out_of_range("MyVector::pop_back: vettore vuoto");
    --size_;
}

#endif // MYVECTOR_HPP

Dettagli da notare:

Prima public, poi private, come richiesto. Persino size(), capacity() e empty() sono definite fuori (nel .hpp).
Nelle firme fuori dalla classe compare MyVector<T>:: davanti al nome; dopo di esso, nell'elenco dei parametri, basta scrivere MyVector (il nome della classe dentro il suo scope sta per MyVector<T>): MyVector<T>::MyVector(const MyVector& other). Il tipo restituito, che sta prima del nome qualificato, va invece scritto per esteso: MyVector<T>& MyVector<T>::operator=(const MyVector& other).
Gli algoritmi std::copy e std::fill funzionano per qualsiasi T copiabile; std::fill(buffer_, buffer_ + size_, T{}) sostituisce il ciclo che metteva 0.0.
push_back(const T& value) fa buffer_[size_] = value: un assegnamento su un elemento già costruito (vedi sotto).
La politica di crescita è sempre il raddoppio a partire da 4 (costo ammortizzato costante, Esercizio - MyVector 2.0 con buffer ridimensionabile (laboratorio 4)).

Programma di prova

main.cppcpp

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

template <typename T>
void stampa(const string& nome, const MyVector<T>& v)       // anche la funzione di stampa e' un template
{
    cout << nome << " (size " << v.size() << ", capacity " << v.capacity() << "):";
    for (size_t i = 0; i < v.size(); ++i) cout << ' ' << v[i];
    cout << '\n';
}

int main()
{
    MyVector<int> vi;                              // la classe MyVector<int> generata dal compilatore
    for (int i = 1; i <= 5; ++i) vi.push_back(i * i);
    stampa("vi", vi);

    MyVector<double> vd {1.5, 2.5, 3.5};           // MyVector<double>
    vd.push_back(4.5);
    stampa("vd", vd);

    MyVector<string> vs;                           // MyVector<string>
    vs.push_back("ciao");
    vs.push_back("mondo");
    MyVector<string> copia = vs;                   // copia profonda: ogni stringa e' copiata
    copia[0] = "salve";
    stampa("vs", vs);
    stampa("copia", copia);

    MyVector<MyVector<int>> matrice;               // un vettore di vettori
    for (int r = 1; r <= 3; ++r) {
        MyVector<int> riga;
        for (int c = 1; c <= r; ++c) riga.push_back(r * 10 + c);
        matrice.push_back(riga);
    }
    for (size_t r = 0; r < matrice.size(); ++r) stampa("riga", matrice[r]);

    MyVector<int> spostato = std::move(vi);
    stampa("spostato", spostato);
    stampa("vi dopo lo spostamento", vi);

    try {
        cout << vd.at(10) << '\n';
    }
    catch (out_of_range&) {
        cout << "vd.at(10): indice fuori dai limiti\n";
    }
    return 0;
}

Il programma usa try/catch: in WebAssembly le eccezioni non funzionano, quindi l'uscita è ricavata a mano e confermata eseguendo una copia in cui throw stampa e termina.

vi (size 5, capacity 8): 1 4 9 16 25
vd (size 4, capacity 6): 1.5 2.5 3.5 4.5
vs (size 2, capacity 4): ciao mondo
copia (size 2, capacity 2): salve mondo
riga (size 1, capacity 1): 11
riga (size 2, capacity 2): 21 22
riga (size 3, capacity 3): 31 32 33
spostato (size 5, capacity 8): 1 4 9 16 25
vi dopo lo spostamento (size 0, capacity 0):
vd.at(10): indice fuori dai limiti

Il compilatore ha generato quattro classi: MyVector<int>, MyVector<double>, MyVector<string> e MyVector<MyVector<int>>. Anche stampa è un template di funzione: T è dedotto dal secondo argomento.
vd parte da 3 elementi (initializer_list, capacity 3): il push_back raddoppia a 6. vi arriva a 5 elementi con capacità 8 (4 → 8).
copia = vs è una copia profonda: dopo copia[0] = "salve", vs conserva ciao; capacity 2 perché la copia ha solo lo spazio che serve.
Il vettore di vettori ha righe di lunghezza diversa; matrice.push_back(riga) copia la riga (e quando la matrice rialloca, copia ogni riga con operator= di MyVector<int>).
std::move(vi) lascia vi vuoto e passa il buffer a spostato.

Limite di questa soluzione: i requisiti su `T`

new T[n] costruisce n oggetti di default: T deve avere un costruttore di default e l'assegnamento, e la capacity extra non è "spazio libero" ma oggetti già costruiti. Il programma seguente lo mostra con un tipo che conta le costruzioni e gli assegnamenti, confrontando con std::vector:

main.cppcpp

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

// Un tipo che conta le sue costruzioni di default e le sue copie
struct Tracer {
    static int costruzioni, assegnamenti;
    Tracer() { ++costruzioni; }
    Tracer(const Tracer&) = default;
    Tracer& operator=(const Tracer&) { ++assegnamenti; return *this; }
};
int Tracer::costruzioni = 0;
int Tracer::assegnamenti = 0;

int main()
{
    {
        MyVector<Tracer> v;
        v.push_back(Tracer());                   // 1 elemento in uso...
        cout << "MyVector<Tracer>: size " << v.size() << ", costruzioni di default "
             << Tracer::costruzioni - 1 << ", assegnamenti " << Tracer::assegnamenti << '\n';
        // (il -1 toglie il temporaneo Tracer() passato a push_back)
    }
    Tracer::costruzioni = 0;
    Tracer::assegnamenti = 0;
    {
        vector<Tracer> v;
        v.push_back(Tracer());
        cout << "std::vector<Tracer>: size " << v.size() << ", costruzioni di default "
             << Tracer::costruzioni - 1 << ", assegnamenti " << Tracer::assegnamenti << '\n';
    }
    return 0;
}

MyVector<Tracer>: size 1, costruzioni di default 4, assegnamenti 1
std::vector<Tracer>: size 1, costruzioni di default 0, assegnamenti 0

Con MyVector<Tracer> un solo push_back costruisce quattro oggetti (la capacità iniziale) e fa un assegnamento; std::vector non ne costruisce nessuno di default: alloca memoria grezza e costruisce un elemento alla volta sul posto (placement new) e li distrugge a mano. Per tipi senza costruttore di default o con costruzione costosa, MyVector<T> così com'è non va bene. Fa parte dello scopo didattico: il layout è lo stesso della STL, i dettagli di gestione della memoria grezza no. Per gli elementi di tipo double, int e string la soluzione è corretta.

Versione ripasso

Da lab 4 a lab 5: template <typename T> class MyVector; buffer T* buffer_ con new T[n]; elemento nullo T{}; push_back(const T& value) (un T può essere grande); tipo restituito T&; tutte le funzioni membro fuori dalla classe, con template <typename T> e MyVector<T>::; membri public prima dei private.
File: myvector.h (classe con sole dichiarazioni, in coda #include "myvector.hpp") e myvector.hpp (definizioni); entrambi con include guard; nessun .cpp per la classe (altrimenti undefined symbol dal linker: il compilatore deve vedere le definizioni quando istanzia).

cpp

template <typename T>
void MyVector<T>::push_back(const T& value)
{ if (size_ == capacity_) reserve(capacity_ == 0 ? 4 : 2 * capacity_);
  buffer_[size_] = value; ++size_; }
template <typename T>
MyVector<T>::MyVector(std::size_t n) : size_{n}, capacity_{n}, buffer_{n > 0 ? new T[n] : nullptr}
{ std::fill(buffer_, buffer_ + size_, T{}); }

Prova: MyVector<int> con push_back(i*i) $\to$ 1 4 9 16 25, capacity 8; MyVector<double> {1.5, 2.5, 3.5} + push_back $\to$ capacity 6; MyVector<string> e copia profonda (copia[0] = "salve", vs resta ciao); MyVector<MyVector<int>> con righe di lunghezza 1, 2, 3; std::move $\to$ sorgente size 0, capacity 0; vd.at(10) $\to$ out_of_range.
Requisiti su T: new T[n] costruisce n oggetti di default $\Rightarrow$ serve il costruttore di default e l'assegnamento; con un tipo che conta: MyVector<Tracer> dopo un push_back ha 4 costruzioni di default e 1 assegnamento, std::vector<Tracer> 0 e 0 (memoria grezza + costruzione sul posto).
Struttura dei file:

cpp

// myvector.h
#ifndef MYVECTOR_H
#define MYVECTOR_H
template <typename T>
class MyVector {
public:                                              // prima i public...
    MyVector();  explicit MyVector(std::size_t n);  MyVector(std::initializer_list<T> lst);
    MyVector(const MyVector& other);  MyVector& operator=(const MyVector& other);
    MyVector(MyVector&& other) noexcept;  MyVector& operator=(MyVector&& other) noexcept;  ~MyVector();
    T& operator[](std::size_t i);  const T& operator[](std::size_t i) const;
    T& at(std::size_t i);  const T& at(std::size_t i) const;
    std::size_t size() const;  std::size_t capacity() const;  bool empty() const;
    void push_back(const T& value);  void pop_back();  void reserve(std::size_t new_capacity);
private:                                             // ...poi i private
    std::size_t size_, capacity_;  T* buffer_;
};
#include "myvector.hpp"                              // definizioni in coda
#endif

Esempi di definizioni fuori classe: template <typename T> std::size_t MyVector<T>::size() const { return size_; }; template <typename T> MyVector<T>& MyVector<T>::operator=(const MyVector& other) { if (this == &other) return *this; T* nuovo = ...; std::copy(...); delete[] buffer_; buffer_ = nuovo; size_ = capacity_ = other.size_; return *this; }; template <typename T> void MyVector<T>::reserve(std::size_t n) { if (n <= capacity_) return; T* nuovo = new T[n]; std::copy(buffer_, buffer_ + size_, nuovo); delete[] buffer_; buffer_ = nuovo; capacity_ = n; }.
Come si usa: MyVector<int> vi; vi.push_back(4); $\to$ capacità 4, poi 8 al quinto; MyVector<string> vs; MyVector<string> copia = vs;; MyVector<MyVector<int>> matrice; con matrice.push_back(riga); stampa è a sua volta un template: template <typename T> void stampa(const string& nome, const MyVector<T>& v).
Errori tipici: definire le funzioni nel .cpp; dimenticare template <typename T> o <T> in una definizione fuori classe; usare 0 invece di T{}; passare T per valore; mettere i membri private prima dei public contro la consegna; includere myvector.hpp senza guard.

Esercizio - MyVector 2.0 con template (laboratorio 5)

Che cosa cambia rispetto al laboratorio 4

Il codice

Programma di prova

Limite di questa soluzione: i requisiti su `T`

Esercizi su questo argomento

Teoria collegata

Esercizio - MyVector 2.0 con template (laboratorio 5)

Che cosa cambia rispetto al laboratorio 4

Il codice

Programma di prova

Limite di questa soluzione: i requisiti su T

Esercizi su questo argomento

Teoria collegata

Limite di questa soluzione: i requisiti su `T`