Diccionaris: map i set

Per què un diccionari?

Vols guardar la nota de cada estudiant i, després, consultar la nota d’un estudiant pel seu nom. Amb una list de parells (nom, nota), cada consulta és una cerca: has de recórrer la llista fins que el trobes. Amb 50.000 estudiants i moltes consultes, és lent.

Un diccionari de paper no funciona així: no el llegeixes des del principi fins que trobes la paraula. Com que està ordenat, obres per la meitat i saps cap a quina banda has d’anar. Això és el que fa un map: guarda parells clau → valor, ordenats per la clau, i troba qualsevol clau en temps logarítmic.

La idea

Un map<string, int> amb notes es pot imaginar així: una fila de parells, sempre ordenada alfabèticament pel nom.

• Les claus són úniques: no hi pot haver dues vegades «Pol».
• Els valors es poden repetir: Martí i Pol tenen tots dos un 7.
• L’ordre és el de les claus, no el d’inserció. Si afegeixes «Carla», va entre Berta i Martí.
• Les claus han de tenir l’operador < (per poder-les ordenar). int, string, char… ja el tenen.

Com és per dins

Per dins, un map no és una fila de nodes com la llista: és un arbre de cerca equilibrat (els veuràs a EDA).
Cada node té una fletxa cap a les claus més petites i una altra cap a les més grans.
Per buscar una clau, no cal passar per totes: a cada node descartes la meitat que no et toca.
Per això troba les claus en $\Theta(\log n)$: amb un milió de claus, uns 20 passos.

El que sí que és com una llista és el recorregut: l’iterador passa per les claus en ordre, de la més petita a la més gran.
Per a l’iterador, el següent d’una clau és la clau que va just després en ordre, i després de l’última hi ha el final, end().

Parells: pair

Abans del map, una peça que fa servir: pair<A, B> guarda dos valors, de tipus possiblement diferents.

pair<string, int> p("Pol", 7);
pair<string, int> q = {"Aina", 9};
cout << p.first << ' ' << p.second;   // Pol 7
p.second = 8;

Dos parells es comparen primer per first i, si són iguals, per second. Cada element d’un map<K, V> és un pair<const K, V>: first és la clau (que no es pot canviar) i second és el valor.

Instruccions bàsiques del map

#include <map>

map<string, int> notes;
notes["Pol"] = 7;              // insereix Pol → 7
notes["Aina"] = 9;             // insereix Aina → 9
notes["Pol"] = 8;              // Pol ja hi era: ara val 8
cout << notes["Aina"];         // 9
cout << notes.size();          // 2

Mira-ho pas a pas. Fixa’t que cada clau nova va al seu lloc en ordre, no al final:

map<string, int> notes;
notes["Pol"] = 7;
notes["Aina"] = 9;
notes["Martí"] = 5;
notes["Pol"] = 8;
notes.insert({"Aina", 3});
auto it = notes.find("Marc");
it = notes.find("Martí");
notes.erase("Aina");

La diferència entre m[k] = v i m.insert({k, v}): si k ja hi és, la primera canvia el valor i la segona no fa res.

Per la mateixa raó, sobre un const map<…>& no pots fer servir m[k] (no compila: podria modificar el map). Fes servir find:

// Pre: cert. Post: retorna la nota de nom, o -1 si no hi és (sense modificar notes).
int nota_de(const map<string, int>& notes, const string& nom) {
    map<string, int>::const_iterator it = notes.find(nom);
    if (it == notes.end()) return -1;
    return it->second;
}

Recórrer un map

Amb iteradors, com una llista. El recorregut va en ordre creixent de clau:

for (map<string, int>::const_iterator it = notes.begin(); it != notes.end(); ++it) {
    cout << it->first << ": " << it->second << endl;
}

it->first és la clau i it->second el valor. Pots canviar el valor (it->second = 10;, amb un iterator no constant), però no la clau: it->first = "Anna"; no compila. Si canviessis la clau, el parell quedaria fora de lloc i el map deixaria d’estar ordenat. Per «canviar» una clau, esborra el parell i insereix-ne un de nou.

Amb el for de rang també funciona: for (const auto& p : notes) cout << p.first << ' ' << p.second;.

Prova totes les instruccions a l’interactiu: cada una que facis queda marcada.
Fixa’t que, faci el que faci, els parells sempre queden en ordre de clau.

