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

Je sais que STL a une API HashMap, mais je ne trouve pas de documentation bonne et complète avec de bons exemples à ce sujet.

Tous les bons exemples seront appréciés.

La bibliothèque standard comprend les conteneurs de carte ( std::mapet std::unordered_map) ordonnés et non ordonnés . Dans une carte ordonnée, les éléments sont triés par la clé, l'insertion et l'accès est en O (log n) . Habituellement, la bibliothèque standard utilise en interne des arbres rouges et noirs pour les cartes ordonnées. Mais ce n'est qu'un détail de mise en œuvre. Dans une insertion de carte non ordonnée et l'accès est en O (1). C'est juste un autre nom pour une table de hachage.

Un exemple avec (ordonné) std::map:

#include <map>
#include <iostream>
#include <cassert>

int main(int argc, char **argv)
{
  std::map<std::string, int> m;
  m["hello"] = 23;
  // check if key is present
  if (m.find("world") != m.end())
    std::cout << "map contains key world!\n";
  // retrieve
  std::cout << m["hello"] << '\n';
  std::map<std::string, int>::iterator i = m.find("hello");
  assert(i != m.end());
  std::cout << "Key: " << i->first << " Value: " << i->second << '\n';
  return 0;
}

Production:

23
Clé: bonjour Valeur: 23

Si vous avez besoin de commander dans votre conteneur et que vous êtes d'accord avec le runtime O (log n), utilisez simplement std::map.

Sinon, si vous avez vraiment besoin d'une table de hachage (insertion / accès O (1)), vérifiez std::unordered_map, qui a une std::mapAPI similaire (par exemple dans l'exemple ci-dessus, il vous suffit de rechercher et de remplacer mappar unordered_map).

Le unordered_mapconteneur a été introduit avec la révision standard C ++ 11 . Ainsi, en fonction de votre compilateur, vous devez activer les fonctionnalités C ++ 11 (par exemple lorsque vous utilisez GCC 4.8, vous devez ajouter -std=c++11au CXXFLAGS).

Même avant la version C ++ 11 prise unordered_mapen charge par GCC - dans l'espace de noms std::tr1. Ainsi, pour les anciens compilateurs GCC, vous pouvez essayer de l'utiliser comme ceci:

#include <tr1/unordered_map>

std::tr1::unordered_map<std::string, int> m;

Il fait également partie de boost, c'est à dire que vous pouvez utiliser l'en -tête boost correspondant pour une meilleure portabilité.

A hash_mapest une version plus ancienne et non standardisée de ce que l'on appelle à des fins de standardisation an unordered_map(à l'origine dans TR1, et inclus dans la norme depuis C ++ 11). Comme son nom l'indique, il est std::mapprincipalement différent de ne pas être ordonné - si, par exemple, vous parcourez une carte de begin()à end(), vous obtenez les éléments dans l'ordre par la clé ¹ , mais si vous parcourez un unordered_mapde begin()à end(), vous obtenez des éléments dans un ordre plus ou moins arbitraire.

On unordered_maps'attend normalement à ce que An ait une complexité constante. Autrement dit, une insertion, une recherche, etc., prend généralement essentiellement une durée fixe, quel que soit le nombre d'éléments dans la table. An std::mapa une complexité logarithmique sur le nombre d'éléments stockés - ce qui signifie que le temps d'insertion ou de récupération d'un élément augmente, mais assez lentement , à mesure que la carte s'agrandit. Par exemple, s'il faut 1 microseconde pour rechercher l'un des 1 million d'éléments, alors vous pouvez vous attendre à ce que cela prenne environ 2 microsecondes pour rechercher l'un des 2 millions d'éléments, 3 microsecondes pour l'un des 4 millions d'éléments, 4 microsecondes pour l'un des 8 millions articles, etc.

D'un point de vue pratique, ce n'est pas vraiment toute l'histoire. Par nature, une simple table de hachage a une taille fixe. L'adapter aux exigences de taille variable pour un conteneur à usage général n'est pas trivial. En conséquence, les opérations qui (potentiellement) agrandissent la table (par exemple, l'insertion) sont potentiellement relativement lentes (c'est-à-dire que la plupart sont assez rapides, mais périodiquement une sera beaucoup plus lente). Les recherches, qui ne peuvent pas modifier la taille de la table, sont généralement beaucoup plus rapides. En conséquence, la plupart des tables basées sur le hachage ont tendance à être à leur meilleur lorsque vous effectuez beaucoup de recherches par rapport au nombre d'insertions. Pour les situations où vous insérez beaucoup de données, puis parcourez le tableau une fois pour récupérer les résultats (par exemple, en comptant le nombre de mots uniques dans un fichier), il y a de fortes chances qu'unstd::map sera tout aussi rapide, et peut-être même plus rapide (mais, encore une fois, la complexité de calcul est différente, donc cela peut également dépendre du nombre de mots uniques dans le fichier).

^{1 Où l'ordre est défini par le troisième paramètre de 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");
}

Toujours pas particulièrement utile pour les clés, sauf si elles sont prédéfinies comme pointeurs, car une valeur correspondante ne fera pas l'affaire! (Cependant, comme j'utilise normalement des chaînes pour les clés, le remplacement de "string" par "const void *" dans la déclaration de la clé devrait résoudre ce problème.)

Preuve qui std::unordered_maputilise une carte de hachage dans GCC stdlibc ++ 6.4

Cela a été mentionné sur: https://stackoverflow.com/a/3578247/895245 mais dans la réponse suivante: Quelle structure de données se trouve à l'intérieur de std :: map en C ++? J'en ai donné d'autres preuves pour l'implémentation GCC stdlibc ++ 6.4 par:

• Débogage d'étape GDB dans la classe
• analyse des caractéristiques de performance

Voici un aperçu du graphique des caractéristiques de performance décrit dans cette réponse:

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

Cette réponse le résout: C ++ unordered_map utilisant un type de classe personnalisé comme clé

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

}

Pour ceux d'entre nous qui essaient de comprendre comment hacher nos propres classes tout en utilisant le modèle standard, il existe une solution simple:

1. Dans votre classe, vous devez définir une surcharge d'opérateur d'égalité ==. Si vous ne savez pas comment faire cela, GeeksforGeeks a un excellent tutoriel https://www.geeksforgeeks.org/operator-overloading-c/

2. Sous l'espace de noms standard, déclarez une structure de modèle appelée hash avec votre nom de classe comme type (voir ci-dessous). J'ai trouvé un excellent article de blog qui montre également un exemple de calcul de hachages à l'aide de XOR et de bitshifting, mais cela sort du cadre de cette question, mais il comprend également des instructions détaillées sur la façon d'accomplir l'utilisation des fonctions de hachage https://prateekvjoshi.com/ 2014/06/05 / utilisation-de-la-fonction-de-hachage-en-c-pour-des-classes-définies par l'utilisateur /

namespace std {

  template<>
  struct hash<my_type> {
    size_t operator()(const my_type& k) {
      // Do your hash function here
      ...
    }
  };

}

3. Donc, pour implémenter une table de hachage en utilisant votre nouvelle fonction de hachage, il vous suffit de créer un std::mapou std::unordered_maptout comme vous le feriez normalement et de l'utiliser my_typecomme clé, la bibliothèque standard utilisera automatiquement la fonction de hachage que vous avez définie auparavant (à l'étape 2) pour hacher vos clés.

#include <unordered_map>

int main() {
  std::unordered_map<my_type, other_type> my_map;
}