Implémentation simple de hashmap en C ++

Question

Je suis relativement nouveau en C ++. En Java, il m'est facile d'instancier et d'utiliser un hashmap. J'aimerais savoir comment le faire de manière simple en C ++, car j'ai vu de nombreuses implémentations différentes et aucune ne me paraissait simple.

Answer 1

La plupart des compilateurs doivent définir std::hash_map pour vous; dans les prochains C++0x standard, il fera partie de la bibliothèque standard, comme std::unordered_map. La STL Page sur c'est assez standard. Si vous utilisez Visual Studio, Microsoft a une page sur elle.

Si vous souhaitez utiliser votre classe en tant que valeur, pas comme les clés, alors vous n'avez pas besoin de faire quelque chose de spécial. Tous les types primitifs (des choses comme int, char, bool et même char *), il faut "juste travail" comme clés dans un hash_map. Cependant, pour quoi que ce soit d'autre, vous devrez définir vos propres fonctions de hachage et de l'égalité des fonctions et ensuite écrire "foncteurs" que de les encapsuler dans une classe.

En supposant que votre classe est appelée MyClass et vous avez déjà défini:

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

Vous aurez besoin de définir deux foncteurs pour envelopper ces méthodes dans les objets.

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);
  }
};

Et instancier votre hash_map/hash_set comme:

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

Tout devrait fonctionner comme prévu après cela.

Answer 2

Utiliser hashmaps en C ++ est facile! C'est comme utiliser une carte C ++ standard. Vous pouvez utiliser votre implémentation compilateur / bibliothèque de unordered_map ou celle fournie par boost , ou un autre fournisseur. Voici un échantillon rapide. Vous en trouverez plus si vous suivez les liens qui vous ont été donnés.

 #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

Jetez un coup d'œil à boost.unordered et à sa structure de données .

Answer 4

Essayez les classes non ordonnées de boost.

Answer 5

Découvrez l' implémentation de la table de hachage simple (table de hachage) en C ++ pour une table de hachage de base avec des paires clé-valeur de type générique et une stratégie de chaînage séparée.