Funciones de conjunto desordenadas de C ++
Se utiliza una tabla hash para construir un conjunto desordenado donde los valores se convierten en índices de tabla hash para garantizar que la inserción de un valor siempre se asigne aleatoriamente. El hecho es que operan lo suficientemente bien y normalmente dan una operación de búsqueda de tiempo constante. Todas las funciones en el conjunto desordenado generalmente requieren un tiempo constante o (1). Aunque, en la peor situación, pueden tomar el tiempo lineal o (n) basado en el algoritmo de hash operativo.
El conjunto desordenado puede incluir claves de cualquier tipo, ya sea que estén predefinidos o de datos definidos por el usuario. Pero cada vez que declaramos las claves de las estructuras de datos definidas por el usuario, debemos indicar el método de comparación que se utiliza para comparar las claves.
Diferencia entre set y desordenado
Un set es una colección ordenada de teclas distintas. Pero un conjunto desordenado es una colección de claves que podrían organizarse en cualquier secuencia. La implementación de SET como una estructura de árbol equilibrada permite retener el orden de los componentes. Las operaciones establecidas tienen una complejidad de tiempo O (log n), pero un conjunto desordenado tiene una O (1). Se definen numerosos métodos para el conjunto desordenado. Pero los más populares son el tamaño y el método vacío para el almacenamiento, encontrar el valor de la clave e insertar y eliminar la configuración. Solo las claves distintas son compatibles con el conjunto desordenado; Para las claves duplicadas, se puede emplear una multisetea desordenada.
Funciones utilizadas para conjuntos desordenados
El conjunto desordenado tiene los siguientes métodos:
- Insert (): esta función agrega un nuevo elemento al contenedor.
- Función end (): devuelve un iterador que apunta al elemento después del final.
- Función count (): cuenta el número de veces que aparece un elemento específico en un conjunto desordenado.
- Método Find (): encuentra un componente en el conjunto.
- Función Clear (): vacía un conjunto desordenado eliminando todos sus componentes.
- Función cbegin (): Devuelve un iterador constante correspondiente al primer miembro en el conjunto desordenado.
- Función Cend (): Devuelve un iterador constante con el último valor en el conjunto desordenado.
- bucket_size (): en un conjunto desordenado, esta función devuelve el recuento total de elementos que están presentes en un determinado cubo.
- Función ERASE (): se elimina de principio a fin, ya sea solo un componente o una colección de elementos.
- Función size (): proporciona el recuento de elementos del conjunto desordenado.
- Función swap (): le permite intercambiar los datos de dos conjuntos desordenados.
- Función emplace (): agrega un elemento que usa esta función a un conjunto desordenado.
- Max_size (): esta función devuelve la mayoría de los elementos un conjunto desordenado es capaz de mantener.
- Método vacía (): verifica si un conjunto no ordenado está vacío.
- Rango igual: devuelve un rango con todos los elementos que tienen el valor predeterminado como su valor.
- Método hash (): Este es un método unario que solo acepta un parámetro y construye su valor de retorno en un valor singular size_t.
- Función de reserva (): se utiliza para exigir que se cambie la capacidad de un conjunto desordenado.
- Función Bucket (): devuelve el número de cubo del elemento.
- Función bucket_count (): este método devuelve el número total de cubos de un conjunto desordenado por este método.
- Load_factor (): Devuelve el factor de capacidad que se emplea con frecuencia al conjunto desordenado.
- Función de rehash (): aumenta el rango de cubos en el conjunto desordenado al número definido o mayor.
- Max_load_factor (): Devuelve el índice de capacidad de carga final que el conjunto no ordenado puede admitir.
- Función emplace_hint (): con el uso de una pista, solo agrega un nuevo elemento a un conjunto desordenado si el valor agregado es distinto.
- Función key_eq (): proporciona un valor booleano basado en la comparación.
La ejecución de diferentes funciones desordenadas en el lenguaje C ++ se cubre en este artículo.
Ejemplo 1:
El tiempo de procesamiento promedio para las funciones Find (), Insert () y ERASE () es constante. Si la clave no está presente en el conjunto definido, el método find () proporciona un iterador a la función End (); más, devuelve un iterador al atributo clave. Para adquirir la clave haciendo referencia a los valores clave con el operador *, el iterador actúa como un puntero a los atributos clave. La siguiente es una instancia de una declaración para las funciones find (), insert () e iteración en un conjunto desordenado.
#incluirusando el espacio de nombres STD;
int main ()
undered_setstrings;
instrumentos de cuerda.insertar ("i");
instrumentos de cuerda.insertar ("amor");
instrumentos de cuerda.insertar ("a");
instrumentos de cuerda.insertar ("jugar");
instrumentos de cuerda.insertar ("bádminton");
clave de cadena = "me gusta";
if (cadenas.encontrar (clave) == cadenas.fin())
cout<< key << " to explore " <
cout<< "explore " << key <
if (cadenas.encontrar (clave) == cadenas.fin())
cout<< key << " to explore\n" ;
demás
cout<< "explore " << key <
undered_set :: iterator i;
para (i = cadenas.comenzar(); i != cadenas.fin(); i ++)
cout<< (*i) <
Incorporamos el archivo de encabezado en el comienzo de este código. Luego, entramos en el espacio de nombres estándar como STD. Luego, invocamos la función principal (). Dentro de esta función, declaramos el conjunto desordenado. Aquí, usamos un conjunto desordenado para organizar los elementos de los conjuntos. Pasamos la cadena como el parámetro de la función de conjunto no ordenada. A continuación, insertamos las diferentes cadenas en los conjuntos. Pasamos las numerosas cadenas como los argumentos de la función Insertar (). Luego, especificamos el valor de la clave utilizando la palabra clave "clave". El método find () se usa en el siguiente paso. Esta función se aplica para encontrar la cadena requerida del conjunto.
Utilizamos el método End () para terminar las cadenas. Esta función devuelve el iterador siempre que la clave no exista en el conjunto. El comando "cout" se aplica para imprimir la declaración. Luego, inicializamos nuevamente un valor para el atributo "clave". Encontramos el valor de un atributo en la cadena utilizando la función find () y terminamos la cadena con la ayuda del método final (). Aplicamos la declaración de "cout" para mostrar el resultado. Iteramos sobre todo el conjunto e imprimimos el contenido del conjunto utilizando la declaración "Cout". Utilizamos el método de conjunto desordenado y declaramos el iterador como "i". Se emplea el bucle "para".
Primero, inicializamos una variable y luego utilizamos la función begin () para iniciar la cadena especificada. Además, definimos la condición del bucle. Se llama a la función End (). El valor del iterador se incrementa en 1. Al final, la declaración "cout" se usa para mostrar el valor del iterador.
Ejemplo 2:
En este caso, ejecutaremos un código en el que declaremos una lista de valores diferentes, y luego encontramos todos los duplicados de esa lista mediante el uso de la función de conjunto no ordenada.
#incluirusando el espacio de nombres STD;
Void printDuplicates (int a [], int b)
unordered_setIntset;
unordered_setDupLicate;
para (int j = 0; j < b; j++)
if (intset.encontrar (a [j]) == intset.fin())
intset.insertar (a [j]);
demás
duplicar.insertar (a [j]);
cout<< "The list of duplicated elements: ";
unordered_set :: iterator it;
para (it = duplicar.comenzar(); él != duplicar.fin(); IT ++)
cout<< *it << " ";
int main ()
int a [] = 11, 30, 42, 21, 94, 35, 11, 77, 62, 89, 94, 35;
int b = sizeof (a) / sizeof (int);
printDuplicates (a, b);
regresar 0;
Aquí incluimos la biblioteca. En el siguiente paso, utilizamos el espacio de nombres estándar como STD. Usamos el método print () para mostrar la replicación en la matriz definida mediante el uso de un conjunto desordenado. Proporcionamos una matriz y una variable para hilizar el entero como argumentos del método printDupplicates ().
Ahora, declaramos los conjuntos desordenados para adquirir y guardar los duplicados. Se utiliza la función de conjunto desordenada. Pasamos el entero como su parámetro. Luego, utilizamos otra función de conjunto desordenada para encontrar los elementos duplicados. Aquí aplicamos el bucle "para". Declaramos una variable del bucle "para". Entonces, especificamos la condición. A continuación, aumentamos el valor "J". Llamamos a la función Find () para encontrar el elemento definido en la matriz. Pasamos el elemento específico como argumento de esta función. Si el elemento requerido ya está presente en la matriz, insertamos ese elemento en el conjunto de duplicado.
Mostramos los valores duplicados de la matriz utilizando la declaración "Cout". Declaramos la variable "it" del iterador para el conjunto desordenado. Se aplica el bucle "para". Luego, los métodos Begin () y End () se usan dentro del bucle "para". Después de eso, llamamos a la función principal (). Inicializamos una variable "A". Luego, definimos los elementos para la matriz y esta matriz se almacena en una variable "A". Encontramos el tamaño de la matriz requerida utilizando el método sizeOf (). Pasamos la matriz como el parámetro de esta función.
Dividimos el valor resultante por el tamaño de los enteros. El valor que obtenemos después de dividir se almacena en una variable "B". Mostramos los valores duplicados de la matriz con la ayuda del método printDupLicate (). Al final, empleamos el comando "return 0".
Ejemplo 3:
Se puede agregar un elemento de datos al contenedor de conjunto no ordenado utilizando la función de biblioteca de plantilla estándar de C ++ InBuilt - la función Insert (). Cada elemento en un conjunto desordenado tiene un valor particular y solo se agrega si no está disponible en el conjunto. Dado que el contenedor emplea varios métodos de hash, la inserción se lleva a cabo automáticamente en el punto que cumple de manera óptima el requisito. Como resultado, el tamaño del contenedor se mejora considerablemente por el número de artículos recuperados.
Método de parámetros del inserto ():
- Valor: define el valor que se debe agregar al contenedor.
- Primero, último: iteradores que proporcionan una variedad de componentes. Tenga en cuenta que el rango abarca todos los componentes entre el primer elemento y el último elemento, como el especificado por el primer elemento, pero termina el elemento apuntado por el último elemento.
El método devuelve un par, con el par :: configurado primero a un iterador que se refiere al nuevo elemento actualizado o al componente correspondiente ya presente en el conjunto. Si se agrega un nuevo elemento de datos, el par :: segundo componente en el par se ajusta a verdadero; de lo contrario, se especifica como falso si un elemento idéntico ya está presente.
El siguiente programa demuestra la función antes mencionada:
#incluir#incluir
#incluir
usando el espacio de nombres STD;
int main ()
unordered_set set = "lunes", "martes";
cadena str = "miércoles";
Colocar.insertar (str);
cout<< "The set of week days is:"
<
cout<< m
<< " ";
cout<
En primer lugar, integramos los archivos de encabezado requeridos. El es responsable de las funcionalidades de entrada y salida. El archivo de encabezado contiene la declaración de las cadenas. El tercero contiene todos los conjuntos desordenados. Utilizamos el espacio de nombres estándar como STD. Luego, comenzamos la codificación dentro del cuerpo de la función Main () después de llamar a la función Main (). Utilizamos el conjunto desordenado de cuerdas.
Aquí, definimos los elementos de mi set. Especificamos los dos días de la semana. Ahora, indicamos el valor de la cadena que queremos insertarse en el conjunto requerido. Insertamos esa cadena utilizando el método Insert (). La declaración "Cout" se emplea para mostrar el texto "El conjunto de días laborables es". Usamos la instrucción "Cout" una vez más antes de ingresar el comando "return 0". Esta declaración de "cout" imprime todos los nombres de los días de semana.
Conclusión
El uso de las funciones de conjunto desordenadas de C ++ está cubierto en este artículo. Implementamos los varios códigos en el software Devc ++ donde utilizamos muchas funciones relacionadas con los conjuntos desordenados. Los conjuntos desordenados son estructuras de datos que pueden contener diferentes componentes en cualquier orden y proporcionar un acceso eficiente a elementos específicos basados en su valor. En primera instancia, utilizamos las múltiples funciones de conjunto desordenadas para examinar cómo funciona el código. Usando el método find (), identificamos un cierto elemento dentro del conjunto. Con la ayuda de la función End (), terminamos el conjunto desordenado. En la segunda ilustración, construimos una matriz que contiene varios enteros. Los valores repetidos y no repetidos se incluyen en la matriz. Para encontrar los valores duplicados en la matriz especificada, aplicamos el método find (). El método Insert () se usó en el último ejemplo para agregar un valor al conjunto desordenado requerido.