Esercizio - Rubrica di contatti con list e sort (primo appello 2023-24, programmazione)

Esame

In questa pagina 3

Testo (60 minuti, su carta). Progettare e implementare la classe Contact per la gestione dei contatti di una rubrica. Contact deve contenere i membri first_name (std::string), last_name (std::string), address (std::string), telephone (int). Fornire a Contact le funzioni membro necessarie per la creazione di un nuovo contatto, la modifica e l'accesso a ciascun dato membro e la stampa di Contact su std::ostream tramite overloading dell'operatore <<. Creare un programma che popoli un oggetto AddressBook di tipo std::list con 10 elementi Contact. Fare in modo che sia possibile utilizzare l'algoritmo STL std::sort per ordinare tale lista secondo i criteri: per last_name e per telephone.

Teoria: C++ - classi, membri e invarianti, C++ - enumerazioni e overloading degli operatori, STL - algoritmi, predicati e 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 →, STL - sequenze, iteratori e container (vector, list, string).

1. Lettura del testo

richiesta	scelta
quattro membri con tipi dati	`private`: i dati non si toccano dall'esterno
creazione	un costruttore con i quattro argomenti (`const std::string&` per non copiare inutilmente)
accesso e modifica a ciascun dato	quattro funzioni di lettura (`const`) e quattro `set_...`
stampa su `ostream` con `<<`	funzione libera `operator<<(std::ostream&, const Contact&)` che restituisce lo stream, così `cout << a << b` si concatena
10 contatti in una `std::list`	`list<Contact>`; `Contact` non ha costruttore di default, quindi si usa `push_back(Contact{...})`
"fare in modo che si possa usare `std::sort`... per `last_name` e per `telephone`"	due criteri di confronto: function object `ByLastName` e `ByTelephone` (o lambda)

Nessuna invariante da proteggere (ogni nome, indirizzo e numero è ammissibile): non servono controlli e le operazioni di copia generate dal compilatore sono corrette (regola dello zero).

Il trabocchetto: `std::sort` su una `list`

