Je ne comprends pas std :: tr1 :: unordered_map

Question

J'ai besoin d'un conteneur associatif qui me permet d'indexer un certain objet à travers une chaîne, mais qui conserve aussi l'ordre d'insertion, donc je peux rechercher un objet spécifique par son nommer ou simplement itérer dessus et récupérer des objets dans le même ordre que je les ai insérés.

Je pense que ce hybrid of linked list and hash map devrait faire le travail, mais avant que j'essaie d'utiliser std::tr1::unordered_map en pensant que cela fonctionnait de cette façon, je l'ai décrit, mais ce n'était pas le cas. Alors quelqu'un pourrait-il m'expliquer le sens et le comportement de unordered_map?

---

@wesc: Je suis sûr std :: carte est mis en œuvre par STL, alors que je suis sûr std :: hash_map est pas dans la STL (je pense ancienne version de Visual Studio, il a mis dans un espace de noms appelé stdext). @cristopher: donc, si je comprends bien, la différence est dans l'implémentation (et donc dans les performances), pas dans la façon dont elle se comporte de l'extérieur.

Answer 1

Boost documentation of unordered containers

La différence est dans la méthode de la façon dont vous générez le haut de regard.

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

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

Voir le hachage pour une description de comment cela fonctionne.

Answer 2

I pense que qu'un 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 de cette omission.

unordered_map est juste que ... non ordonné. Vous ne pouvez pas en dépendre en conservant toute commande sur itération.

Answer 3

@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.

Answer 4

Vous êtes sûr que std :: hash_map existe dans tous les 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 4.3.1 de toute façon. Autant que je sache, hash_map a toujours été non-standard, et maintenant tr1 le corrige.

Answer 5

Désolé, lire votre dernier commentaire faux. Oui, hash_map n'est pas en STL, la carte est. Mais unordered_map et hash_map sont les mêmes que ceux que j'ai lus.

carte -> log (n) insertion, la récupération, l'itération est efficace (et ordonnée par comparaison clé)

hash_map/unordered_map -> insertion constante de temps et la récupération, le temps d'itération n'est pas garantie pour être efficace

Aucune d'entre elles ne fonctionnera pour vous-même, car la carte ordonne les éléments en fonction du contenu de la clé, et non de la séquence d'insertion (sauf si votre clé contient des informations sur la séquence d'insertion).

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

Answer 6

Vous devez indexer un conteneur associatif deux façons:

• ordre d'insertion
• de comparaison de chaînes

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

Answer 7

Vous avez demandé la raison canonique pour laquelle Boost :: MultiIndex a été créé: liste d'insertion avec recherche rapide par clé. Boost MultiIndex tutorial: list fast lookup