C++ - costrutto MAP / MULTIMAP

MAP e' un contenitore del C++ di tipo associativo che memorizza coppie di elementi chiave-valore, in cui ogni chiave è univoca. È implementato come un albero rosso-nero, il che garantisce un'efficienza logaritmica per l'inserimento, l'accesso e la cancellazione degli elementi.

La struttura std::map offre una serie di funzionalità:

• Associatività: gli elementi vengono memorizzati in base al valore della loro chiave. Le chiavi sono uniche, il che significa che non possono esserci due elementi con la stessa chiave all'interno della mappa.
• Ordinamento: gli elementi nella mappa vengono automaticamente ordinati in base all'ordine delle chiavi. Per impostazione predefinita, l'ordinamento è crescente, ma è possibile fornire un comparatore personalizzato per specificare un ordine diverso.
• Accesso tramite chiave: puoi accedere al valore associato a una chiave specifica utilizzando l'operatore di accesso [] o il metodo at(). Se la chiave non esiste nella mappa, verrà creata un'entry con la chiave fornita e un valore di default (zero per i tipi numerici, un oggetto vuoto per i tipi di oggetti personalizzati).
• Unicità delle chiavi: Le chiavi in una mappa sono uniche. Ciò significa che non possono esserci due elementi con la stessa chiave. Se si inserisce un elemento con una chiave già presente nella mappa, il valore associato alla chiave esistente verrà sovrascritto con il nuovo valore.
• Ricerca efficiente: la struttura interna dell'albero rosso-nero consente una ricerca efficiente degli elementi. L'accesso agli elementi tramite chiave avviene in tempo logaritmico (O(log n)).
• Inserimento e cancellazione efficiente: l'inserimento e la cancellazione degli elementi avvengono in tempo logaritmico (O(log n)). Questa efficienza è garantita dall'implementazione dell'albero rosso-nero.
• Dimensione dinamica: le dimensioni della mappa possono cambiare dinamicamente, consentendo l'aggiunta e la rimozione di elementi durante l'esecuzione del programma.
• Iterazione: puoi iterare attraverso gli elementi della mappa utilizzando iteratori o range-based for loop.

#include <iostream>
#include <map>

int main() {
    std::map<std::string, int> scores;

    scores["Alice"] = 95;
    scores["Bob"] = 80;
    scores["Charlie"] = 75;

    std::cout << "Alice's score: " << scores["Alice"] << std::endl;

    for (const auto& pair : scores) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

In C++, la classe std::map della libreria standard gestisce una singola chiave associata a un valore. Se desideri gestire più chiavi per un unico valore, puoi utilizzare una variante di std::map chiamata std::multimap.

La classe std::multimap è molto simile a std::map, ma consente di avere più coppie chiave-valore con la stessa chiave. Questo significa che puoi inserire più elementi con la stessa chiave all'interno di una std::multimap.

Ecco un esempio di utilizzo di std::multimap:

#include <iostream>
#include <map>

int main() {
    std::multimap<int, std::string> students;

    students.insert(std::make_pair(1, "Alice"));
    students.insert(std::make_pair(2, "Bob"));
    students.insert(std::make_pair(1, "Charlie"));

    // Itera attraverso gli elementi con chiave 1
    auto range = students.equal_range(1);
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
    }

    return 0;
}

In questo esempio, viene creata una std::multimap chiamata students in cui le chiavi sono identificatori degli studenti e i valori sono i loro nomi. Vengono inseriti tre elementi, due con chiave 1 e uno con chiave 2.

Successivamente, viene utilizzato il metodo equal_range(1) per ottenere un intervallo di iteratori che rappresentano gli elementi con chiave 1. Il ciclo for itera attraverso l'intervallo e stampa le chiavi e i valori corrispondenti.

Si noti che std::multimap mantiene gli elementi ordinati per chiave, ma non per valore. Pertanto, se l'ordine dei valori è rilevante, potresti dover utilizzare altre strutture dati o logica aggiuntiva per mantenere l'ordine desiderato.

Spero che questa spiegazione sia stata chiara. Se hai altre domande, non esitare a chiedere.