Question

J'utilise habituellement la carte stdlib 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 objet). L’implémentation de la carte stdlib est basée sur des arbres offrant de meilleures performances (O (log n)) que le tableau standard ou le vecteur stdlib.

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

Était-ce utile?

La solution

Si vous utilisez C ++ 11, vous avez accès aux en-têtes <unordered_map> et <unordered_set>. Ces classes fournissent les std::unordered_map et std::unordered_set .

Si vous utilisez C ++ 03 avec TR1, vous avez accès 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 les en-têtes sont <tr1/unordered_map> et <tr1/unordered_set> à la place).

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

Autres conseils

Si vous ne possédez pas déjà unordered_map ni unordered_set, ils font partie de boost .
Voici la documentation relative aux deux .

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

std :: tr1 :: unordered_map, dans <unordered_map>

si vous n’avez pas tr1, obtenez un boost et utilisez boost :: unordered_map dans <boost/unordered_map.hpp>

Visual Studio a 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.

Voir std :: hash_map de SGI.

Ceci est également inclus dans la distribution de STLPort .

hash_map est également pris en charge dans les libstdc ++ .

Dinkumware a également pris en charge , ce qui Cela signifie que beaucoup d'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. Sinon, boost.org a une version assez similaire à l'exception de std :: namespace. Dans ce cas, insérez une déclaration using afin de pouvoir basculer sur std :: later.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top