Dados dos std::set s, uno puede simplemente iterar a través de ambos conjuntos simultáneamente y comparar los elementos, lo que resulta en una complejidad lineal. Esto no funciona para std::unordered_set s, porque los elementos se pueden almacenar en cualquier orden. Entonces, ¿qué tan caro es a == b para std::unordered_set?¿Qué tan caro es comparar dos conjuntos desordenados para la igualdad?
Complejidad de operator== y operator!=:
complejidad lineal en el caso promedio. N en el peor de los casos, donde N es el tamaño del contenedor.
Más detalles en el §23.2.5 estándar, punto 11:
Para unordered_set y unordered_map, la complejidad de operator== (es decir, el número de llamadas para el operador == de la value_type, al predicado devuelto por key_equal(), y a la hasher devuelto por hash_function()) es proporcional a N en el caso promedio y a N en el peor caso, donde N es a.size().
El peor caso es O (n²).
Pero los conjuntos desordenados en realidad están ordenados por hash. Por lo tanto, es posible comparar los valores hash (si esto falla, los conjuntos no pueden ser iguales) y luego verificar que los mismos valores hash (lineales) tengan los mismos valores (O (n²) para diferentes valores con el mismo hash).
En el mejor de los casos esto es O (n).
Normalmente la complejidad tiende a O (n) si la función hash es "buena" (diferentes objetos -> siempre diferente hash) y a O (n²) si la función hash es "mala" (todo siempre tiene el mismo valor hash)
"la función hash es buena (diferentes objetos -> hash siempre diferente)" -> diferentes hashes pueden ser verdaderos incluso para un terrible algoritmo hash (por ejemplo, cadenas hash de hasta 128 caracteres devolviendo un valor hash de 8 * 128 bits clonado desde la cadena), pero modifique eso en el número de cubos y el resultado es feo. Cuando no hay un conocimiento especial de las entradas que facilite la prevención de colisiones, una buena modificación de la función hash generalmente tiene colisiones en la proporción de cubetas usadas y no utilizadas ... lo que todavía da como resultado promedios de O (n). –
@TonyDelroy: ¡Gracias por señalar esto! Un "buen hash" no solo debe devolver "valores diferentes", sino también un "bien distribuido" respeto a los cubos (el espacio hash debe ser uniforme y primordial respecto a los cubos, solo para minimizar el efecto que mencionas) –
¿Tiene una forma eficiente de verificar la membresía establecida (por ejemplo, están respaldados por hashtables)? – Thilo
En palabras claras, sencillas, fáciles de comprender y comprender del Estándar C++: "Dos contenedores no ordenados' a' y 'b' se comparan igual 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 ' distancia (Ea1, Ea2) == distancia (Eb1, Eb2) 'y' is_permutation (Ea1, Ea2, Eb1) 'devuelve' true'. Para 'unordered_set' ... la complejidad de' operator == '... es proporcional a 'N' en el caso promedio y a' N^2' en el peor de los casos, donde 'N' es' a.size() '." –