std::sort richiede iteratori random access (STL - algoritmi, predicati e 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 →): list ha iteratori bidirezionali, quindi std::sort(AddressBook.begin(), AddressBook.end(), ByLastName()) non compila (errore dentro l'implementazione: invalid operands to binary expression ('std::__list_iterator<int, void *>' ...), perché sort usa it1 - it2 e simili). Il testo chiede di "poter usare std::sort" sulla lista: le soluzioni valide sono due.

usare la funzione membro list::sort(criterio), che accetta lo stesso function object (ordina riagganciando i nodi, senza copiare gli elementi);
copiare la lista in un vector<Contact> e applicare davvero std::sort.

Il programma mostra entrambe. In un compito su carta conviene scrivere la prima, dire la ragione, e aggiungere la seconda se resta tempo.

2. Il codice

contact/include/contact.hcpp

#ifndef CONTACT_H
#define CONTACT_H

#include <iosfwd>
#include <string>

// Contatto di una rubrica. Nessun invariante particolare: i quattro dati sono liberi.
class Contact {
public:
    Contact(const std::string& first_name, const std::string& last_name,
            const std::string& address, int telephone);

    // accesso in lettura (const) e modifica (set_...) a ciascun dato membro
    const std::string& first_name() const { return first_name_; }
    const std::string& last_name() const { return last_name_; }
    const std::string& address() const { return address_; }
    int telephone() const { return telephone_; }
    void set_first_name(const std::string& v) { first_name_ = v; }
    void set_last_name(const std::string& v) { last_name_ = v; }
    void set_address(const std::string& v) { address_ = v; }
    void set_telephone(int v) { telephone_ = v; }

private:
    std::string first_name_;
    std::string last_name_;
    std::string address_;
    int telephone_;      // int come da testo (nota: un numero italiano di 10 cifre supera INT_MAX)
};

std::ostream& operator<<(std::ostream& os, const Contact& c);

// Criteri di ordinamento per std::sort / list::sort: il primo restituisce true se a viene prima di b.
struct ByLastName {
    bool operator()(const Contact& a, const Contact& b) const { return a.last_name() < b.last_name(); }
};
struct ByTelephone {
    bool operator()(const Contact& a, const Contact& b) const { return a.telephone() < b.telephone(); }
};

#endif // CONTACT_H

contact/src/contact.cppcpp

#include "contact.h"
#include <ostream>

Contact::Contact(const std::string& first_name, const std::string& last_name,
                 const std::string& address, int telephone)
    : first_name_{first_name}, last_name_{last_name}, address_{address}, telephone_{telephone} {}

std::ostream& operator<<(std::ostream& os, const Contact& c)
{
    return os << c.last_name() << ' ' << c.first_name() << ", " << c.address() << ", tel. " << c.telephone();
}

contact/src/main.cppcpp

#include <algorithm>
#include <iostream>
#include <list>
#include <vector>
#include "contact.h"

namespace {
void print(const char* title, const std::list<Contact>& book)
{
    std::cout << title << '\n';
    for (const Contact& c : book) std::cout << "  " << c << '\n';
}
}

int main()
{
    std::list<Contact> AddressBook;                       // 10 contatti
    AddressBook.push_back(Contact{"Marta", "Rossi", "via Roma 1", 3401234});
    AddressBook.push_back(Contact{"Luca", "Bianchi", "via Dante 22", 3407777});
    AddressBook.push_back(Contact{"Anna", "Verdi", "corso Italia 5", 3400001});
    AddressBook.push_back(Contact{"Paolo", "Neri", "piazza Duomo 3", 3409999});
    AddressBook.push_back(Contact{"Sara", "Conti", "via Mazzini 8", 3405555});
    AddressBook.push_back(Contact{"Gianni", "Esposito", "via Napoli 12", 3402222});
    AddressBook.push_back(Contact{"Elena", "Ferrari", "via Torino 7", 3406666});
    AddressBook.push_back(Contact{"Davide", "Greco", "via Milano 40", 3403333});
    AddressBook.push_back(Contact{"Chiara", "Bruno", "via Verdi 9", 3408888});
    AddressBook.push_back(Contact{"Fabio", "Marino", "via Garibaldi 2", 3404444});
    print("originale", AddressBook);

    // std::sort NON si puo' usare direttamente su una std::list: vuole iteratori random access.
    // std::sort(AddressBook.begin(), AddressBook.end(), ByLastName());          // errore di compilazione

    // 1) la lista ha il proprio ordinamento, che accetta lo stesso criterio
    AddressBook.sort(ByLastName());
    print("list::sort per last_name", AddressBook);
    AddressBook.sort(ByTelephone());
    print("list::sort per telephone", AddressBook);

    // 2) oppure si copia in un vector e si usa davvero std::sort (con function object o lambda)
    std::vector<Contact> v(AddressBook.begin(), AddressBook.end());
    std::sort(v.begin(), v.end(), ByLastName());
    std::cout << "std::sort su vector per last_name, primo e ultimo: " << v.front().last_name()
              << ", " << v.back().last_name() << '\n';
    std::sort(v.begin(), v.end(), [](const Contact& a, const Contact& b) { return a.telephone() < b.telephone(); });
    std::cout << "std::sort su vector per telephone, primo e ultimo: " << v.front().telephone()
              << ", " << v.back().telephone() << '\n';

    // modifica tramite le funzioni membro
    Contact& first = v.front();
    first.set_address("via Nuova 99");
    first.set_telephone(3400000);
    std::cout << first << '\n';
}

Uscita eseguita (compilato anche per Linux con -Wall -Wextra senza avvisi):

originale
  Rossi Marta, via Roma 1, tel. 3401234
  Bianchi Luca, via Dante 22, tel. 3407777
  ... (dieci contatti nell'ordine di inserimento)
list::sort per last_name
  Bianchi Luca, via Dante 22, tel. 3407777
  Bruno Chiara, via Verdi 9, tel. 3408888
  Conti Sara, via Mazzini 8, tel. 3405555
  Esposito Gianni, via Napoli 12, tel. 3402222
  Ferrari Elena, via Torino 7, tel. 3406666
  Greco Davide, via Milano 40, tel. 3403333
  Marino Fabio, via Garibaldi 2, tel. 3404444
  Neri Paolo, piazza Duomo 3, tel. 3409999
  Rossi Marta, via Roma 1, tel. 3401234
  Verdi Anna, corso Italia 5, tel. 3400001
list::sort per telephone
  Verdi Anna, corso Italia 5, tel. 3400001
  Rossi Marta, via Roma 1, tel. 3401234
  Esposito Gianni, via Napoli 12, tel. 3402222
  Greco Davide, via Milano 40, tel. 3403333
  Marino Fabio, via Garibaldi 2, tel. 3404444
  Conti Sara, via Mazzini 8, tel. 3405555
  Ferrari Elena, via Torino 7, tel. 3406666
  Bianchi Luca, via Dante 22, tel. 3407777
  Bruno Chiara, via Verdi 9, tel. 3408888
  Neri Paolo, piazza Duomo 3, tel. 3409999
std::sort su vector per last_name, primo e ultimo: Bianchi, Verdi
std::sort su vector per telephone, primo e ultimo: 3400001, 3409999
Verdi Anna, via Nuova 99, tel. 3400000

Punti da commentare:

L'ordinamento per cognome è lessicografico sulla std::string (maiuscole prima delle minuscole, a parità di cognome l'ordine relativo è non garantito per std::sort; list::sort è invece stabile).
I criteri restituiscono true se a viene strettamente prima di b (mai <=): è il requisito Compare.
ByLastName e ByTelephone sono struct con operator() const: function object senza stato, quindi inline e copiabili a costo zero.
Il telephone è un int come da testo: un numero di cellulare italiano di 10 cifre supera il massimo di un int a 32 bit (circa 2,1 miliardi); in un progetto vero si userebbe una std::string (il prefisso +39 e gli zeri iniziali non sono numeri). I contatti dell'esempio hanno numeri di 7 cifre per rientrare.
Le funzioni di modifica set_... e quelle di lettura sono nell'header perché brevi (una riga): regola di stile del corso.
Il codice è diviso come richiesto negli esami "indicare la divisione in file": contact.h (interfaccia, include guard, i due criteri), contact.cpp (costruttore e operator<<), main.cpp.

3. Errori da evitare

std::sort(lista.begin(), lista.end(), ...) direttamente sulla lista.
Un criterio con <=, o che confronta con ==.
Dati membro pubblici o friend per far funzionare operator<<.
Implementare operator<< come funzione membro (avrebbe lo stream come operando di destra).
operator<< che stampa con std::cout invece che sullo ostream ricevuto, o che non restituisce lo stream.
Passare Contact per valore nei criteri (copia di quattro dati a ogni confronto).

Versione ripasso

Testo: classe Contact con first_name, last_name, address (std::string) e telephone (int): costruzione, modifica e accesso, operator<<; std::list<Contact> con 10 elementi ordinabile con std::sort per last_name e per telephone. Teoria: STL - algoritmi, predicati e 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 →, STL - sequenze, iteratori e container (vector, list, string).
Scelte: dati private; costruttore con const std::string&; lettura const, set_...; operator<< libero che restituisce lo stream; regola dello zero.
Trabocchetto: std::sort vuole iteratori random access, list ha iteratori bidirezionali: non compila. Soluzioni: list::sort(criterio) (stabile) oppure copia in vector e std::sort.
Criteri: function object ByLastName, ByTelephone (o lambda): operator()(const Contact&, const Contact&) const restituisce true se a precede strettamente b.