Un exemple complet: recompte de vots

Llegeixes els noms dels candidats que han votat uns quants electors i vols saber quants vots té cadascun, en ordre alfabètic, i qui guanya.

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> vots;  // candidat -> nombre de vots
    string nom;
    while (cin >> nom) ++vots[nom];  // si nom no hi és, es crea amb 0 i passa a 1

    // Recorregut en ordre alfabètic de clau
    for (map<string, int>::const_iterator it = vots.begin(); it != vots.end(); ++it) {
        cout << it->first << ": " << it->second << endl;
    }

    // El guanyador: el primer en ordre alfabètic dels que tenen més vots
    map<string, int>::const_iterator millor = vots.begin();
    for (map<string, int>::const_iterator it = vots.begin(); it != vots.end(); ++it) {
        if (it->second > millor->second) millor = it;
    }
    if (millor != vots.end()) cout << "Guanya " << millor->first << endl;
}

Amb l’entrada Pau Laia Pau Marc Laia Pau Joana Laia, escriu:

Joana: 1
Laia: 3
Marc: 1
Pau: 3
Guanya Laia

Aquí ++vots[nom] és exactament el comportament que volem: la primera vegada que surt un nom, es crea amb 0 i passa a 1. Si haguéssim fet servir una llista, cada vot seria una cerca $\Theta(n)$; amb el map, $\Theta(\log n)$. I l’ordre alfabètic surt de franc.

Conjunts: set

Un set<T> és com un map amb només claus: un conjunt de valors sense repetits, guardats en ordre.

#include <set>

set<string> vistos;
vistos.insert("gat");
vistos.insert("ase");
vistos.insert("gat");           // ja hi era: no fa res
cout << vistos.size();          // 2
cout << vistos.count("ase");    // 1
vistos.erase("ase");
for (const string& s : vistos) cout << s << ' ';   // gat

set<string> vistos;
vistos.insert("gat");
vistos.insert("ase");
vistos.insert("gat");
vistos.erase("ase");

Serveix per a preguntes del tipus «ja l’he vist?» o «quants de diferents n’hi ha?».

Instruccions bàsiques del set

Els elements d’un set no es poden modificar a través d’un iterador, per la mateixa raó que les claus d’un map: el conjunt deixaria d’estar ordenat.

Com es recorre

Igual que el map: amb un iterador, de begin() a end(), i surten en ordre creixent.

for (set<int>::iterator it = s.begin(); it != s.end(); ++it) {
    cout << *it << ' ';
}

Errors habituals

Exercicis

map<string, int> m;
m["gat"] = 3;
m["ase"] = 5;
m.insert({"gat", 10});
m["bou"];
cout << m.size() << ' ' << m["gat"] << ' ' << m.count("cabra") << ' ' << m.size() << endl;
for (auto it = m.begin(); it != m.end(); ++it) cout << it->first << '=' << it->second << ' ';
cout << endl;

3 3 0 3
ase=5 bou=0 gat=3

// Pre: nom és a notes. Post: retorna si la nota de nom és >= 5.
bool aprovat(const map<string, int>& notes, const string& nom) {
    return notes[nom] >= 5;
}

bool aprovat(const map<string, int>& notes, const string& nom) {
    return notes.at(nom) >= 5;
}

// Pre: cert. Post: s'han esborrat de m totes les entrades amb valor 0.
void esborra_zeros(map<string, int>& m) {
    map<string, int>::iterator it = m.begin();
    while (it != m.end()) {
        if (it->second == 0) it = m.erase(it);
        else ++it;
    }
}

// Pre: cert.
// Post: retorna un map que associa a cada nota les persones que la tenen,
//       en ordre alfabètic.
map<int, list<string>> per_nota(const map<string, int>& notes) {
    map<int, list<string>> r;
    for (map<string, int>::const_iterator it = notes.begin(); it != notes.end(); ++it) {
        r[it->second].push_back(it->first);  // com que notes va en ordre de nom, cada llista també
    }
    return r;
}

// Pre: cert. Post: retorna els elements que surten a totes dues llistes, sense repetits i ordenats.
set<int> comuns(const list<int>& a, const list<int>& b) {
    set<int> sa(a.begin(), a.end());  // els elements d'a, sense repetits
    set<int> r;
    for (int x : b) {
        if (sa.count(x) == 1) r.insert(x);
    }
    return r;
}