reactjs - unordered_set - unordered_map c++ example

¿La igualdad std:: unordered_map depende del orden de inserción?

Question

Si crea dos contenedores std::unordered_map usando el mismo conjunto de pares clave-valor (no iguales), pero insertados en un orden diferente (para que los contenedores contengan elementos iguales, pero potencialmente en diferentes órdenes), se garantiza que los contenedores sean igual, según el operador de igualdad ( operator== ). Supongo que los operadores de código hash e igualdad de los elementos del contenedor satisfacen todas las restricciones requeridas en su implementación.

Answer 1

A continuación hay citas de operator== sobre std: unordered_map, operator == operator== = (Std :: unordered_map):

El contenido de dos contenedores no ordenados lhs y rhs son iguales si se cumplen las siguientes condiciones:

• lhs.size () == rhs.size ()
• cada grupo de elementos equivalentes [lhs_eq1, lhs_eq2) obtenido de lhs.equal_range (lhs_eq1) tiene un grupo correspondiente de elementos equivalentes en el otro contenedor [rhs_eq1, rhs_eq2) obtenido de rhs.equal_range (rhs_eq1), que tiene las siguientes propiedades:
  • std :: distance (lhs_eq1, lhs_eq2) == std :: distance (rhs_eq1, rhs_eq2).
  • std :: is_permutation (lhs_eq1, lhs_eq2, rhs_eq1) == true.

Tenga en cuenta que:

El comportamiento no está definido si Key o T no son EqualityComparable.

El comportamiento tampoco está definido si Hash y KeyEqual lo hacen (hasta C ++ 20) KeyEqual (dado que C ++ 20) no tiene el mismo comportamiento en lhs y rhs o si operator == for Key no es un refinamiento de la partición en grupos de claves equivalentes introducidos por KeyEqual (es decir, si dos elementos que se comparan son iguales usando operator == caen en diferentes particiones)

Finalmente, considerar es la complejidad:

Proporcional a N llama al operador == en value_type, llama al predicado devuelto por key_eq, y llama al hasher devuelto por hash_function, en el caso promedio, proporcional a N2 en el peor caso donde N es el tamaño del contenedor.

Por lo tanto, si ambos mapas desordenados tienen el mismo tamaño, y cada clave en uno de los contenedores se busca en el otro más, si se encuentra, entonces se comparan sus valores, entonces se consideran los mismos.

Answer 2

De [unord.red]/12

Dos contenedores a y b no ordenados son iguales si a.size() == b.size() y, para cada grupo de clave equivalente [Ea1, Ea2) obtenido de a.equal_range(Ea1) , existe un grupo de clave equivalente [Eb1, Eb2) obtenido de b.equal_range(Ea1) , tal que is_permutation(Ea1, Ea2, Eb1, Eb2) devuelve true . [...]

Entonces, mientras las claves sean las mismas y el tamaño sea el mismo, los contenedores se compararán igual sin importar en qué orden estén las llaves.

Answer 3

Sí, están garantizados que serán iguales en este caso. La redacción específica (de N4659, § [unord.req] / 12) es:

Dos contenedores a y b no ordenados son iguales si a.size() == b.size() y, para cada grupo de clave equivalente [Ea1, Ea2) obtenido de a.equal_range(Ea1) , existe un grupo de clave equivalente [Eb1, Eb2) obtenido de b.equal_range(Ea1) , tal que is_permutation(Ea1, Ea2, Eb1, Eb2) devuelve true .

Por lo tanto, siempre que las claves (y los valores asociados) en uno sean iguales a los demás (pero posiblemente en un orden permutado diferente), se compararán iguales.