Programmazione C++: mappe

Puntate precedenti: I vettori, ancora sui vettori, Liste e iteratori.

Oggi analizzo un’altro contenitore della libreria standard del C++, molto usato e anche parecchio criticato: la mappa associativa. Si tratta di un contenitore un po’ particolare, perché permette di associare un “valore” a una “chiave”. In pratica, è come se potessimo indirizzare un vettore con una valore qualsiasi invece che con un indice numerico. L’esempio classico è il seguente:

#include <map>
#include <iostream>
#include <string>

using namespace std;

int main()
{
    map<string, int> eta_persona;
    eta_persona["Giuseppe"] = 41;

    pair<string, int> elem1 = {"Giovanni", 35};
    pair<string, int> elem2 = {"Juhan", 21};
    
    eta_persona.insert(elem1);
    eta_persona.insert(elem2);

    cout << "Elem1.first  = " << elem1.first << endl;
    cout << "Elem2.second = " << elem1.second << endl;

    cout << "Eta' di Giuseppe: " << eta_persona["Giuseppe"] << endl;

    cout << "Stampa tutte le eta': " << endl;
    for (auto i : eta_persona) 
        cout << "Eta' " <<  i.first << " = " << i.second << endl;    
}

Alla linea 9 dichiariamo il nostro contenitore e diciamo che associerà numeri interi a stringhe. Nell’esempio, infatti, cerchiamo di memorizzare l’età di un insieme di persone. La chiave è la stringa, ed è quella che utilizzeremo per fare le ricerche nel contenitore; il valore da cercare è l’intero.

Alla linea 10 facciamo subito vedere un esempio di assegnamento: alla chiave “Giuseppe” viene assegnato il valore 41 (e già, sto diventando vecchio…).

Ma esattamente, come vengono memorizzati gli elementi all’interno del contenitore? Gli elementi dentro il contenitore sono coppie (chiave, valore), e una coppia in C++ ha tipo std::pair. Alla linee 12 e 13 prepariamo due coppie di valori (vedete come è giovane Juhan, invece? ), e alla linee 15 e 16 li inseriamo nel contenitore. Una pair non è altro che una struttura con due campi: il primo campo si chiama first e corrisponde alla chiave; il secondo campo si chiama (sorpresa!) second e corrisponde al valore. Alle linee 18 e 19 stampiamo i due elementi a video.

Naturalmente, per stampare un elemento del contenitore possiamo anche utilizzare la notazione con le parentesi quadre, come alla linea 21.

Infine, se vogliamo scorrere e stampare tutti gli elementi della mappa, possiamo usare gli iteratori, esattamente come nel vettore e nella lista. Solo che stavolta, un iteratore punta a una coppia. Alle linee 24-25 stampiamo tutti gli elementi della mappa con un ciclo for.

Le persone abituate al vecchio C++ si stupiranno della sintassi: che sono quei due punti? Chi sa programmare in Python invece ritrova una vecchia conoscenza. Il nuovo ciclo for à la Python è disponibile nel nuovo standard ed è parecchio comodo, soprattutto se combinato con la nuova parola chiave auto. Vediamo di spiegarci: il C++ è un linguaggio fortemente tipato (a differenza del Python) e quindi vuole che si dichiarino i tipi di tutte le variabili. La variabile i avrebbe tipo

std::pair<string, int> i;

che però è lungo da scrivere (ed anche noioso). Non solo: il tipo è automaticamente ottenibile dal contenitore che sta a destra dei due punti: se voglio esplorare una map, allora sappiamo già che gli elementi ivi contenuti saranno pair. E allora, perché non lasciare che sia il compilatore a ricavarsi automaticamente il tipo? Questa tecnica è simile a quello che succede in Haskell, che è un linguaggio fortemente tipato, ma dove la dichiarazione dei tipi è superflua, tanto ci pensa il compilatore a ricavarseli automaticamente.

Ok, fin qui tutto facile. Compilate con il solito “g++ -std=c++0x”, otterrete l’eseguibile che potete lanciare, ottenendo questo risultato:

Elem1.first  = Giovanni
Elem2.second = 35
Eta' di Giuseppe: 41
Eta' di Eleonora: 0
Stampa tutte le eta': 
Eta' Eleonora = 0
Eta' Giovanni = 35
Eta' Giuseppe = 41
Eta' Juhan = 21

