Esercizio - Numeri razionali con classe e overloading (laboratorio 2)

Secondo laboratorio del corso di Laboratorio di Programmazione, Ing. Informatica UniPD: progettare la classe Rational e darle gli operatori. Teoria: C++ - classi, membri e invariantiuna classe è un tipo definito dal programmatore che rappresenta un concetto con una rappresentazione (dati membro) e delle operazioni (funzioni membro); l'interfaccia pubblica separa chi usa la classe da chi la implementa e i dati privati sono modificabili solo tramite l'interfaccia; struct è una class con membri pubblici di default; l'invariante è la regola che definisce gli stati validi, e il costruttore deve stabilirlo e ogni funzione membro conservarlo; il costruttore (stesso nome della classe) inizializza con una lista di inizializzazione e, se i dati non sono validi, lancia un'eccezione, l'unico modo per far fallire un costruttore; le funzioni membro si definiscono fuori dalla classe (solo le brevissime dentro, dove sono inline); le funzioni che non modificano l'oggetto sono dichiarate const; le funzioni che si possono scrivere con la sola interfaccia pubblica (operator==, next_sunday) sono helper function esterne, spesso nello stesso namespace.C++ - classi, membri e invarianti →, C++ - enumerazioni e overloading degli operatoriun'enumerazione è un tipo definito dall'utente che specifica un insieme di valori simbolici (enumeratori); enum class crea uno scope (Month::jan), non si converte implicitamente in int, e i valori partono da 0 o dal valore del precedente più uno; l'overloading degli operatori permette di definire gli operatori esistenti per tipi definiti dall'utente (almeno un operando UDT, stesso numero di operandi e stessa sintassi) scrivendo una funzione di nome operator+, operator++, operator[], ...; si può fare con una helper function (due argomenti per un operatore binario, il primo può essere di qualunque tipo) o con una funzione membro (un argomento in meno, perché il primo operando è l'oggetto, quindi l'UDT deve stare a sinistra: T + int sì, int + T no); << e >> sono helper function che prendono e restituiscono ostream& e istream&; ++ ha due forme (pre e post, quest'ultima con un int fittizio); gli operatori più utili sono =, ==, !=, <, [], ().C++ - enumerazioni e overloading degli operatori →, per la copia 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 →.

Testo. Dal libro di testo (cap. 9, esercizio 13). Progettare e realizzare la classe Rational: un numero razionale ha un numeratore e un denominatore, per esempio $5/6$ (circa $0.83333$). Fornire: A. un costruttore di default che inizializza il numero a 0; B. un costruttore con un argomento int (un intero da rappresentare come razionale); C. un costruttore con due int, numeratore e denominatore; D. l'assegnamento; E. addizione; F. sottrazione; G. moltiplicazione; H. divisione; I. uguaglianza (==), maggiore (>), minore (<) e l'operatore di uscita su stream (<<). Fornire anche una conversione a double con una funzione to_double(). Provare tutti gli operatori in main.

Per l'addizione provare l'overloading di: A. somma di due Rational; B. somma di un Rational e di un int. Entrambi vanno scritti in due modi: come funzione membro e come helper function (non contemporaneamente). Quali sono le differenze fra int + Rational e Rational + int? Prestare molta attenzione al tipo restituito, e a se debba essere una variabile o una reference.

Domande di discussione

1. Quali sono le due parti di una classe? L'interfaccia (membri public: ciò che l'utente può usare) e l'implementazione (membri private: dati e funzioni di servizio).

2. Differenza fra interfaccia e implementazione. L'interfaccia è il punto di vista di chi usa la classe e cambia raramente; l'implementazione è il punto di vista di chi la scrive, nascosta e libera di cambiare. Qui: l'interfaccia di Rational sono i costruttori, numerator(), denominator(), gli operatori; num_ e den_ e normalize() sono l'implementazione.

3. Perché un costruttore invece di una funzione init_day()? Il costruttore è chiamato sempre alla creazione, non si può bypassare e può rifiutare un oggetto non valido (un denominatore nullo); una funzione di inizializzazione si può dimenticare, e nel frattempo l'oggetto esiste in uno stato inutilizzabile.

4. Cos'è un invariante? Esempi. Una regola sullo stato valido che il costruttore stabilisce e ogni funzione membro conserva. Per Rational: $den > 0$ e frazione ridotta ai minimi termini (lo zero è $0/1$). Con questi invarianti ogni razionale ha una rappresentazione unica, e l'uguaglianza si riduce al confronto dei due interi.

