STL - container associativi (map e set)

I contenitori sequenziali (STL - sequenze, iteratori e container (vector, list, string)La STL (Standard Template Library) fornisce contenitori (vector, list, map, ...) e algoritmi generici (sort, find, accumulate, ...) tenuti insieme da una interfaccia unificata: la sequenza, un intervallo [begin, end) di elementi gestito tramite iteratori (oggetti che identificano un elemento: * dereferenzia, ++ avanza, == e != confrontano; end è il primo elemento dopo l'ultimo, quindi una sequenza vuota ha begin == end). Gli algoritmi conoscono solo gli iteratori e i contenitori espongono solo iteratori, così i due mondi sono disaccoppiati e cambiare contenitore non cambia l'algoritmo. Un iteratore di lista è una classe annidata con un puntatore al nodo; auto deduce il tipo dell'iteratore. vector (contiguo, [] e at(), insert/erase costosi e che invalidano gli iteratori), string (un vector di char con + e +=), list (nodi concatenati, insert/erase senza spostare gli altri elementi, niente []) e char[] (array C: dimensione fissa, niente iteratori, == confronta i puntatori) a confronto.STL - sequenze, iteratori e container (vector, list, string) →) memorizzano gli elementi in una posizione: per trovare qualcosa bisogna conoscere l'indice o scorrere. I container associativi li organizzano in base a una chiave: dato un valore (la chiave) si arriva all'elemento senza scorrere tutto. Funzionano con gli stessi iteratori e gli stessi algoritmi (STL - algoritmi, predicati e lambdaLa STL ha circa 80 algoritmi generici (header e ) che lavorano su sequenze [first, last) di qualunque contenitore tramite iteratori: find/find_if, count/count_if, sort, copy/copy_if/unique_copy, merge, equal_range, equal, accumulate, inner_product. find cerca un valore e restituisce l'iteratore alla prima occorrenza o end(); find_if verifica un predicato (funzione che restituisce bool) passato come puntatore a funzione, function object (classe con operator()) o lambda expression. Una variabile globale per passare la soglia al predicato è da evitare; il function object la memorizza in un dato membro. Una 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 →).

Le versioni ordinate sono implementate con un albero bilanciato (ricerca, inserimento, rimozione in tempo logaritmico, elementi sempre in ordine di chiave); quelle unordered_ con una tabella hash (tempo medio costante, nessun ordine; sono le strutture dei dizionari e degli insiemi di Python, v. Dizionari e insiemi in PythonADT mappa e insieme; dict con chiavi hashable, accesso, get, iterazione, conteggi e raggruppamenti; set e operazioni insiemistiche; tabelle hash e costo O(1) medio; Counter e defaultdict.Dizionari e insiemi in Python →).

map

map (header <map>) gestisce coppie chiave-valore, è ordinata per chiave ed è ottimizzata per le ricerche dalla chiave: è facile e veloce verificare se una chiave è presente e recuperare il valore associato.

Esempio classico: l'istogramma delle parole di un testo (le slide leggono da cin; qui il testo è in uno istringstream, che si usa allo stesso modo).

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

int main()
{
    // istogramma delle parole di un testo (le slide leggono da cin; qui il testo e' in una stringa)
    istringstream testo{"il gatto e il cane e il topo"};
    map<string, int> words;
    for (string s; testo >> s; )
        ++words[s];                                    // se s non c'e', viene creato con valore 0

    for (const auto& p : words)                        // ordinato per CHIAVE; p e' una pair<const string,int>
        cout << p.first << ": " << p.second << '\n';

    cout << "---- accesso e ricerca\n";
    cout << "words[\"il\"] = " << words["il"] << '\n';
    cout << "size prima: " << words.size() << '\n';
    cout << "words[\"drago\"] = " << words["drago"] << "  (creato con 0)\n";
    cout << "size dopo: " << words.size() << '\n';

    auto it = words.find("cane");                      // find non crea nulla
    if (it != words.end()) cout << "trovato " << it->first << " -> " << it->second << '\n';
    cout << "find(\"mela\") == end: " << (words.find("mela") == words.end()) << '\n';
    cout << "count(\"gatto\") = " << words.count("gatto") << '\n';

    cout << "---- insert ed erase\n";
    auto r = words.insert(make_pair(string{"gatto"}, 100));      // chiave gia' presente
    cout << "insert gatto: inserito=" << r.second << ", valore resta " << r.first->second << '\n';
    words.insert({"zebra", 1});
    words.erase("drago");
    for (const auto& [parola, n] : words) cout << parola << '=' << n << ' ';   // structured binding (C++17)
    cout << '\n';

    cout << "---- at() e unordered_map\n";
    cout << "words.at(\"zebra\") = " << words.at("zebra") << '\n';     // at(chiave assente) lancerebbe out_of_range
    unordered_map<string, int> h{{"uno", 1}, {"due", 2}};            // tabella hash: nessun ordine garantito
    cout << "h[\"due\"] = " << h["due"] << ", size " << h.size() << '\n';
}

Uscita eseguita:

cane: 1
e: 2
gatto: 1
il: 3
topo: 1
---- accesso e ricerca
words["il"] = 3
size prima: 5
words["drago"] = 0  (creato con 0)
size dopo: 6
trovato cane -> 1
find("mela") == end: 1
count("gatto") = 1
---- insert ed erase
insert gatto: inserito=0, valore resta 1
cane=1 e=2 gatto=1 il=3 topo=1 zebra=1
---- at() e unordered_map
words.at("zebra") = 1
h["due"] = 2, size 2

Indicizzare una map

L'elemento cruciale è ++words[s]. L'indicizzazione usa una string e la map fornisce l'int corrispondente. Se la chiave non esiste, operator[] crea un elemento con quella chiave e il valore inizializzato con il costruttore di default del tipo (per int, 0): perciò la prima volta che si incontra una parola il contatore parte da 0 e ++ lo porta a 1. La conseguenza si vede nel programma: words["drago"] aumenta la size da 5 a 6 anche se si voleva solo leggere. Per cercare senza creare si usa find(chiave) (restituisce end() se manca) o count(chiave); at(chiave) restituisce il valore e lancia out_of_range se manca.

pair

Gli elementi di una map sono coppie, gestite come pair<const string, int>: i membri sono first (la chiave, const) e second (il valore). Il ciclo for (const auto& p : words) scorre gli elementi in ordine di chiave; cout << p.first << ": " << p.second. Per creare una coppia: make_pair(chiave, valore) oppure {chiave, valore}. insert restituisce una pair<iterator, bool>: il bool dice se l'inserimento è avvenuto (non avviene se la chiave c'è già: insert gatto: inserito=0). Con C++17 si può anche scrivere for (const auto& [parola, n] : words).