Uno dei problemi della map è però proprio la sua facilità d’uso, in particolare la notazione con le parentesi quadre. Che succede se ad esempio vogliamo sapere l’età di Eleonora? ecco il programmino:

#include <map>
#include <iostream>
#include <string>

using namespace std;

int main()
{
    map<string, int> eta_persona;
    eta_persona["Giuseppe"] = 41;

    pair<string, int> elem1 = {"Giovanni", 35};
    pair<string, int> elem2 = {"Juhan", 21};
    eta_persona.insert(elem1);
    eta_persona.insert(elem2);

    cout << "Eta' di Giuseppe: " << eta_persona["Giuseppe"] << endl;
    // Attenzione!!
    cout << "Eta' di Eleonora: " << eta_persona["Eleonora"] << endl;
    cout << "Stampa tutte le eta': " << endl;
    for (auto i : eta_persona) 
        cout << "Eta' " <<  i.first << " = " << i.second << endl;    
}

E l’output è questo:

Elem1.first  = Giovanni
Elem2.second = 35
Eta' di Giuseppe: 41
Eta' di Eleonora: 0
Stampa tutte le eta': 
Eta' Eleonora = 0
Eta' Giovanni = 35
Eta' Giuseppe = 41
Eta' Juhan = 21

Ops, l’elemento (“Eleonora”, 0) è stato inserito nella mappa, anche se ho acceduto in lettura! Che è successo?

È successo che i progettisti della libreria si sono trovati con un problema. Volevano fornire la possibilità di accedere agli elementi dell’array con la parentesi quadra, perché faceva “figo”; ma come comunicare il fatto che l’elemento non era presente? L’operazione di accesso non può restituire un valore di errore particolare (come -1) perché proprio quel valore potrebbe essere un numero valido nell’applicazione. Una soluzione poteva essere quella di lanciare un’eccezione, ma il codice si sarebbe complicato molto, e soprattutto, i progettisti volevano tener fuori dalle balle il meccanismo delle eccezioni per quanto possibile. Quindi hanno deciso per una soluzione un po’ sporca: se l’elemento non c’è lo aggiungiamo con un valore di default (nel caso dell’intero, 0). Ed ecco che, semplicemente cercando una chiave dentro la mappa, un nuovo elemento viene magicamente aggiunto.
Purtroppo, questo comportamento è tutt’altro che intuitivo, e se non lo sapete rischiate di finire nei casini.

Per sapere se un elemento esiste all’interno della mappa, senza rischiare di aggiungerlo, dovete utilizzare la funzione find() che vi restituisce un iteratore all’elemento trovato (se esiste), oppure alla fine del contenitore (se non esiste). Ecco il codice corretto:

#include <map>
#include <iostream>
#include <string>

using namespace std;

int main()
{
    map<string, int> eta_persona;
    eta_persona["Giuseppe"] = 41;

    pair<string, int> elem1 = {"Giovanni", 35};
    pair<string, int> elem2 = {"Juhan", 21};
    eta_persona.insert(elem1);
    eta_persona.insert(elem2);
    cout << "Eta' di Giuseppe: " << eta_persona["Giuseppe"] << endl;    

    auto iter = eta_persona.find("Eleonora");
    if (iter != eta_persona.end()) 
        cout <<"L'età di Eleonora è: " << iter->second << ekdl;
    else cout << "Eleonora non è stat ancora inserita" << endl;
}

Notate ancora una volta l’uso di auto per dichiarare l’iteratore. Senza di auto, avrei dovuto scrivere

map<string, int>::iterator iter = eta_persona.find("Eleonora");

Meglio con auto, no?

Se lanciate il programmino, ottenete:

Eta' di Giuseppe: 41
Eleonora non è stata ancora inserita

Tutto a posto, dunque.

Vediamo un po’, e se volessi utilizzare la funzione print() scritta l’altra volta per stampare tutti gli elementi di una mappa? Eccola:

#include <map>
#include <iostream>
#include <string>

using namespace std;

template<class Iter>
void print(Iter a, Iter b)
{
    cout << "[";
    for (Iter p=a; p!=b; ++p) cout << *p << ", ";
    cout << "]" << endl;
}

int main()
{
    map<string, int> eta_persona;

    eta_persona["Giuseppe"] = 41;
    pair<string, int> elem1 = {"Giovanni", 35};
    pair<string, int> elem2 = {"Juhan", 21};    
    eta_persona.insert(elem1);
    eta_persona.insert(elem2);
    cout << "Eta' di Giuseppe: " << eta_persona["Giuseppe"] << endl;

    cout << "Stampa tutte le eta': " << endl;
    print(eta_persona.begin(), eta_persona.end());
}

