C++ Map

Da Andreabont's Wiki.

Arrow left blue.pngVoce principale: C++ Contenitori.

In C++ una map è una struttura dati associativa chiave-valore, che permette di accedere ad uno dei valori salvati attraverso l'operatore [] nel quale viene inserita la chiave che indica in modo univoco il valore.

std::map

Questa map è internamente strutturata come un albero a ricerca binaria, quindi l'accesso chiave->valore avviene in tempo O(log n).

std::map<std::string, int> miamappa;
miamappa["chiave"] = 3;

Nel caso si voglia usare un oggetto personalizzato come chiave della map è necessario fornire l'implementazione dell'operatore di confronto, oppure implementare il corretto operatore sull'oggetto.

Fornire il funtore

Avendo il seguente funtore:

struct mioComparatore {
    bool operator()(const MiaClasse& a, const MiaClasse& b) const {
        return a.value < b.value;
    }
};

Possiamo dichiarare la nostra map:

std::map<MiaClasse, std::string, mioComparatore> miamappa;
MiaClasse istanza;
miamappa[istanza] = "ciao";

std::unordered_map

Questa map è internamente organizzata attraverso una funzione di hash, che associa la chiave al valore in tempo O(1).

std::unordered_map<std::string, int> miamappa;
miamappa["chiave"] = 3;

Nel caso si voglia usare un oggetto personalizzato come chiave della map è necessario fornire l'implementazione dell'operatore di uguaglianza e la funzione di hash oppure implementare il corretto operatore sull'oggetto.

Fornire i funtori

Implementiamo il funtore che fornirà alla unordered map la funzione di hash necessaria al suo funzionamento:

struct miaHash {
  size_t operator()(const MiaClasse &obj) const {
    return std::hash<int>()(obj.value);
  }
};

Implementiamo il funtore che fornirà l'operatore di uguaglianza alla unordered map:

struct mioComparatore {
  bool operator() (const MiaClasse &obj1, const MiaClasse &obj2) const {
    return (obj1.value == obj2.value);
  }
};

Possiamo quindi utilizzare la nostra unordered map:

std::unordered_map<MiaClasse, std::string, miaHash, mioComparatore> miamappa;
MiaClasse istanza;
miamappa[istanza] = "ciao";

Itarare per chiave-valore

for(auto& tuple : mymap) {
   std::cout << tuple.first << " -> " << tuple.second << std::endl;
}