example - unordered_map c++

¿Cuál es la diferencia entre set y unordered_set en C++?

Question

Nos encontramos con esta buena pregunta, que es similar, pero no del todo, ya que habla de Java, que tiene una implementación diferente de hash-tables, en virtud de tener acceso sincronizado / mutators Diferencias entre HashMap y Hashtable?

Entonces, ¿cuál es la diferencia en la implementación de C ++ de set y unordered_set? Esta pregunta se puede extender, por supuesto, al mapa frente a un mapa no ordenado, y así sucesivamente para otros contenedores de C ++.

Aquí está mi evaluación inicial

set : Si bien el estándar no pide explícitamente que se implemente como árboles, la restricción de tiempo-complejidad solicitada para sus operaciones de búsqueda / inserción significa que siempre se implementará como árbol. Por lo general, como árbol RB (como se ve en GCC 4.8), que es de altura equilibrada. Como tienen una altura equilibrada, tienen una complejidad de tiempo predecible para find ()

Ventajas: Compacto (en comparación con otros DS en comparación)

Con: La complejidad del tiempo de acceso es O (lg n)

unordered_set : Si bien el estándar no solicita explícitamente que se implemente como árboles, la restricción de complejidad de tiempo solicitada para sus operaciones de búsqueda / inserción significa que siempre se implementará como tabla hash.

Pros:

1. Más rápido (promesas amortizadas O (1) para la búsqueda)
2. Fáciles de convertir primitivas básicas a thread-safe, en comparación con Tree-DS

Contras :

1. Buscar no garantiza ser O (1) El peor caso térmico es O (n)
2. No es tan compacto como un árbol. (para fines prácticos, los factores de carga nunca son 1)

Nota: El O (1), para hashtable proviene de la suposición de que no hay colisión. Incluso con un factor de carga de .5, cada segunda inserción de variable está provocando una colisión. Se pudo observar que el factor de carga de hash-table es inversamente proporcional al número de operaciones requeridas para acceder a un elemento en él. Más reducimos #operations, sparser hash-table. Cuando el elemento almacenado tiene un tamaño comparable al puntero, la sobrecarga es bastante significativa.

Editar: Dado que la mayoría dice que la pregunta contiene suficiente respuesta, estoy cambiando la pregunta a "¿Perdí alguna diferencia entre el mapa / conjunto de análisis de rendimiento que uno debería saber?"

Answer 1

Creo que generalmente has respondido tu propia pregunta, sin embargo, esto:

No es tan compacto como un árbol. (para fines prácticos, los factores de carga nunca son 1)

no es necesariamente cierto. Cada nodo de un árbol (asumiremos que es un árbol rojo-negro) para un tipo T utiliza un espacio que es igual a al menos 2 * pointer_size + sizeof(T) + sizeof(bool) . Este puede ser un 3 * pointer size dependiendo de si el árbol contiene un puntero parent para cada nodo de árbol.

Compare esto con un hash-map: habrá un espacio de matriz desperdiciado para cada mapa hash debido al hecho de que load factor < 1 como ha dicho. Sin embargo, suponiendo que el mapa hash utiliza listas enlazadas para el encadenamiento (y realmente, no hay una razón real para no hacerlo), cada elemento insertado toma solo el sizeof(T) + pointer size .

Tenga en cuenta que este análisis ignora cualquier sobrecarga que pueda provenir del espacio extra utilizado por la alineación.

Para cualquier elemento T que tiene un tamaño pequeño (por lo tanto, cualquier tipo básico), el tamaño de los punteros y otros gastos generales domina. Con un factor de carga de > 0.5 (por ejemplo), std::unordered_set puede usar menos memoria que su equivalente std::set .

El otro gran punto que falta es el hecho de que iterar a través de un std::set está garantizado para producir un orden del más pequeño al más grande, basado en la función de comparación dada, mientras que iterar a través de std::unordered_set devolverá los valores en un "random " orden.

Answer 2

Otra diferencia (aunque no relacionada con el rendimiento) es que la inserción del set no invalida los iteradores, mientras que la inserción unordered_set puede si activa un reajuste. En la práctica, es una preocupación menor, ya que las referencias a los elementos reales siguen siendo válidas.

Answer 3

Yuushi ya se ocupa de la eficiencia espacial y otros puntos; Algunas otras partes de la pregunta comentaré ...

El O (1), para hashtable proviene de la suposición de que no hay colisión.

Eso no es cierto. Lo que O (1) significa no es que el primer intento de búsqueda siempre tenga éxito, es que hay, en promedio, una cantidad constante de intentos necesarios, en lugar de algo que crece a medida que crece el número de valores. Por ejemplo, con un _map o ... _map , max_load_factor defecto 1.0 en la construcción, y si el factor de carga se aproxima a eso con una buena función hash, el número promedio de elementos que hash a cualquier cubo será alrededor de 2 independientemente de cómo muchos valores están en la tabla.

Incluso con un factor de carga de .5, cada segunda inserción de variable está provocando una colisión.

Es cierto, pero no es tan grave como podría esperar intuitivamente: la longitud promedio de la cadena de 2 a 1.0 factor de carga no está mal.

Se pudo observar que el factor de carga de hash-table es inversamente proporcional al número de operaciones requeridas para acceder a un elemento en él. Más reducimos #operations, sparser hash-table.

Definitivamente hay una correlación (no es inversa).