programming - data structure c++ pdf

¿Por qué alguien usaría set en lugar de unordered_set?

Question

C ++ 0x está presentando unordered_set que está disponible en boost y en muchos otros lugares. Lo que entiendo es que unordered_set es una tabla hash con O(1) complejidad de búsqueda. Por otro lado, set no es más que un árbol con complejidad de búsqueda de log(n) . ¿Por qué diablos alguien usaría set lugar de unordered_set ? es decir, ¿hay necesidad de set más?

Answer 1

Considere algoritmos de barrido. Estos algoritmos fallarían por completo con tablas hash, pero funcionarían maravillosamente con árboles balanceados. Para darle un ejemplo concreto de un algoritmo de línea de barrido, considere el algoritmo de fortuna. http://en.wikipedia.org/wiki/Fortune%27s_algorithm

Answer 2

Cuando, para alguien que quiere iterar sobre los elementos del conjunto, importa el orden.

Answer 3

De mano, diría que es conveniente tener cosas en una relación si estás buscando convertirlo a un formato diferente.

También es posible que, si bien uno es más rápido de acceder, el tiempo para construir el índice o la memoria utilizada al crearlo y / o acceder a él es mayor.

Answer 4

Los conjuntos desordenados tienen que pagar por su tiempo promedio de acceso O (1) de varias maneras:

• set usa menos memoria que unordered_set para almacenar la misma cantidad de elementos.
• Para una pequeña cantidad de elementos , las búsquedas en un set pueden ser más rápidas que las búsquedas en un conjunto unordered_set .
• Aunque muchas operaciones son más rápidas en el caso promedio de unordered_set , a menudo se garantiza que tienen una mejor complejidad en el peor de los casos para el set (por ejemplo, insert ).
• Ese set ordena los elementos es útil si quieres acceder a ellos en orden.
• Puede comparar lexicográficamente diferentes set con < , <= , > y >= . unordered_set s unordered_set es necesario para admitir estas operaciones.

Answer 5

Perdóneme, una cosa más que vale la pena notar sobre la propiedad ordenada:

Si desea un rango de datos en el contenedor, por ejemplo: Usted almacenó la hora en el conjunto , y quiere tiempo desde 2013-01-01 hasta 2014-01-01.

Para unordered_set es imposible.

Por supuesto, este ejemplo sería más convincente para casos de uso entre map y unordered_map .

Answer 6

Porque std :: set es parte de Standard C ++ y unordered_set no lo es. C ++ 0x NO es un estándar, y tampoco lo es Boost. Para muchos de nosotros, la portabilidad es esencial, y eso significa apegarse al estándar.

Answer 7

Si alguien es demasiado perezoso para escribir desordenado_

Answer 8

Si desea ordenar las cosas, entonces usaría set en lugar de unordered_set. unordered_set se usa sobre el conjunto cuando el orden almacenado no importa.

Answer 9

Siempre que prefieras un árbol para una tabla hash.

Por ejemplo, las tablas hash son "O (n)" en el peor de los casos. O (1) es el caso promedio. Los árboles son "O ( log n)" en el peor.

Answer 10

Una cosa más, además de lo que otras personas ya mencionaron. Si bien la complejidad amortizada esperada para insertar un elemento en un conjunto no ordenado es O (1), de vez en cuando tomará O (n) porque la tabla hash necesita ser reestructurada (el número de segmentos debe cambiarse), incluso con una ''buena'' función hash. Al igual que insertar un elemento en un vector toma O (n) de vez en cuando porque la matriz subyacente necesita ser reasignada.

La inserción en un conjunto siempre lleva como máximo O (log n). Esto podría ser preferible en algunas aplicaciones.