Purtroppo, così non funziona, il gcc vi da questo errore (quasi) incomprensibile:

maps2.cpp: In function ‘void print(Iter, Iter) [with Iter = std::_Rb_tree_iterator<std::pair<const std::basic_string, int> >]’:
maps2.cpp:27:49:   instantiated from here
maps2.cpp:11:31: error: cannot bind ‘std::ostream {aka std::basic_ostream}’ lvalue to ‘std::basic_ostream&&’
/usr/include/c++/4.6/ostream:581:5: error:   initializing argument 1 of ‘std::basic_ostream& std::operator<<(std::basic_ostream&&, const _Tp&) [with _CharT = char, _Traits = std::char_traits, _Tp = std::pair<const std::basic_string, int>]’

(Si lo so, è brutto, ma ora ve lo spiego io).
In pratica, alla linea 11 stiamo cerando di stampare una coppia (l’elemento puntato da p, che è un iteratore alla mappa), e il C++ non sa come stamparla. La funzione di stampa (sarebbe quell’operatore strano, <<) non sa come trattare le coppie, e quindi si ferma dando errore di compilazione.

Niente panico! Se il C++ non sa fare una cosa da se’, basta spiegargliela per bene. Non sai stampare una pair? Te lo dico io come si fa, aggiungendo una funzione in più:

template<class F, class S>
std::ostream& operator<<(std::ostream &out, 
                         const std::pair<F,S> &elem)
{
    out << "(" << elem.first << ", " << elem.second << ")";
    return out;
}

Questo è il famigerato overload degli operatori. In pratica, l’operatore << non è altro che una funzione, il cui nome è operator<<, e prende due argomenti, di cui il primo è uno stream di uscita (ad esempio cout, ma anche un qualsiasi file), il secondo è l’oggetto da stampare, nel nostro caso una qualunque coppia di elementi qualsiasi, per esempio di tipo generico F e S. Poiché una funzione così non esiste, la scriviamo noi. E gli diciamo che deve stampare per prima cosa una parentesi tonda aperta, seguita dal primo elemento della coppia, dalla virgola, dal secondo elemento della coppia, e infine dalla parentesi tonda chiusa. Infine, ritorniamo lo stream come risultato, in maniera che si possa fare una concatenazione, per esempio con endl.

Chiaro? No? Non importa, sarà chiaro con degli altri esempi che faremo più avanti (spero). Ecco il programma finale:

#include <map>
#include <iostream>
#include <string>

using namespace std;

template<class F, class S>
std::ostream& operator<<(std::ostream &out, 
                         const std::pair<F,S> &elem)
{
    out << "(" << elem.first << ", " << elem.second << ")";
    return out;
}

template<class Iter>
void print(Iter a, Iter b)
{
    cout << "[";
    for (Iter p=a; p!=b; ++p) cout << (*p) << ", ";
    cout << "]" << endl;
}


int main()
{
    map<string, int> eta_persona;

    eta_persona["Giuseppe"] = 41;
    pair<string, int> elem1 = {"Giovanni", 35};
    pair<string, int> elem2 = {"Juhan", 21};    
    eta_persona.insert(elem1);
    eta_persona.insert(elem2);
    cout << "Eta' di Giuseppe: " << eta_persona["Giuseppe"] << endl;

    cout << "Stampa tutte le eta': " << endl;
    print(eta_persona.begin(), eta_persona.end());
}

Prima di chiudere, alcune considerazione sull’efficienza.
La mappa è implementata internamente come un albero binario di ricerca, per cui ogni accesso prende un tempo proporzionale al logaritmo in base due del numero di elementi presenti. Anche per l’inserzione è lo stesso, sempre tempo logaritmico. Dato che l’albero binario è già ordinato, non ha senso ordinare una mappa; il requisito fondamentale, però, è che esista un ordinamento per il tipo che rappresenta la chiave. Se la chiave è una stringa, come nei nostri esempi, l’ordinamento di default è quello alfabetico. E’ però possibile sia cambiare l’ordinamento di default, sia impostare un ordinamento di default per una vostra classe specifica. Ma questo lo vedremo la prossima volta, che adesso si è fatto tardi!

Buon luglio e accendete i condizionatori che i PC soffrono al caldo!

About these ads