L'égalité std::unordered_map dépend-elle de l'ordre d'insertion ?

Question

Si vous créez deux std::unordered_map utilisant le même ensemble de paires clé-valeur (non égales), mais insérées dans un ordre différent (les conteneurs contiennent donc des éléments égaux, mais potentiellement dans des ordres différents), l'égalité des conteneurs est-elle garantie, selon l'opérateur d'égalité ( operator== ). Je suppose que les opérateurs de code de hachage et d'égalité des éléments du conteneur satisfont à toutes les contraintes requises pour leur mise en œuvre.

Answer 1

Oui, il est garanti qu'ils reviennent égaux dans ce cas. Le libellé spécifique (tiré de N4659, §[unord.req]/12) est le suivant :

Deux conteneurs non ordonnés a et b comparez, égalisez si a.size() == b.size() et, pour chaque groupe de clés équivalentes [Ea1, Ea2) obtenu à partir de a.equal_range(Ea1) il existe un groupe de clés équivalentes [Eb1, Eb2) obtenu à partir de b.equal_range(Ea1) de telle sorte que is_permutation(Ea1, Ea2, Eb1, Eb2) renvoie à true .

Ainsi, tant que les clés (et les valeurs associées) de l'un sont les mêmes que celles de l'autre (mais éventuellement dans un ordre différent), la comparaison sera égale.

Answer 2

De [unord.red]/12

Deux conteneurs non ordonnés a et b comparez, égalisez si a.size() == b.size() et, pour chaque groupe de clés équivalentes [Ea1, Ea2) obtenu à partir de a.equal_­range(Ea1) il existe un groupe de clés équivalentes [Eb1, Eb2) obtenu à partir de b.equal_­range(Ea1) de telle sorte que is_­permutation(Ea1, Ea2, Eb1, Eb2) renvoie à true . [...]

Ainsi, tant que les clés sont les mêmes et que la taille est la même, les conteneurs seront comparables, quel que soit l'ordre des clés.

Answer 3

Voici des citations de cppreference.com à propos du std:unordered_map, opérateur==,!=(std::unordered_map) :

Les contenus de deux conteneurs non ordonnés lhs et rhs sont égaux si les conditions suivantes sont remplies :

• lhs.size() == rhs.size()
• chaque groupe d'éléments équivalents [lhs_eq1, lhs_eq2) obtenu à partir de lhs.equal_range(lhs_eq1) a un groupe correspondant d'éléments équivalents dans l'autre conteneur [rhs_eq1, rhs_eq2) obtenu à partir de rhs.equal_range(rhs_eq1), qui a les propriétés suivantes :
  • std::distance(lhs_eq1, lhs_eq2) == std::distance(rhs_eq1, rhs_eq2).
  • std::is_permutation(lhs_eq1, lhs_eq2, rhs_eq1) == true.

Notez que :

Le comportement est indéfini si Key ou T ne sont pas EqualityComparable.

Le comportement est également indéfini si Hash et KeyEqual n'ont pas (jusqu'à C++20)KeyEqual n'a pas (depuis C++20) le même comportement sur les lhs et rhs ou si operator== pour Key n'est pas un raffinement de la partition en groupes de clés équivalentes introduite par KeyEqual (c'est-à-dire, si deux éléments qui se comparent de manière égale en utilisant operator== tombent dans des partitions différentes).

Enfin, il faut tenir compte de la complexité :

Proportionnel à N appels à l'opérateur== sur value_type, appels au prédicat renvoyé par key_eq et appels au hachoir renvoyé par hash_function, dans le cas moyen, proportionnel à N2 dans le cas le plus défavorable où N est la taille du conteneur.

Par conséquent, si les deux cartes non ordonnées ont la même taille, et que chaque clé de l'un des conteneurs est recherchée dans l'autre, et que si elle est trouvée, leurs valeurs sont comparées, alors elles sont considérées comme identiques.