Je ne comprends pas std :: tr1 :: unordered_map

Question

J'ai besoin d'un conteneur associatif qui me fait indexer un certain objet via une chaîne, mais qui conserve également l'ordre d'insertion, afin que je puisse rechercher un objet spécifique par son nom ou simplement le parcourir et récupérer les objets dans le même ordre que j'ai inséré. eux.

je pense que ce hybride de liste chaînée et de carte de hachage devrait faire l'affaire, mais avant d'essayer d'utiliser std::tr1::unordered_map pensant que cela fonctionnait de cette façon que j'ai décrit, mais ce n'était pas le cas.Alors quelqu'un pourrait-il m'expliquer la signification et le comportement de unordered_map?

---

@wesc :Je suis sûr que std::map est implémenté par STL, alors que je suis sûr que std::hash_map n'est PAS dans la STL (je pense que l'ancienne version de Visual Studio l'a placé dans un espace de noms appelé stdext).

@cristopher :donc, si je comprends bien, la différence réside dans l'implémentation (et donc les performances), pas dans la façon dont il se comporte en externe.

Answer 1

Améliorer la documentation des conteneurs non commandés

La différence réside dans la méthode de génération de la recherche.

Dans les conteneurs de carte/ensemble, le operator< est utilisé pour générer un arbre ordonné.

Dans les conteneurs non commandés, un operator( key ) => index est utilisé.

Voir hachage pour une description de la façon dont cela fonctionne.

Answer 2

Vous avez demandé la raison canonique pour laquelle Boost::MultiIndex a été créé :ordre d'insertion de liste avec recherche rapide par clé. Tutoriel Boost MultiIndex :liste de recherche rapide

Answer 3

Vous devez indexer un conteneur associatif de deux manières :

• Ordre d'insertion
• Comparaison de chaînes

Essayer Boost.MultiIndex ou Boost.Intrusif.Je ne l'ai pas utilisé de cette façon mais je pense que c'est possible.

Answer 4

Désolé, j'ai mal lu votre dernier commentaire.Oui, hash_map n'est pas en STL, map l'est.Mais unordered_map et hash_map sont identiques d'après ce que j'ai lu.

map -> log (n) l'insertion, la récupération, l'itération sont efficaces (et classées par comparaison clé)

hash_map/unordered_map -> insertion et récupération à temps constant, le temps d'itération n'est pas garanti pour être efficace

Aucun de ces éléments ne fonctionnera pour vous par lui-même, puisque la carte classe les éléments en fonction du contenu de la clé et non de la séquence d'insertion (à moins que votre clé ne contienne des informations sur la séquence d'insertion).

Vous devrez faire soit ce que vous avez décrit (list + hash_map), soit créer un type de clé comportant le numéro de séquence d'insertion ainsi qu'une fonction de comparaison appropriée.

Answer 5

je pense qu'unordered_map et hash_map sont plus ou moins la même chose.La différence est que la STL n'a pas officiellement de hash_map (ce que vous utilisez est probablement une chose spécifique au compilateur), donc unordered_map est le correctif pour cette omission.

unordered_map c'est juste ça...non ordonné.Vous ne pouvez pas compter sur lui pour conserver l'ordre des itérations.

Answer 6

Vous êtes sûr que std::hash_map existe dans tous Implémentations STL ?SGI STL l'implémente, mais GNU g++ ne l'a pas (il est situé dans l'espace de noms __gnu_cxx) à partir de la version 4.3.1 de toute façon.Pour autant que je sache, hash_map a toujours été non standard, et maintenant tr1 corrige ce problème.

Answer 7

@wesc :STL a std :: map...alors quelle est la différence avec unordered_map ?Je ne pense pas que STL implémenterait deux fois la même chose et l'appellerait différemment.