Esercizio - Confronto tra map e vector (secondo appello 2021-22, teoria)

Domanda aperta 3 del secondo appello 2021-22 (11 febbraio 2022) del corso di Laboratorio di Programmazione, Ing. Informatica UniPD. Teoria: STL - container associativi (map e set)I container associativi memorizzano gli elementi in base a una chiave: map è un contenitore ordinato di coppie (chiave, valore) ottimizzato per cercare dalla chiave (albero bilanciato, ricerca in tempo logaritmico), con operator[] che crea l'elemento se la chiave manca (il valore è inizializzato con il costruttore di default, quindi ++words[s] conta le occorrenze); gli elementi sono pair<const Chiave, Valore> con campi first e second. set è una map senza valori: contiene solo chiavi ordinate, senza [] né push_back, si usa con insert ed erase, e per i tipi definiti dall'utente richiede una funzione d'ordine (un function object). Le varianti: multimap e multiset ammettono chiavi ripetute; le versioni unordered_* usano tabelle hash e non mantengono l'ordine. Header , 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) →. Strutture dati analoghe in Mappe e dizionariADT mappa (chiavi distinte) con get, put, remove, keySet/values/entrySet; famiglia mappa/mappa ordinata/dizionario (multimappa); applicazioni; implementazioni semplici ma poco efficienti (lista, array indicizzato dalle chiavi); dizionario realizzato con una mappa di liste.Mappe e dizionari → e Tabelle hashTabella hash per implementare una mappa: funzione hash = hash code + compression function, bucket array, separate chaining; hash code per numeri e stringhe (polynomial, cyclic shift), division e MAD; load factor, complessità al caso pessimo Theta(n) e medio O(1+lambda), rehashing; esempio svolto con inserimenti e collisioni.Tabelle hash →; un confronto con la lista è in Esercizio - Confronto tra list e vector (terzo appello 2021-22, teoria).

Testo. Si illustrino le differenze tra i contenitori STL map e vector, fornendo dettagli sulle rispettive politiche di gestione dei dati. Si riporti un esempio di utilizzo di map e un esempio di utilizzo di vector.

vector

Un contenitore sequenziale: una sequenza di elementi dello stesso tipo in memoria contigua.

• accesso per posizione: v[i] in tempo costante, at(i) con controllo dei limiti (su richiesta); front(), back();
• gli elementi stanno nell'ordine di inserimento (nessun ordinamento automatico), si possono ripetere;
• espandibile: push_back() aggiunge in coda (tempo ammortizzato costante, il buffer raddoppia quando è pieno, vedi Esercizio - MyVector 2.0 con buffer ridimensionabile (laboratorio 4));
• insert() ed erase() in mezzo sono inefficienti (spostano gli elementi successivi) e invalidano gli iteratori: serve usare il valore restituito;
• cercare un valore richiede di scorrere la sequenza ($O(n)$, o $O(\log n)$ solo se ordinata, con la ricerca binaria);
• operator== confronta gli elementi.

map

Un contenitore associativo: gestisce coppie (chiave, valore), in cui la chiave è unica e determina la posizione.

• è ordinato per chiave (con <, o con una funzione d'ordine data) ed è rappresentato con un albero bilanciato (non in memoria contigua);
• accesso e ricerca per chiave: m[k], find(k), in tempo $O(\log n)$; l'inserimento resta ordinato, sempre $O(\log n)$, senza spostare gli altri elementi;
• gli elementi sono pair<const K, V> con membri first (chiave) e second (valore); si visitano in ordine di chiave;
• operator[] crea l'elemento se la chiave manca, con valore inizializzato col "costruttore di default" (0 per int): comodo per i conteggi (++words[s]);
• non esiste push_back(): è la mappa a decidere dove inserire; non esiste "l'$i$-esimo elemento";
• un set è una map senza valori (solo chiavi ordinate).

Confronto

Esempio di utilizzo di entrambi

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

int main()
{
    // VECTOR: sequenza contigua, accesso per posizione, nell'ordine in cui si inserisce
    vector<string> parole {"pera", "mela", "pera", "uva", "mela", "pera"};
    cout << "vector: " << parole.size() << " elementi, parole[2] = " << parole[2] << '\n';
    int n_pera = 0;
    for (const string& s : parole) if (s == "pera") ++n_pera;       // cercare un valore = scorrere tutto: O(n)
    cout << "pere (conteggio a mano): " << n_pera << '\n';

    // MAP: coppie (chiave, valore) ordinate per chiave, ricerca per chiave
    map<string, int> conteggio;
    for (const string& s : parole) ++conteggio[s];                  // operator[] crea la chiave se manca (valore 0)
    for (const auto& p : conteggio)                                 // visita in ordine di chiave
        cout << "  " << p.first << ": " << p.second << '\n';
    cout << "conteggio[\"pera\"] = " << conteggio["pera"] << '\n';
    auto it = conteggio.find("uva");                                // ricerca per chiave: O(log n)
    cout << "find(uva): " << (it != conteggio.end() ? "trovata" : "assente") << ", "
         << "find(kiwi): " << (conteggio.find("kiwi") != conteggio.end() ? "trovata" : "assente") << '\n';
    cout << "size della map = " << conteggio.size() << " chiavi (le ripetizioni confluiscono in una)\n";

    // insert su vector: sposta gli elementi e invalida gli iteratori; il valore restituito e' quello buono
    vector<int> v {0, 1, 2, 3, 4, 5};
    auto p = v.begin() + 3;
    p = v.insert(p, 99);                                            // riassegna p: il vecchio non vale piu'
    cout << "dopo insert: *p = " << *p << ", v.size() = " << v.size() << '\n';
    return 0;
}

vector: 6 elementi, parole[2] = pera
pere (conteggio a mano): 3
  mela: 2
  pera: 3
  uva: 1
conteggio["pera"] = 3
find(uva): trovata, find(kiwi): assente
size della map = 3 chiavi (le ripetizioni confluiscono in una)
dopo insert: *p = 99, v.size() = 7

• Il vector conserva le sei parole nell'ordine, anche ripetute; contare le "pera" richiede di scorrere tutto.
• La map<string, int> fa il conteggio direttamente: ++conteggio[s] crea la chiave con valore 0 la prima volta e poi incrementa; visitata in ordine alfabetico di chiave (mela, pera, uva); le sei parole confluiscono in tre chiavi; find restituisce end() se la chiave manca.
• Ultima parte: v.insert(p, 99) sposta gli elementi dopo la posizione e restituisce un iteratore valido; il vecchio p non lo è più: per questo si riassegna.