Linguaggio C++ avanzato

Nov 7, 2022

Nell’articolo precedente su C++ abbiamo presentato i tipi di dati supportati da questo linguaggio. Tuttavia, per alcune implementazioni risulta utile utilizzare delle strutture diverse da quelle già esistenti. È frequente implementare algoritmi che sfruttano oggetti matematici che non possono essere rappresentati con i tipi supportati di base da C++, come per esempio i numeri complessi, coppie di valori, vettori, ecc. In generale è utile mantenere insieme a un valore le sue prorietà in un’unica variabile (segno, errori di approssimazione, ecc).

Indice

In questi appunti vengono presentate le struct e le classi: approcci di programmazione supportati da C++ per creare e modificare oggetti informatici.

In seguito viene sviluppato il concetto di pointer e proposto un esempio e l’implementazione delle linked list che ne fanno uso.

Struct

Per questo utilizzo C++ offre le struct: strutture con le quali si possono personalizzare i formati e i tipi di dati di un oggetto.

Implementazione

Creiamo una struttura come segue:

struct struttura { 
    int var1; 
    int var2;
};

e abbiamo modo di utilizzarla per salvare dei valori:

struttura coppia;
coppia.var1 = 3;
coppia.var2 = 5;
oppure:
struttura coopia = {3, 5};

Sullo stesso modello possiamo creare una struttura che gestisca i numeri razionali (frazioni). Siamo quindi in grado di utilizzare la struttura rational all’interno di funzioni. In questo caso scriviamo la funzione somma.

struct rational { 
    int n; 
    int d; //d != 0
};

rational add (rational a, rational b){ 
    rational result; 
    result.n = a.n * b.d + a.d * b.n; 
    result.d = a.d * b.d; 
    return result; 
}

Chiaramente questa implementazione è molto limitata, in quanto:

non tiene conto dell’impossibilità di dividere per 0;
non riduce le frazioni ai minimi termini. Questo significa che due funzioni uguali verrebbero considerate diverse (ad esempio: 2/4 e 1/2);

Malgrado i suoi limiti, essa è comunque in grado di restituire l’idea alla base delle strutture in C++.

Operator overloading: dalle funzioni ai metodi

È anche possibile definire l’operazione della somma in maniera specifica per la struttura rational. In questo modo è possibile definire come la stessa operazione (quella della somma) si comporti per argomenti diversi (che siano numeri razionali, interi, vettori, ecc).

rational operator+ (rational a, rational b) {
    rational result;
    result.n = a.n * b.d + a.d * b.n;
    result.d = a.d * b.d;
    return result; 
}

Questo consente l’utilizzo della infix notation, molto più pratica e veloce:

const rational t = r + s;

Come per la somma è possibile definire operazioni di ogni tipo: per il confronto (==, >, <=, …) o per la stampa e la lettura (>>, <<).

Classi

C++ è un object oriented programming language (OOP), ovvero supporta nativamente la creazione di oggetti con le classi. Pensate a un progetto architettonico su carta con il quale è possibile costruire più case, ognuna con piccole modifiche, come il colore della facciata, il numero di finestre o la presenza di un garage. Le classi sono modelli che contengono variabili (in cui salvare valori e preferenze oggetto per oggetto) e metodi (funzioni specifiche per gli oggetti che operano sugli oggetti della classe).

Core idea delle classi in C++

Subito sopra in livello di complessità alle struct troviamo le classi. Pensate per un utilizzo leggermente diverso, consentono di creare modelli per oggetti informatici che tengano conto di dati e siano in grado di eseguire delle funzioni.

class rational { 
    int n; 
    int d; // d != 0 
};

Riprendiamo l’esempio dei numeri razionali e lo sviluppiamo di seguito con le classi.

Nelle struct tutte le informazioni definite all’interno della struttura sono pubbliche: ovvero, accessibili (con la dot notation) ovunque all’interno di main. Per le classi invece è diverso e di default tutte le informazioni definite al suo interno sono private, a meno che non sia specificato diversamente.

class rational{
    public: 
        int numerator() const {
            return n;
        }
        int denominator() const {
            return d;
        }
    
    private:
        int n;
        int d;
}

n e d non sono accessibili con class_name.n/d, ma si possono ottenere chiamando la funzione rispettiva definita all’interno di public. Queste funzioni ritornano valori che non si possono modificare: per questa ragione sono const.

rational r;
int n = r.numerator();
int d = r.denominator();

Constructor

Il constructor di una classe è un metodo particolare con lo stesso nome della classe. Al posto di eseguire un’operazione con gli oggetti definiti sul modello della classe (si direbbe metodo di una classe), offre la possibilità di creare un nuovo oggetto sul modello della classe in maniera diversa a seconda delle esigenze.

class rational { 
    public:
        rational (int num, int den): n (num), d (den) {
            assert (den != 0);
        }
        rational(int num): n (num), d (1){
            //no assert needed
            //a d è assegnato 1: creiamo un numero naturale
        }
    ...
}
rational r = rational(2, 3); // creiamo un nuovo oggetto sfruttando il primo constructor definito
rational n = rational(5); // qui sfruttiamo il secondo constructor

A seconda delle informazioni fornite quando si chiama il constructor per creare un nuovo oggetto sul modello di una classe (ci si riferisce a questo oggetto come elemento della classe rational) il compiler sceglie il constructor compatibile con la nostra richiesta (function overloading).

Nel caso in cui non venga fornito nessun argomento, è necessario definire un default constructor:

class rational { 
    public:
        rational (int num, int den): n (0), d (1) {
            //numero razionale di default è lo 0
        }
}

Nel caso proposto, stabiliamo arbitrariamente che il valore di un numero razionale sia lo 0.

Pointer

