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

2 minutos de lectura

avatar de usuario de kal
cal

¿Cuándo debo elegir uno sobre el otro? ¿Hay algún consejo que recomendaría para usar los contenedores STL correctos?

  • No hay hashset en STL. Habrá unordered_set en C++ (con suerte) el próximo año.

    – Avakar

    25 de marzo de 2010 a las 18:28

  • Hablando de esto sgi.com/tech/stl/hash_set.html

    – kal

    25 de marzo de 2010 a las 18:31

  • Hay una discusión relacionada con esto aquí: http://stackoverflow.com/questions/222658/multiset-map-and-hash-map-complexity Editar: la respuesta de Adam Rosenfield sobre esa pregunta establece la gran O para cada uno.

    – es mate

    25 de marzo de 2010 a las 18:33

  • @mkal: Eso no es parte del STL estándar. hash_set es una extensión.

    – kennytm

    25 de marzo de 2010 a las 18:38

  • ¿Qué es el “STL estándar”?

    – Carreras de ligereza en órbita

    23 de abril de 2016 a las 17:22

Avatar de usuario de Mark Ransom
marca rescate

hash_set es una extensión que no forma parte del estándar C++. Las búsquedas deben ser O(1) en lugar de O(log n) para setpor lo que será más rápido en la mayoría de las circunstancias.

Se verá otra diferencia cuando itere a través de los contenedores. set entregará los contenidos en orden ordenado, mientras que hash_set será esencialmente aleatorio (Gracias Lou Franco).

Editar: Se introdujo la actualización de C++ 11 al estándar C++ unordered_set que debe preferirse en lugar de hash_set. El rendimiento será similar y está garantizado por la norma. El “desordenado” en el nombre enfatiza que iterarlo producirá resultados sin ningún orden en particular.

Avatar de usuario de Alex
Alex

stl::set se implementa como un árbol de búsqueda binaria.
hashset se implementa como una tabla hash.

El problema principal aquí es que mucha gente usa stl::set pensando que es una tabla hash con búsqueda de O (1), que no es y no tiene. Realmente tiene O(log(n)) para búsquedas. Aparte de eso, lea sobre árboles binarios frente a tablas hash para tener una mejor idea de las estructuras de datos.

  • ¿Por qué esto fue votado negativo? — un árbol rojo-negro es una especie de árbol de búsqueda binaria, y la especificación no dice que tiene que ser rojo-negro — simplemente establece parámetros de gran O para las operaciones.

    – Lou Franco

    25 de marzo de 2010 a las 18:54

  • @LouFranco: Probablemente porque discute [possible (likely!)] implementaciones en lugar de comportamiento/semántica exigidos por el estándar.

    – Carreras de ligereza en órbita

    23 de abril de 2016 a las 17:24

Otra cosa a tener en cuenta es que con hash_set debe proporcionar la función hash, mientras que un conjunto solo requiere una función de comparación (‘

  • También hay funciones hash para tipos nativos.

    – Lou Franco

    25 de marzo de 2010 a las 19:09

No creo que nadie haya respondido la otra parte de la pregunta todavía.

La razón para usar hash_set o unordered_set es el tiempo de búsqueda generalmente O(1). Digo generalmente porque de vez en cuando, dependiendo de la implementación, es posible que se deba copiar un hash en una matriz de hash más grande, o un cubo de hash puede terminar conteniendo miles de entradas.

La razón para usar un conjunto es si a menudo necesita el miembro más grande o más pequeño de un conjunto. Un hash no tiene orden, por lo que no hay una forma rápida de encontrar el elemento más pequeño. Un árbol tiene orden, por lo que el más grande o el más pequeño es muy rápido. O(log n) para un árbol simple, O(1) si contiene punteros a los extremos.

Avatar de usuario de Alex Gaynor
Alex Gaynor

Un hash_set se implementaría mediante una tabla hash, que tiene principalmente operaciones O(1), mientras que un conjunto se implementa mediante un árbol de algún tipo (AVL, rojo negro, etc.) que tiene operaciones O(log n), pero son en orden ordenado.

Editar: había escrito que los árboles son O (n). Eso está completamente mal.

  • Oh Jesús, no puedo creer que escribí O(n). Esa es probablemente la cosa más tonta que he hecho en todo el día.

    – Alex Gaynor

    26 de marzo de 2010 a las 5:07

  • Oh Jesús, no puedo creer que escribí O(n). Esa es probablemente la cosa más tonta que he hecho en todo el día.

    – Alex Gaynor

    26 de marzo de 2010 a las 5:07

¿Ha sido útil esta solución?