Hashtable en C++ ?

Question

J'utilise généralement C++ stdlib map lorsque j'ai besoin de stocker des données associées à un type de valeur spécifique (une valeur clé - par exemple une chaîne de caractères ou un autre objet). L'implémentation de stdlib map est basée sur des arbres qui offrent de meilleures performances (O(log n)) que le tableau standard ou le vecteur stdlib.

Ma question est la suivante : connaissez-vous une implémentation "standard" de hashtable en C++ qui offre des performances encore meilleures (O(1)) ? Quelque chose de similaire à ce qui est disponible dans la classe Hashtable de l'API Java.

Answer 1

Si vous utilisez C++11, vous avez accès à l'option <unordered_map> y <unordered_set> les en-têtes. Ceux-ci fournissent des classes std::unordered_map y std::unordered_set .

Si vous utilisez C++03 avec TR1, vous avez accès aux classes std::tr1::unordered_map y std::tr1::unordered_set en utilisant les mêmes en-têtes (sauf si vous utilisez GCC, auquel cas les en-têtes sont les suivants <tr1/unordered_map> y <tr1/unordered_set> à la place).

Dans tous les cas, il existe des unordered_multimap y unordered_multiset également.

Answer 2

Si vous n'avez pas encore unordered_map ou unordered_set, ils font partie du module booster .
Voici la documentation pour les deux .

Answer 3

Jetez un coup d'œil à ce blog : Comparaison des bibliothèques de tables de hachage .

Answer 4

Il existe un hash_map comme beaucoup l'ont mentionné ici, mais il ne fait pas partie du stl. C'est une extension SGI, donc si vous cherchez quelque chose dans la STL, je pense que vous n'avez pas de chance.

Answer 5

Visual Studio dispose de la classe stdext::hash_map dans l'en-tête <hash_map> et gcc a la classe __gnu_cxx::hash_map dans le même en-tête.