5. Dentro o fuori dalla classe? Dentro solo funzioni brevissime (qui numerator(), denominator()), perché diventano inline; il resto fuori, per tenere pulita l'interfaccia e per non forzare la ricompilazione dei client a ogni modifica.

Progetto della classe

Decisioni, in ordine:

Gli accessori numerator() e denominator() sono const, in modo che le helper function possano leggere anche da const Rational&. Il costruttore riporta sempre alla forma normale con normalize(): sposta il segno al numeratore e divide per il MCD del valore assoluto (std::gcd(abs(num_), den_); gcd(0, d) = d fa diventare $0/d$ uguale a $0/1$).

Le formule: $\dfrac{a}{b} + \dfrac{c}{d} = \dfrac{ad + cb}{bd}$, $\dfrac{a}{b} \cdot \dfrac{c}{d} = \dfrac{ac}{bd}$, $\dfrac{a}{b} \div \dfrac{c}{d} = \dfrac{ad}{bc}$ (con $c \ne 0$): il costruttore pensa a ridurre e a sistemare il segno, anche se $c$ è negativo. Per $<$: $\dfrac{a}{b} < \dfrac{c}{d} \iff ad < cb$, valido perché i denominatori sono positivi (invariante!); il prodotto si calcola in long long per evitare l'overflow.

I file

#ifndef RATIONAL_H
#define RATIONAL_H

#include <iosfwd>

// Numero razionale num/den.
// Invarianti: den_ > 0 e la frazione e' ridotta ai minimi termini (MCD = 1); lo zero e' 0/1.
class Rational {
public:
    class DivisionByZero {};                       // segnala un denominatore o un divisore nullo

    Rational(int num = 0, int den = 1);            // tre costruttori in uno: 0, n/1, num/den
    // Copia, assegnamento e distruttore NON si scrivono: i membri sono due int e quelli generati
    // dal compilatore (membro a membro) sono gia' corretti.

    int numerator() const { return num_; }
    int denominator() const { return den_; }
    double to_double() const;                      // conversione esplicita a double

private:
    void normalize();                              // ripristina gli invarianti

    int num_;
    int den_;
};

// Tutti gli operatori binari sono helper function: non servono i dati privati
// e le conversioni implicite valgono per ENTRAMBI gli operandi (r + 1 e 1 + r).
Rational operator+(const Rational& a, const Rational& b);
Rational operator-(const Rational& a, const Rational& b);
Rational operator*(const Rational& a, const Rational& b);
Rational operator/(const Rational& a, const Rational& b);   // lancia DivisionByZero se b == 0

bool operator==(const Rational& a, const Rational& b);
bool operator!=(const Rational& a, const Rational& b);
bool operator<(const Rational& a, const Rational& b);
bool operator>(const Rational& a, const Rational& b);

std::ostream& operator<<(std::ostream& os, const Rational& r);

#endif // RATIONAL_H

#include "rational.h"

#include <cstdlib>
#include <numeric>
#include <ostream>

Rational::Rational(int num, int den) : num_{num}, den_{den}
{
    if (den_ == 0) throw DivisionByZero();   // il denominatore nullo violerebbe l'invariante
    normalize();
}

void Rational::normalize()
{
    if (den_ < 0) {                          // il segno sta sempre al numeratore
        num_ = -num_;
        den_ = -den_;
    }
    int g = std::gcd(std::abs(num_), den_);  // gcd(0, d) = d: lo zero diventa 0/1
    num_ /= g;
    den_ /= g;
}

double Rational::to_double() const
{
    // il cast sul numeratore serve: senza, num_ / den_ sarebbe una divisione tra interi
    return static_cast<double>(num_) / den_;
}

Rational operator+(const Rational& a, const Rational& b)
{
    // a/b + c/d = (a*d + c*b) / (b*d); il costruttore riduce e sistema il segno
    return Rational(a.numerator() * b.denominator() + b.numerator() * a.denominator(),
                    a.denominator() * b.denominator());
}

Rational operator-(const Rational& a, const Rational& b)
{
    return Rational(a.numerator() * b.denominator() - b.numerator() * a.denominator(),
                    a.denominator() * b.denominator());
}

Rational operator*(const Rational& a, const Rational& b)
{
    return Rational(a.numerator() * b.numerator(), a.denominator() * b.denominator());
}

Rational operator/(const Rational& a, const Rational& b)
{
    if (b.numerator() == 0) throw Rational::DivisionByZero();
    // a/b : c/d = a*d / (b*c); se c e' negativo il costruttore sposta il segno
    return Rational(a.numerator() * b.denominator(), a.denominator() * b.numerator());
}

