Set vs Hashset en C++

1. Set vs. Hashset en C++
2. Set en C++
3. Hashset en C++
4. Diferencias clave entre un conjunto y un hashset en C++
5. Conclusión

Un set en C++ funciona como un contenedor para almacenar elementos de datos y recuperarlos cuando sea necesario. De manera similar, un hashset, más precisamente, unordered_set en C++, tiene un propósito similar al de los conjuntos de almacenamiento de elementos de datos.

En este artículo, vamos a discutir un set y un unordered_set en detalle.

Set vs. Hashset en C++

Un set es un contenedor asociativo que se utiliza para almacenar elementos de datos, mientras que un unordered_set también es un contenedor asociativo que se utiliza para almacenar elementos de datos para nuestras necesidades futuras. Entonces, ¿en qué se diferencian ambas estructuras de datos de los vectores, mapas y otros objetos contenedores?

La respuesta es simple. El set y un unordered_set almacenan elementos de datos únicos.

Por lo tanto, no permiten elementos duplicados. Sin embargo, otras estructuras de datos como vectores y mapas también permiten el almacenamiento de elementos duplicados.

Ambas estructuras de datos están presentes en la biblioteca de plantillas estándar de C++.

Ahora, ya que explicamos brevemente cuándo usar el set y el unordered_set en C++, ahora entendámoslos en detalle.

Set en C++

Como se discutió anteriormente, un set es un contenedor asociativo que almacena elementos de datos únicos de manera ordenada. Sin embargo, puede almacenarlos en cualquier orden aleatorio, pero tan pronto como los recupere del set, devolverá los elementos solo de forma ordenada.

Por lo tanto, un set contiene definiciones para clasificar los elementos de datos ocultos del usuario.

Los sets en C++ se implementan como árboles de búsqueda binarios; por lo tanto, están ordenados. Además, la búsqueda de un elemento lleva un tiempo O(log n).

Veamos cómo implementar un set en C++.

#include <iostream>
#include <set>
using namespace std;

int main() {
  int a[] = {4, 8, 3, 6, 9, 8, 1, 3, 3};
  int size = sizeof(a) / sizeof(a[0]);
  set<int> s;
  for (int i = 0; i < size; i++) {
    s.insert(a[i]);
  }
  set<int>::iterator i;
  for (i = s.begin(); i != s.end(); i++) {
    cout << *i << " ";
  }
}

Producción :

1 3 4 6 8 9

Por lo tanto, como puede ver en el ejemplo de código anterior, los elementos almacenados en la matriz están en orden aleatorio y contienen elementos duplicados. Sin embargo, tan pronto como se almacenan en un conjunto s, se ordenan internamente y también se eliminan los elementos duplicados.

Por lo tanto, la salida es un grupo ordenado de elementos sin duplicados.

Hashset en C++

El unordered_set o hashset en C++ significan lo mismo. Este unordered_set también se usa para almacenar elementos de datos únicos, pero la única diferencia entre un set y un unordered_set es que un unordered_set no tiene un orden en el que se almacenan los elementos mientras que el set almacena los elementos en orden ordenado.

Este unordered_set tampoco almacena elementos duplicados. Sin embargo, se implementan mediante tablas hash.

El elemento, también llamado clave, que se insertará se convierte en un índice de la tabla hash y se almacena en ese índice en particular.

Dado que los elementos se almacenan en cualquier orden aleatorio, recuperarlos lleva un tiempo O(1), lo que hace que su operación de búsqueda sea más rápida de implementar.

Tomemos un ejemplo del uso de un unordered_set en C++.

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
  int a[] = {4, 8, 3, 6, 9, 8, 1, 3, 3};
  int size = sizeof(a) / sizeof(a[0]);
  unordered_set<int> s;
  for (int i = 0; i < size; i++) {
    s.insert(a[i]);
  }
  unordered_set<int>::iterator i;
  for (i = s.begin(); i != s.end(); i++) {
    cout << *i << " ";
  }
}

Producción :

1 9 6 3 8 4

Por lo tanto, como puede ver en el ejemplo de código anterior, los elementos se almacenan en cualquier orden aleatorio en el conjunto; sin embargo, los elementos devueltos del conjunto también están en cualquier orden aleatorio, pero elimina todos los elementos duplicados y devuelve solo los elementos únicos al usuario.

Diferencias clave entre un conjunto y un hashset en C++

1. Los sets se utilizan para almacenar los elementos en orden creciente, mientras que un unordered_set almacena los elementos sin ningún orden.
2. Los sets se implementan utilizando los árboles de búsqueda binarios, mientras que un unordered_set se implementa utilizando las tablas hash.
3. La operación de búsqueda en un set tarda O(log n) en buscar un elemento, mientras que lleva O(1) en buscar un elemento en un unordered_set.
4. Los sets se incluyen en el archivo de encabezado #include <set>, mientras que un unordered_set se incluye utilizando el archivo de encabezado #include <unordered_set>.

Conclusión

En este artículo, hemos discutido un set y un hashset en C++. Ambas estructuras de datos están presentes en C++ STL y se utilizan para almacenar elementos de datos únicos.

Sin embargo, la diferencia clave entre los dos es que un set devuelve un conjunto ordenado de elementos, mientras que un unordered_set devuelve los elementos de datos sin orden.

Puedes usar cualquiera de los dos, pero la operación de búsqueda es más rápida en un unordered_set, tomando un tiempo casi constante para buscar un elemento; por lo tanto, se prefiere.