Si le non-ordonné_map en C ++ utilise une résolution de collision. Comment les valeurs / listes de valeurs chaînées peuvent-elles être consultées?
unordered_map<int,int> diff;
//collision : inserting two entries with same key 1
diff.insert(make_pair(1, 7));
diff.insert(make_pair(1, 26));
cout<<diff[1];
3 Réponses :
Si vous souhaitez plus d'une valeur par clé, vous devez utiliser un https://fr.cppreference.com/w/cpp/container/unorded_multimap
Vous perdrez la possibilité d'utiliser Unorded_multimap . Votre code actuel ne stocke pas une seconde valeur pour 1.
opérateur [] cependant.
"Votre code actuel efface 7 lorsque 26 est défini comme valeur pour 1." Oui, mais 26 ne sera pas défini comme valeur pour 1.
bon point. Mais toujours, si l'OP doit insérer plusieurs clés, une multimap répondra au problème.
Votre réponse est pour "Comment puis-je obtenir les 7 et 26". D'autre part, la réponse pour "Quel est le comportement de non-commandé_map dans de tels scénarios?" est "la deuxième insertion est rejetée".
MDR. Droite, j'ai raté la deuxième question. J'ai fait confiance (peut-être par erreur) le titre pour être la vraie requête
La deuxième insertion avec la clé qui existe déjà échouera.
Quote de STD :: Unommanded_map
insert_return_type insert (node_type && nh); (7) (Depuis C ++ 17)7) Si NH est une poignée de nœud vide, ne fait rien. Sinon, insère l'élément appartenant à NH dans le conteneur, si le conteneur ne contient pas déjà d'élément avec une clé équivalente à
NH.Key () . .7) renvoie un insert_return_type avec les membres initialisés comme suit: Si NH est vide, INSERTE est FALSE, la position est
extrémité () et le nœud est vide. Sinon, si l'insertion a eu lieu, insérée est vraie, les points de position à l'élément inséré et le nœud est vide. Si l'insertion a échoué, INSERTED est faux, le nœud a la valeur précédente de NH et de la position de position à un élément avec une clé équivalente àNH.Key () . .
Cette question montre un malentendu de la façon dont la chaînage est utilisée et ce que les gens veulent normalement par une collision.
dans votre code d'exemple: Les deux insertions ont la même clé, alors elles mappent dans le même seau dans la table de hachage. Le premier Vous ne devriez pas appeler cela une "collision" Bien que: il s'agissait de la même clé pour les deux appels d'insertion, qui est hachée par une fonction de hachage et mappée sur un "godet" dans la table de hachage, mais la même clé toujours carte vers le même seau - C'est une propriété inhérente à des fonctions et de tables de hachage. une collision est lorsque deux distincts clés du même seau. Tables de hachage Support Collisions : Ils vous permettent de stocker de nombreuses paires {Key, de la valeur} avec des touches distinctes qui se heurtent au même seau. La sortie est juste 7 Comment puis-je obtenir les deux à la fois 7 et 26 en supposant que la chaînage est utilisée dans UNRONOMORDED_MAP pour la résolution de collision.Qu'est-ce que le comportement de non ordonné_map dans de tels scénarios?
Vous ne pouvez pas obtenir les deux paires de la valeur de clé Quand Utilisation de insérer trouve le godet vide, donc {1,7} est lié à partir de ce godet. La deuxième fois, la fonction insert trouve la touche déjà insérée 1 liée du godet et abandonne l'insertion. Unommked_map ne prend pas en charge les touches : c'est-à-dire plusieurs paires {clé, valeur} avec la même clé.
{1,7} et {1,26} dans le même non ordonné_map en même temps. Pour permettre à la même clé d'être associé à plusieurs valeurs - donc insert ne recherche pas les éléments chaînés du godet pour voir si la clé était déjà insérée et abandonnée lorsqu'il est trouvé - vous devez utiliser un Unommked_multiset à la place. Unorded_Multiset , il y a certains justification logique pour l'appeler une collision lorsque plusieurs valeurs de même clé sont insérées, car les deux paires ne peuvent pas être d'abord dans la liste des nœuds chaînées - Il faut pousser l'autre à l'autre ou aller à l'arrière de la ligne - afin de parler, comme pour une collision clé différente à ce seau. Pour éviter toute confusion, je vous recommande de réserver la terminologie "collision" pour les collisions-clés de différenciation.