Quelle est la meilleure façon d'utiliser un HashMap en C++?

A hash_map est une ancienne version non standardisée de ce qui est appelé unordered_map (actuellement disponible dans le cadre de TR1, et sera inclus dans C++0x). Comme le nom l'indique, il est différent de std::map principalement en étant non classé-si, par exemple, vous itérez à travers une carte de begin() à end() , vous obtenez des articles dans l'ordre par la touche ¹ , mais si vous itérez à travers un unordered_map de begin() à end() , vous obtenez des articles dans un ordre plus ou moins arbitraire.

Un unordered_map est normalement attendu pour avoir une constante de la complexité. C'est-à-dire une insertion, une recherche, etc., prend essentiellement un montant fixe de temps, indépendamment du nombre d'articles sont dans la table. Un std::map a une complexité qui est logarithmique sur le nombre d'articles stockés -- ce qui signifie que le temps d'insérer ou de récupérer un article augmente, mais très lentement , que la carte se développe plus grandes. Par exemple, s'il faut 1 microseconde pour rechercher l'un des 1 million d'articles, on peut s'attendre à ce qu'il faille environ 2 microsecondes pour rechercher l'un des 2 millions d'articles, 3 microsecondes pour l'un des 4 millions d'articles, 4 microsecondes pour l'un des 8 millions d'articles, etc.

d'un point de vue pratique, ce n'est pas vraiment toute l'histoire. Par nature, une table de hachage simple a une taille fixe. L'adapter aux exigences de taille variable pour un conteneur polyvalent est quelque peu non-trivial. Par conséquent, les opérations qui (potentiellement) font croître ou rétrécir la table (p. ex., insertion et suppression) sont souvent relativement lentes. Les recherches, qui ne peuvent pas changer la taille de la table, sont généralement beaucoup plus rapides. En conséquence, la plupart des tables basées sur le hash ont tendance à être à leur meilleur lorsque vous faites beaucoup de recherches et relativement peu d'insertions et de suppressions. Pour les situations où vous insérez beaucoup de données, puis itérez à travers la table une fois pour récupérer les résultats (par exemple, compter le nombre de mots uniques dans un fichier) les chances sont qu'un std::map sera tout aussi rapide, et très probablement encore plus rapide.

¹ où l'ordre est défini par le troisième paramètre du modèle lorsque vous créez la carte, std::less<T> par défaut.

voici un exemple plus complet et flexible qui n'omet pas les inclusions nécessaires pour générer des erreurs de compilation:

#include <iostream>
#include <unordered_map>

class Hashtable {
    std::unordered_map<const void *, const void *> htmap;

public:
    void put(const void *key, const void *value) {
            htmap[key] = value;
    }

    const void *get(const void *key) {
            return htmap[key];
    }

};

int main() {
    Hashtable ht;
    ht.put("Bob", "Dylan");
    int one = 1;
    ht.put("one", &one);
    std::cout << (char *)ht.get("Bob") << "; " << *(int *)ht.get("one");
}

N'est toujours pas particulièrement utile pour les clés, à moins qu'elles ne soient prédéfinies comme pointeurs, parce qu'une valeur correspondante ne fera pas l'affaire! (Cependant, puisque j'utilise normalement des chaînes de caractères pour les clés, remplacer" const void * "par" string " dans la déclaration de la clé devrait résoudre ce problème.)

comment utiliser une classe personnalisée et une fonction de hachage avec unordered_map

Cette réponse ongles: C++ unordered_map à l'aide d'un type de classe personnalisée comme la touche

extrait: égalité:

struct Key
{
  std::string first;
  std::string second;
  int         third;

  bool operator==(const Key &other) const
  { return (first == other.first
            && second == other.second
            && third == other.third);
  }
};

fonction de hachage:

namespace std {

  template <>
  struct hash<Key>
  {
    std::size_t operator()(const Key& k) const
    {
      using std::size_t;
      using std::hash;
      using std::string;

      // Compute individual hash values for first,
      // second and third and combine them using XOR
      // and bit shifting:

      return ((hash<string>()(k.first)
               ^ (hash<string>()(k.second) << 1)) >> 1)
               ^ (hash<int>()(k.third) << 1);
    }
  };

}