Semplice implementazione hashmap in C ++

Question

Sono relativamente nuovo in C ++. In Java, è facile per me creare un'istanza e utilizzare una hashmap. Mi piacerebbe sapere come farlo in modo semplice in C ++, dal momento che ho visto molte implementazioni diverse e nessuna di esse mi è sembrata semplice.

Answer 1

La maggior parte dei compilatori dovrebbe definire std :: hash_map per te; nel prossimo standard C ++ 0x , farà parte della libreria standard come std :: unordered_map . La Pagina STL su di essa è abbastanza standard. Se usi Visual Studio, Microsoft ha una pagina su di esso.

Se vuoi usare la tua classe come valore, non come chiave, non devi fare nulla di speciale. Tutti i tipi primitivi (cose come int , char , bool e persino char * ) dovrebbero " semplicemente funzionare " come chiavi in ??un hash_map . Tuttavia, per qualsiasi altra cosa dovrai definire le tue funzioni di hashing e uguaglianza e quindi scrivere "funzioni" che li avvolge in una classe.

Supponendo che la tua classe si chiami MyClass e che tu abbia già definito:

size_t MyClass::HashValue() const { /* something */ }
bool MyClass::Equals(const MyClass& other) const { /* something */ }

Dovrai definire due funzioni per avvolgere questi metodi negli oggetti.

struct MyClassHash {
  size_t operator()(const MyClass& p) const {
    return p.HashValue();
  }
};

struct MyClassEqual {
  bool operator()(const MyClass& c1, const MyClass& c2) const {
    return c1.Equals(c2);
  }
};

E crea un'istanza del tuo hash_map / hash_set come:

hash_map<MyClass, DataType, MyClassHash, MyClassEqual> my_hash_map;
hash_set<MyClass, MyClassHash, MyClassEqual> my_hash_set;

Tutto dovrebbe funzionare come previsto dopo.

Answer 2

L'uso di hashmap in C ++ è facile! È come usare una mappa C ++ standard. Puoi utilizzare l'implementazione del tuo compilatore / libreria di unordered_map o utilizzare quella fornita da boost o qualche altro fornitore. Ecco un rapido esempio. Ne troverai di più se segui i link che ti sono stati dati.

#include <unordered_map>
#include <string>
#include <iostream>

int main()
{
    typedef std::tr1::unordered_map< std::string, int > hashmap;
    hashmap numbers;

    numbers["one"] = 1;
    numbers["two"] = 2;
    numbers["three"] = 3;

    std::tr1::hash< std::string > hashfunc = numbers.hash_function();
    for( hashmap::const_iterator i = numbers.begin(), e = numbers.end() ; i != e ; ++i ) {
        std::cout << i->first << " -> " << i->second << " (hash = " << hashfunc( i->first ) << ")" << std::endl;
    }
    return 0;
}

Answer 3

Dai un'occhiata a boost.unordered e la sua struttura dati .

Answer 4

Prova le classi non ordinate di boost.

Answer 5

Scopri Implementazione di una mappa hash semplice (tabella hash) in C ++ per una tabella hash di base con chiave di tipo generico- coppie di valori e strategia di concatenamento separata.