bool operator==(const Rational& a, const Rational& b)
{
    // grazie agli invarianti (ridotta, den > 0) la rappresentazione e' unica: basta confrontare i membri
    return a.numerator() == b.numerator() && a.denominator() == b.denominator();
}

bool operator!=(const Rational& a, const Rational& b) { return !(a == b); }

bool operator<(const Rational& a, const Rational& b)
{
    // a/b < c/d  <=>  a*d < c*b, valido perche' i denominatori sono positivi; long long contro l'overflow
    return static_cast<long long>(a.numerator()) * b.denominator()
         < static_cast<long long>(b.numerator()) * a.denominator();
}

bool operator>(const Rational& a, const Rational& b) { return b < a; }

std::ostream& operator<<(std::ostream& os, const Rational& r)
{
    return os << r.numerator() << '/' << r.denominator();
}

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

int main()
{
    Rational a;                       // default: 0/1
    Rational b(5);                    // intero: 5/1
    Rational c(3, 4);
    Rational d(-6, 8);                // ridotta: -3/4
    Rational e(2, -4);                // il segno passa al numeratore: -1/2
    cout << "a = " << a << ", b = " << b << ", c = " << c << ", d = " << d << ", e = " << e << '\n';

    cout << "c + d = " << c + d << '\n';
    cout << "c - d = " << c - d << '\n';
    cout << "c * d = " << c * d << '\n';
    cout << "c / d = " << c / d << '\n';
    cout << "c / e = " << c / e << '\n';          // il divisore e' negativo
    cout << "c + 1 = " << c + 1 << " e 1 + c = " << 1 + c << '\n';   // entrambi gli ordini

    Rational f = c;                   // costruttore di copia (generato)
    f = e;                            // assegnamento
    cout << "f = " << f << '\n';

    cout << "c == Rational(6, 8): " << (c == Rational(6, 8)) << '\n';
    cout << "c != d: " << (c != d) << '\n';
    cout << "c > d: " << (c > d) << ", c < d: " << (c < d) << ", c < b: " << (c < b) << '\n';
    cout << "c.to_double() = " << c.to_double() << '\n';
    cout << "1/3 come double: " << Rational(1, 3).to_double() << '\n';

    try {
        Rational x(1, 0);
        cout << x << '\n';
    }
    catch (Rational::DivisionByZero) {
        cout << "Rational(1, 0): denominatore nullo\n";
    }
    try {
        cout << c / a << '\n';
    }
    catch (Rational::DivisionByZero) {
        cout << "c / a: divisione per zero\n";
    }
    return 0;
}