map contro vector

• map mantiene i dati ordinati rispetto alla chiave;
• offre una ricerca molto più veloce a partire dalla chiave, mentre in un vector non ordinato si deve scorrere tutto;
• associa esplicitamente una chiave a un valore (il vector associa un indice, per forza intero e consecutivo).

set

Un set (header <set>) è una map senza i valori: contiene solo chiavi, ordinate. Quindi viene meno la ricerca del valore a partire dalla chiave:

• non c'è operator[];
• non c'è push_back(): è il set a decidere dove inserire l'elemento;
• si gestisce con le operazioni tipiche delle liste, insert() ed erase().

Il set è ordinato, quindi serve una funzione d'ordine per il tipo contenuto, compresi i tipi definiti dall'utente. Per costruire un set di Fruit bisogna definirla (un function object, STL - algoritmi, predicati e lambdaLa STL ha circa 80 algoritmi generici (header e ) che lavorano su sequenze [first, last) di qualunque contenitore tramite iteratori: find/find_if, count/count_if, sort, copy/copy_if/unique_copy, merge, equal_range, equal, accumulate, inner_product. find cerca un valore e restituisce l'iteratore alla prima occorrenza o end(); find_if verifica un predicato (funzione che restituisce bool) passato come puntatore a funzione, function object (classe con operator()) o lambda expression. Una variabile globale per passare la soglia al predicato è da evitare; il function object la memorizza in un dato membro. Una 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 →) e passarla come secondo argomento del template:

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

struct Fruit {
    string name;
    int count;
    double unit_price;
};

struct Fruit_order {                                   // funzione d'ordine: confronta SOLO il nome
    bool operator()(const Fruit& a, const Fruit& b) const { return a.name < b.name; }
};

ostream& operator<<(ostream& os, const Fruit& f)
{
    return os << f.name << " x" << f.count << " a " << f.unit_price;
}

int main()
{
    set<Fruit, Fruit_order> inventory;
    inventory.insert(Fruit{"Quince", 5, 0.5});
    inventory.insert(Fruit{"Apple", 200, 0.37});
    inventory.insert(Fruit{"Cherry", 40, 2.1});
    auto r = inventory.insert(Fruit{"Apple", 1, 9.99});      // stesso nome: per il set e' un duplicato
    cout << "secondo Apple inserito? " << r.second << '\n';

    for (auto p = inventory.begin(); p != inventory.end(); ++p)   // niente pair: *p e' direttamente l'elemento
        cout << *p << '\n';                                       // ordinato per nome

    auto it = inventory.find(Fruit{"Cherry", 0, 0});         // si cerca con un elemento "campione"
    cout << "Cherry: " << (it != inventory.end() ? it->count : -1) << " pezzi\n";
    inventory.erase(it);
    cout << "dopo erase: " << inventory.size() << " frutti\n";

    set<int> s{5, 1, 4, 1, 5, 9};                            // i duplicati spariscono, ordine crescente
    for (int x : s) cout << x << ' ';
    cout << "| count(4) = " << s.count(4) << ", multiset: ";
    multiset<int> ms{5, 1, 4, 1, 5, 9};                      // multiset: duplicati ammessi
    for (int x : ms) cout << x << ' ';
    cout << '\n';
}

Uscita eseguita:

secondo Apple inserito? 0
Apple x200 a 0.37
Cherry x40 a 2.1
Quince x5 a 0.5
Cherry: 40 pezzi
dopo erase: 2 frutti
1 4 5 9 | count(4) = 1, multiset: 1 1 4 5 5 9

Osservazioni.

• La funzione d'ordine Fruit_order confronta solo il nome. Per il set due frutti con lo stesso nome sono lo stesso elemento: il secondo Apple non viene inserito (inserito? 0). L'ordine deve essere un ordinamento "stretto" e coerente (a < b, non <=).
• Il set non contiene pair: si accede al dato direttamente con *p (le slide dicono per errore che è la map a non contenerli: è il set). Gli elementi di un set sono const: per modificare un elemento si toglie e si reinserisce, altrimenti si romperebbe l'ordinamento.
• find cerca con un elemento "campione" dell'ordinamento (qui basta il nome); erase accetta l'iteratore restituito.
• set<int> elimina i duplicati e ordina in modo crescente; il multiset li ammette.
• Le slide scrivono inventory.insert(Fruit{"Quince", 5}) con meno inizializzatori dei membri: è lecito (inizializzazione di aggregato) e gli altri membri restano a zero o al valore di default; nel programma sono indicati tutti.

Spunti di approfondimento

Le unordered_map e unordered_set implementano le tabelle hash: l'accesso medio è più veloce di map ma non c'è ordine, e per i tipi propri serve una funzione di hash oltre al confronto di uguaglianza. Gli stream iterator (istream_iterator) permettono di usare uno stream come sequenza di ingresso per gli algoritmi.

Domande d'esame

1. Quando conviene una map a un vector? Cosa fa m[k] se k non c'è? Traccia. Quando si cerca spesso per chiave non intera o non consecutiva: albero bilanciato, ricerca logaritmica e dati ordinati per chiave. m[k] crea l'elemento con valore di default (0 per int) e lo restituisce; per non creare si usa find o count.

2. Scrivere un programma che conta le occorrenze delle parole in un testo. Traccia. map<string,int> words; for (string s; cin >> s; ) ++words[s]; for (const auto& p : words) cout << p.first << ": " << p.second << '\n';.

3. Come si crea un set di tipi definiti dall'utente? Traccia. Serve una funzione d'ordine: struct Fruit_order { bool operator()(const Fruit& a, const Fruit& b) const { return a.name < b.name; } }; e set<Fruit, Fruit_order> inventory;. Due elementi equivalenti per l'ordine sono duplicati e non vengono inseriti.