Hashtable en C ++?

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

Mes questions sont les suivantes: connaissez-vous une implémentation hashtable “standard” en C ++ qui offre de meilleures performances (O (1))? Quelque chose de similaire à ce qui est disponible dans la classe Hashtable à partir de l’API Java.

Si vous utilisez C ++ 11, vous avez access aux en-têtes et . Celles-ci fournissent les classes std::unordered_map et std::unordered_set .

Si vous utilisez C ++ 03 avec TR1, vous avez access aux classes std::tr1::unordered_map et std::tr1::unordered_set , en utilisant les mêmes en-têtes (sauf si vous utilisez GCC, auquel cas la les en-têtes sont et place.

Dans tous les cas, il existe également unordered_multiset types unordered_multimap et unordered_multiset correspondants.

Si vous ne possédez pas déjà unordered_map ou unordered_set, ils font partie du boost .
Voici la documentation pour les deux .

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

std :: tr1 :: unordered_map, dans

si vous n’avez pas tr1, obtenez un coup de pouce et utilisez boost :: unordered_map dans

Visual Studio a la classe stdext::hash_map dans l’en-tête et gcc a la classe __gnu_cxx::hash_map dans le même en-tête.

Voir std :: hash_map de SGI.

Ceci est également inclus dans la dissortingbution STLPort .

hash_map est également supporté dans libstdc ++ de GNU.

Dinkumware le supporte également, ce qui signifie que de nombreuses implémentations auront un hash_map (je pense que même Visual C ++ est fourni avec Dinkumware).

Si vous avez les extensions TR1 disponibles pour votre compilateur, utilisez-les. Si ce n’est pas le cas, boost.org a une version assez similaire à l’exception de std :: namespace. Dans ce cas, insérez une déclaration using afin de pouvoir passer à std :: later.

std :: hash_map