Si compila con g++ -o prog main.cpp rational.cpp. Uscita (il programma usa try/catch, che in WebAssembly non funzionano: l'uscita è ricavata a mano e confermata eseguendo una copia in cui throw stampa e termina):

a = 0/1, b = 5/1, c = 3/4, d = -3/4, e = -1/2
c + d = 0/1
c - d = 3/2
c * d = -9/16
c / d = -1/1
c / e = -3/2
c + 1 = 7/4 e 1 + c = 7/4
f = -1/2
c == Rational(6, 8): 1
c != d: 1
c > d: 1, c < d: 0, c < b: 1
c.to_double() = 0.75
1/3 come double: 0.333333
Rational(1, 0): denominatore nullo
c / a: divisione per zero

Controlli dalla tabella delle uscite: $-6/8$ diventa $-3/4$ e $2/-4$ diventa $-1/2$ (invarianti rispettati); $\frac34 + (-\frac34) = 0/1$; $\frac34 - (-\frac34) = \frac32$; $\frac34 \cdot (-\frac34) = -\frac9{16}$; $\frac34 \div (-\frac34) = -1/1$; $\frac34 \div (-\frac12) = -\frac32$ (divisore negativo gestito); c + 1 e 1 + c danno entrambi $\frac74$.

Rational + int contro int + Rational

Con la funzione membro, l'operando di sinistra è l'oggetto stesso (this): Rational::operator+(const Rational& b) const permette r + s e, grazie alla conversione implicita del costruttore Rat(int), anche r + 1 (diventa r.operator+(Rat(1))). Ma 1 + r non compila: a sinistra c'è un int, e un int non ha membri.

#include <iostream>
using namespace std;

// Versione minima di Rational, con le somme come FUNZIONI MEMBRO
class Rat {
public:
    Rat(int n = 0, int d = 1) : num{n}, den{d} {}           // il costruttore a un argomento e' implicito
    Rat operator+(const Rat& b) const { return Rat(num * b.den + b.num * den, den * b.den); }
    int num, den;
};

int main()
{
    Rat r(1, 2), s(1, 3);
    Rat t = r + s;                   // r.operator+(s): ok
    Rat u = r + 1;                   // r.operator+(Rat(1)): ok, l'argomento 1 e' convertito
    cout << t.num << '/' << t.den << ' ' << u.num << '/' << u.den << '\n';
    // Rat v = 1 + r;                // ERRORE: a sinistra c'e' un int, non esiste (int).operator+
    return 0;
}

5/6 3/2

error: invalid operands to binary expression ('int' and 'Rat')      (con Rat v = 1 + r;)

Con una helper function Rat operator+(const Rat& a, const Rat& b) il compilatore può convertire entrambi gli argomenti, quindi funzionano r + s, r + 1 e 1 + r.

#include <iostream>
using namespace std;

// Stessa classe, con la somma come HELPER FUNCTION
struct Rat {
    Rat(int n = 0, int d = 1) : num{n}, den{d} {}
    int num, den;
};

Rat operator+(const Rat& a, const Rat& b) { return Rat(a.num * b.den + b.num * a.den, a.den * b.den); }

int main()
{
    Rat r(1, 2), s(1, 3);
    Rat t = r + s;
    Rat u = r + 1;                   // operator+(r, Rat(1))
    Rat v = 1 + r;                   // operator+(Rat(1), r): ora funziona
    cout << t.num << '/' << t.den << ' ' << u.num << '/' << u.den << ' ' << v.num << '/' << v.den << '\n';
    return 0;
}

5/6 3/2 3/2

Quindi: con un unico overload (const Rational&, const Rational&) e il costruttore Rational(int) non esplicito non servono overload separati per gli int. Scrivendo anche operator+(const Rational&, int) in versione membro (Rational::operator+(int)) si ottiene Rational + int ma non int + Rational; per l'altro ordine serve per forza una helper function operator+(int, const Rational&). Per questo la guida di stile Google raccomanda: prefer to define non-modifying binary operators as non-member functions, per non avere un a < b che compila mentre b < a no.

Tipi restituiti.

La soluzione del corso: errori trovati

Il corso pubblica una soluzione del laboratorio 2 (cartella lab2 con include/rational.h, src/rational.cpp, src/main.cpp, CMakeLists.txt). Compilata e provata, ha tre problemi.

1. La normalizzazione non sposta il segno al numeratore. Il commento in normalize() dice che sposta il negativo al numeratore. In realtà divide numeratore e denominatore per Gcd(numerator_, denominator_), e Gcd è l'algoritmo di Euclide con %, che in C++ ha il segno del dividendo: il risultato può essere negativo. Dividere per un MCD negativo inverte entrambi i segni, quindi un denominatore può rimanere negativo:

I valori numerici sono giusti, ma la forma non è coerente: -1/2 esce come 1/-2 mentre -5/8 esce come -5/8 (dipende dal segno che l'algoritmo di Euclide dà all'MCD), e il denominatore dichiarato positivo non lo è. Qualunque codice che assuma $den > 0$ sbaglia: per esempio il confronto < per prodotto incrociato dà il risultato opposto con un denominatore negativo. La correzione è quella di questa soluzione: prima si sistema il segno (if (den_ < 0) { num_ = -num_; den_ = -den_; }), poi si divide per l'MCD del valore assoluto.

2. Lcm può essere negativo. Dipende dallo stesso Gcd: Lcm(-7, 11) dà $-77$ e Lcm(-4, 6) dà $-12$, mentre Lcm(7, -11) dà $+77$ (il segno dipende dall'ordine degli argomenti).

3. L'operatore di conversione operator double() rende ambigue Rational + int e Rational == int. La classe ha sia il costruttore implicito Rational(int) sia operator double() implicito. Per r + 1 il compilatore ha due strade: convertire 1 in Rational (e usare operator+(Rational, Rational)) oppure convertire r in double (e usare la somma built-in). Nessuna è migliore: errore.

error: use of overloaded operator '+' is ambiguous (with operand types 'Rational' and 'int')
error: use of overloaded operator '==' is ambiguous (with operand types 'Rational' and 'int')

Per questo qui la conversione è solo to_double(); se si vuole la conversione per cast, explicit operator double() const.

Aspetti buoni della soluzione ufficiale, ripresi qui: un solo costruttore con argomenti di default; le helper function per i binari; static constexpr per i default; accessori numerator() e denominator() const. Il passaggio per copia dei Rational negli operatori (due int) è lecito; qui si preferisce const Rational& per uniformità con le classi più grandi, senza differenze pratiche.

Limiti comuni. Le operazioni su int possono andare in overflow con numeratori e denominatori grandi: la versione robusta ridurrebbe i fattori comuni prima di moltiplicare, o userebbe long long.