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. Je voudrais savoir comment le faire de manière simple en C ++, car j’ai vu beaucoup d’implémentations différentes et aucune d’entre elles ne me paraissait simple.

Answer 1

La plupart des compilateurs devraient définir std :: hash_map pour vous; dans la prochaine norme C ++ 0x , elle fera partie de la bibliothèque standard sous la forme std :: unordered_map . La page STL est assez standard. Si vous utilisez Visual Studio, Microsoft a une page dessus.

Si vous voulez utiliser votre classe comme valeur et non comme clé, vous n'avez rien de spécial à faire. Tous les types primitifs (éléments tels que int , char , bool et même char * ) devraient "tout simplement fonctionner". en tant que clés dans un hash_map . Cependant, pour toute autre tâche, vous devrez définir vos propres fonctions de hachage et d’égalité, puis écrire "foncteurs". qui les envelopper dans une classe.

En supposant que votre classe s'appelle MyClass et que vous avez déjà défini:

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

Vous devrez définir deux foncteurs pour intégrer ces méthodes dans des 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 instanciez votre hash_map / hash_set en tant que:

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

Tout devrait fonctionner comme prévu par la suite.

Answer 2

Utiliser hashmaps en C ++ est simple! C'est comme utiliser une carte C ++ standard. Vous pouvez utiliser votre compilateur / bibliothèque de unordered_map ou celui fourni 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 carte de hachage simple (table de hachage) en C ++ pour une table de hachage de base avec un type générique key- paires de valeur et stratégie de chaînage séparée.