Los conjuntos son un tipo de contenedor asociativo en el que cada elemento tiene que ser único porque el valor del elemento lo identifica. Los valores se almacenan en un orden específico, es decir, ascendente o descendente.
El estándar::conjunto La clase es parte de la biblioteca de plantillas estándar (STL) de C++ y se define dentro del archivo de cabecera.
Sintaxis:
patrones de software java
std::set set_name;>
Tipo de datos: El conjunto puede tomar cualquier tipo de datos dependiendo de los valores, p.e. int, char, flotante, etc.
Ejemplo:
set val; // defining an empty set set val = {6, 10, 5, 1}; // defining a set with values> Programa:
C++
// C++ Program to Demonstrate> // the basic working of STL> #include> #include> int> main()> {> >std::set<>char>>a;> >a.insert(>'G'>);> >a.insert(>'F'>);> >a.insert(>'G'>);> >for> (>auto>& str : a) {> >std::cout << str <<>' '>;> >}> >std::cout <<>'
'>;> >return> 0;> }> |
>
>Producción
F G>
Complejidad del tiempo: O(N) // N es el tamaño del conjunto.
Espacio Auxiliar: EN)
La razón por la que imprimió solo F y G es que el conjunto no toma varios valores iguales, solo acepta un valor único. Nosotros podemos usar Conjunto múltiple si queremos almacenar varios valores iguales.
Establecer ordenado en orden descendente
De forma predeterminada, std::set está ordenado en orden ascendente. Sin embargo, tenemos la opción de cambiar el orden de clasificación utilizando la siguiente sintaxis.
java int como cadena
std::set set_name;>
Ejemplo:
C++
// C++ program to demonstrate the creation of descending> // order set container> #include> #include> using> namespace> std;> int> main()> {> >set<>int>, greater<>int>>>s1;> >s1.insert(10);> >s1.insert(5);> >s1.insert(12);> >s1.insert(4);> >for> (>auto> i : s1) {> >cout << i <<>' '>;> >}> >return> 0;> }> |
>
>Producción
escaneo.siguiente java
12 10 5 4>
Complejidad del tiempo: O(N) // N es el tamaño del conjunto.
Espacio Auxiliar: EN)
Nota: Podemos usar cualquier comparador en lugar de mayor para darle al conjunto un orden de clasificación personalizado.
Propiedades
- Orden de almacenamiento – El conjunto almacena los elementos en ordenado orden.
- Valores Características – Todos los elementos de un conjunto tienen valores únicos .
- Valores Naturaleza – El valor del elemento no se puede modificar una vez agregado al conjunto, aunque es posible eliminar y luego agregar el valor modificado de ese elemento. Así, los valores son inmutable .
- Técnica de búsqueda – Los conjuntos siguen el Árbol de búsqueda binaria implementación.
- Ordenar – Los valores de un conjunto son no indexado .
Nota: Para almacenar los elementos en un orden desordenado (aleatorio), conjunto_desordenado() puede ser usado.
Algunas funciones básicas asociadas con Set
- comenzar() – Devuelve un iterador al primer elemento del conjunto.
- fin() – Devuelve un iterador al elemento teórico que sigue al último elemento del conjunto.
- tamaño() – Devuelve el número de elementos del conjunto.
- tamaño máximo() – Devuelve el número máximo de elementos que el conjunto puede contener.
- vacío() – Devuelve si el conjunto está vacío.
Las complejidades de tiempo para realizar diversas operaciones en conjuntos son:
- Inserción de Elementos – O(logN)
- Eliminación de elementos – O(logN)
CPP
// C++ program to demonstrate various functions of> // STL> #include> #include> #include> using> namespace> std;> int> main()> {> >// empty set container> >set<>int>, greater<>int>>>s1;> >// insert elements in random order> >s1.insert(40);> >s1.insert(30);> >s1.insert(60);> >s1.insert(20);> >s1.insert(50);> >// only one 50 will be added to the set> >s1.insert(50);> >s1.insert(10);> >// printing set s1> >set<>int>, greater<>int>>>::iterador itr;> >cout <<>'
The set s1 is :
'>;> >for> (itr = s1.begin(); itr != s1.end(); itr++) {> >cout << *itr <<>' '>;> >}> >cout << endl;> >// assigning the elements from s1 to s2> >set<>int>>s2(s1.begin(), s1.end());> >// print all elements of the set s2> >cout <<>'
The set s2 after assign from s1 is :
'>;> >for> (itr = s2.begin(); itr != s2.end(); itr++) {> >cout << *itr <<>' '>;> >}> >cout << endl;> >// remove all elements up to 30 in s2> >cout <<>'
s2 after removal of elements less than 30 '> >':
'>;> >s2.erase(s2.begin(), s2.find(30));> >for> (itr = s2.begin(); itr != s2.end(); itr++) {> >cout << *itr <<>' '>;> >}> >// remove element with value 50 in s2> >int> num;> >num = s2.erase(50);> >cout <<>'
s2.erase(50) : '>;> >cout << num <<>' removed
'>;> >for> (itr = s2.begin(); itr != s2.end(); itr++) {> >cout << *itr <<>' '>;> >}> >cout << endl;> >// lower bound and upper bound for set s1> >cout <<>'s1.lower_bound(40) : '> ><< *s1.lower_bound(40) << endl;> >cout <<>'s1.upper_bound(40) : '> ><< *s1.upper_bound(40) << endl;> >// lower bound and upper bound for set s2> >cout <<>'s2.lower_bound(40) : '> ><< *s2.lower_bound(40) << endl;> >cout <<>'s2.upper_bound(40) : '> ><< *s2.upper_bound(40) << endl;> >return> 0;> }> |
>
>
npm borrar cachéProducción
The set s1 is : 60 50 40 30 20 10 The set s2 after assign from s1 is : 10 20 30 40 50 60 s2 after removal of elements less than 30 : 30 40 50 60 s2.erase(50) : 1 removed 30 40 60 s1.lower_bound(40) : 40 s1.upper_bound(40) : 30 s2.lower_bound(40) : 40 s2.upper_bound(40) : 60>
Función diferente de Set en C++ STL
| Función | Descripción |
|---|---|
| comenzar() | Devuelve un iterador al primer elemento del conjunto. |
| fin() | Devuelve un iterador al elemento teórico que sigue al último elemento del conjunto. |
| comenzar() | Devuelve un iterador inverso que apunta al último elemento del contenedor. |
| prestar() | Devuelve un iterador inverso que apunta al elemento teórico justo antes del primer elemento en el contenedor establecido. |
| crbegin() | Devuelve un iterador constante que apunta al último elemento del contenedor. |
| crédito() | Devuelve un iterador constante que apunta a la posición justo antes del primer elemento del contenedor. |
| comenzar() | Devuelve un iterador constante que apunta al primer elemento del contenedor. |
| algunos() | Devuelve un iterador constante que apunta a la posición más allá del último elemento del contenedor. |
| tamaño() | Devuelve el número de elementos del conjunto. |
| tamaño máximo() | Devuelve el número máximo de elementos que puede contener el conjunto. |
| vacío() | Devuelve si el conjunto está vacío. |
| insertar (const g) | Agrega un nuevo elemento 'g' al conjunto. |
| inserción de iterador (posición del iterador, const g) | Agrega un nuevo elemento 'g' en la posición señalada por el iterador. |
| borrar (posición del iterador) | Elimina el elemento en la posición señalada por el iterador. |
| borrar (const g) | Elimina el valor 'g' del conjunto. |
| claro() | Elimina todos los elementos del conjunto. |
| clave_comp() / valor_comp() | Devuelve el objeto que determina cómo se ordenan los elementos del conjunto ('<' por defecto). |
| encontrar (const g) | Devuelve un iterador al elemento 'g' en el conjunto si se encuentra; en caso contrario, devuelve el iterador al final. |
| contar (const g) | Devuelve 1 o 0 según si el elemento 'g' está presente en el conjunto o no. |
| límite_inferior(const g) | Devuelve un iterador al primer elemento que es equivalente a 'g' o que definitivamente no irá antes del elemento 'g' en el conjunto. |
| límite_superior(const g) | Devuelve un iterador al primer elemento que irá después del elemento 'g' en el conjunto. |
| rango_igual() | La función devuelve un iterador de pares. (comp_clave). El par se refiere al rango que incluye todos los elementos del contenedor que tienen una clave equivalente a k. |
| emplazar() | Esta función se utiliza para insertar un nuevo elemento en el contenedor del conjunto, solo si el elemento a insertar es único y no existe ya en el conjunto. |
| emplace_hint() | Devuelve un iterador que apunta a la posición donde se realiza la inserción. Si el elemento pasado en el parámetro ya existe, devuelve un iterador que apunta a la posición donde se encuentra el elemento existente. |
| intercambio() | Esta función se utiliza para intercambiar el contenido de dos juegos, pero los juegos deben ser del mismo tipo, aunque los tamaños pueden diferir. |
| operador= | El '=' es un operador en C++ STL que copia (o mueve) un conjunto a otro conjunto y set::operator= es la función del operador correspondiente. |
| get_allocador() | Devuelve la copia del objeto asignador asociado al conjunto. |
Diferencia entre conjunto y conjunto desordenado
| Colocar | Conjunto desordenado |
|---|---|
| Establecer elementos de tiendas en un orden ordenado. | El conjunto desordenado almacena elementos en un orden desordenado |
| Establecer tiendas/adquirir elementos únicos únicamente | El conjunto desordenado almacena/adquiere solo valores únicos |
| El conjunto utiliza árboles de búsqueda binaria para su implementación. | El conjunto desordenado utiliza tablas hash para la implementación |
| Se puede borrar más de un elemento dando el iterador inicial y final | Podemos borrar ese elemento para el cual se da la posición del iterador. |
| establecer Set_Name; | conjunto_desordenadoNombre_conjunto_desordenado; |
Para obtener más información, puede consultar el artículo: Conjuntos versus conjuntos desordenados .