C++ salva i dati in forma binaria all’interno della memoria del nostro computer. In particolare a ogni oggetto è assegnato un indirizzo nella memoria del computer in cui sono salvate le sue informazioni. A seconda dell’oggetto si conosce anche il numero di bit che occupa in memoria (la lunghezza). Un pointer è un oggetto che punta a quell’indirizzo nella memoria del computer; a seconda del tipo può anche conoscere la lunghezza di bit che occupa un oggetto. Consente quindi di raggiungere la posizione di un oggetto, il suo valore, così come di modificarlo e collegarlo ad altri punti nella memoria del computer.

Possiamo quindi inizializzare una variabile e chiedere al pointer di restituire il suo indirizzo:

int a = 10;
int* p = &a;
int A = *p;

* significa che p contiene l’indirizzo di un integer: si dice che p punta ad a:

con * si può anche accedere al valore salvato a un determinato indirizzo.

& è un reference operator, restituisce quindi l’indirizzo a cui si trova a.

Utilizzo dei pointer

Se conosciamo una lista i cui elementi sono compresi tra [begin, end) posizioni nella memoria, possiamo accedere a questi elementi utilizzando i pointer. il vantaggio è quello di evitare un’implementazione con le array, generalmente meno efficiente.

for(int* p = begin; p != end; ++p){
    std::cout << *p;
}

void fill(int* begin, int* end; int value){
    for(int* p = begin; p != end; ++p){
        *p = value;
    }
}
int* A = new int[5]; 
fill(A, A+5, 1);

Allo stesso modo è possibile assegnare a tutti questi elementi un valore specifico chiamando una funzione fill definita come sopra.

A+5 è un’espressione di pointer arithmetic: il compiler riconosce che A punta al primo elemento di una lista e aggiunge quindi per ogni unità il numero di bit corrispondente alla lunghezza degli elementi che contiene. A+1 punta al secondo elemento della lista. A+5 punta alla fine della lista, alla prima posizione in cui non sono più contenuti elementi di A.

Esempio: check for palindromes

Un palindromo è una parola che risulta uguale nei due ordini di lettura (sinistra verso destra e destra verso sinistra). Per esempio ANNA è un palindromo.

bool is_palindrome (const char* begin, const char* end) {
    while (begin < end){
        if (*(begin++) != *(--end)){
            return false;
        }
    }
return true; 
}

dall’esterno verso l’interno verifichiamo che ogni lettera sia uguale a coppia, come a specchio;
non appena due lettere non coincidono la procedura viene interrotta: sicuramente non si tratta di un palindromo;
begin punta al primo elemento della lista, mentre end al primo elemento che non fa parte della lista. Per questa ragione begin++ aumenta di un’unità la posizione del pointer dopo la verifica, mentre –end la diminuisce di uno prima della verifica.

Linked list

Finora l’unico modo che conosciamo per salvare una lista di elementi sono le array. Nelle sezioni precedenti abbiamo visto come i pointer ci aiutano a gestire in maniera più flessibile l’accesso e la modifica dei suoi elementi.

I pointer ci consenteno di non salvare i dati in maniera sequenziale (uno dopo l’altro) come succede con le array, ma anche sparsi all’interno della memoria. Creare nuove liste in questo modo risulta più veloce perché non è necessario liberare nuovo spazio per contenere tutti i dati potenziali della lista che vogliamo creare.

Una linked list è una struttura di dati (data structure) che permette di collegare gli elementi di una lista (rappresentati come nodi con due celle), non affiancandoli uno dopo l’altro nella memoria del computer, ma collegando ogni elemento al successivo: con un pointer che punta all’indirizzo occupato dal nodo successivo. Ogni nodo in una linked list contiene un valore e conosce il nodo successivo cui è collegato:

//struttura che contiene un elemento della lista
struct llnode { 
    int value; //valore contenuto nel nodo
    llnode* next; //nodo successivo
    llnode(int v, llnode* n): value(v), next(n) {} // Defualt constructor 
};

Il primo nodo della lista si chiama head, l’ultimo punta al nullptr (il pointer nullo, senza nessun indirizzo).

Inseriamo ora 3 elementi:

llnode* third = new llnode(2, nullptr);
llnode* second = new llnode(1, third);
llnode* head = new llnode(0, second);

Le linked list:

non hanno una lunghezza fissa;
tengono conto dell’ordine con cui vengono inseriti gli elementi;
non consentono il random access alla posizione i: per raggiungere l’i-esimo elemento della lista bisogna percorrerla tutta dalla head fino a i;
necessita più memoria rispetto a una array: per ogni elemento si salva il suo valore e l’indirizzo del nodo successivo.

Print list

Per stampare tutti gli elementi della lista creiamo una funzione che percorre e recupera i valori dei nodi:

void print_list(llnode* head){
    while(head != nullptr){
        cout << head -> value << " ";
        head = head -> next;
    }
}

Vediamo ancora come aggiungere un elemento in coda e in testa a una linked list.

void insert(llnode ** head, int value){
    llnode* n = new llnode(value, head); //creiamo un nuovo nodo prima di head
    *head = n; //head punta sempre all'elemento successivo
}

void insert(llnode ** head, int value){
    llnode* n = new llnode(value, nullptr);
    //controllare se la ll è vuota
    if(*head -> == nullptr){
        *head = n;
        return:
    }
    
    //raggiungere l'ultimo elemento
    llnode* last = *head;
    while(last -> next != nullptr){
        last = last -> next;
    }
    
    //collegare l'ultimo nodo a quello appena creato
    last -> next = n;
}

Conclusione

Approfonditi questi argomenti il funzionamento di C++ dovrebbe essere più chiaro, anche se non per questo senza più angoli da esplorare. In particolare è consigliato: