¿Qué es un conjunto desordenado?
En C++ , un conjunto desordenado es un contenedor desordenado que puede contener varios elementos únicos. A diferencia de un conjunto, los elementos de un conjunto desordenado no se organizan en ningún orden en particular. Internamente, un conjunto desordenado se implementa mediante una tabla hash donde las claves se convierten en índices de una tabla hash, por lo que la inserción siempre es aleatoria. Todas las operaciones en unordered_set toman un tiempo constante O (1) en promedio, pero puede llegar al tiempo lineal O (n) en el peor de los casos, lo que también depende de la función hash utilizada internamente.
Unordered_set puede contener claves de cualquier tipo: estructura de datos predefinida o definida por el usuario, pero cuando definimos una clave de tipo, el usuario define el tipo, debemos especificar nuestra función de comparación según las claves que se compararán.
Funciones asociadas a un conjunto desordenado:
- insert() : inserta un nuevo {elemento} en el contenedor unordered_set.
- begin() : Devuelve un iterador que apunta al primer elemento en el contenedor unordered_set.
- end() : Devuelve un iterador que apunta al elemento más allá del final.
- count() : cuenta las ocurrencias de un elemento en particular en un contenedor unordered_set.
- find() : busca un elemento en el contenedor.
- clear() : elimina todos los elementos de un conjunto desordenado y lo vacía.
¿Qué es Vector?
En C++, un vector es similar a una array dinámica con la capacidad de cambiar su tamaño. Los elementos de un vector se almacenan en ubicaciones de memoria contiguas y también se puede acceder a ellos con la ayuda de iteradores.
Algunas de las funciones asociadas a un vector se describen a continuación:
- begin() : Devuelve un iterador que apunta al primer elemento del vector
- end(): Devuelve un iterador que apunta al elemento teórico que sigue al último elemento en el vector
- rbegin() : Devuelve un iterador inverso que apunta al último elemento del vector (comienzo inverso). Se mueve del último al primer elemento.
- rend() : Devuelve un iterador inverso que apunta al elemento teórico que precede al primer elemento del vector (considerado como extremo inverso)
- cbegin() : Devuelve un iterador constante que apunta al primer elemento del vector.
- cend() : Devuelve un iterador constante que apunta al elemento teórico que sigue al último elemento del vector.
- crbegin() : Devuelve un iterador inverso constante que apunta al último elemento del vector (comienzo inverso). Se mueve del último al primer elemento.
- crend() : Devuelve un iterador inverso constante que apunta al elemento teórico que precede al primer elemento del vector (considerado como extremo inverso).
¿Qué es un conjunto desordenado de vectores?
Un vector de conjunto desordenado es un contenedor asociativo desordenado que se usa para mantener juntos vectores únicos. Dos vectores se consideran iguales si los elementos correspondientes de los vectores son iguales.
A diferencia de un conjunto de vectores, los vectores no están ordenados en ningún orden particular en un conjunto desordenado de vectores. De forma predeterminada, C++ no nos brinda la posibilidad de crear un conjunto desordenado de vectores. Estamos obligados a pasar una función hash con la que se puede crear fácilmente un conjunto desordenado de vectores.
Sintaxis:
unordered_set<vector<tipo de datos>, hashFunction> myUnorderedSet;
Aquí,
dataType: un tipo de datos. Representa el tipo de valor almacenado por cada vector en el conjunto desordenado.
función hash:
struct hashFunction
{
size_t operator()(const vector<int> &myVector) const
{
std::hash<int> hasher;
tamaño_t respuesta = 0;
for (int i : myVector)
{
respuesta ^= hasher(i) + 0x9e3779b9 +
(respuesta << 6) + (respuesta >> 2);
}
devolver respuesta;
}
};Nota:
Uno puede personalizar la función hash según la necesidad, pero la función hash anterior es bastante eficiente para manejar colisiones.
Ejemplo 1: A continuación se muestra el programa C++ de un conjunto desordenado de vectores de tipo entero.
C++
// C++ program to demonstrate the
// working of unordered set of vectors
#include <bits/stdc++.h>
using namespace std;
// Hash function
struct hashFunction
{
size_t operator()(const vector<int>
&myVector) const
{
std::hash<int> hasher;
size_t answer = 0;
for (int i : myVector)
{
answer ^= hasher(i) + 0x9e3779b9 +
(answer << 6) + (answer >> 2);
}
return answer;
}
};
// Function to iterate over
// vector elements
void printVector(vector<int> myVector)
{
cout << "[ ";
for(auto element : myVector)
cout << element << ' ';
cout << "]\n";
}
// Function to iterate over unordered
// set elements
void print(unordered_set<vector<int>,
hashFunction> &unorderedsetOfVectors)
{
for (auto it = unorderedsetOfVectors.begin();
it != unorderedsetOfVectors.end();
it++)
{
// Each element is a vector
printVector(*it);
}
}
// Driver code
int main()
{
// Declaring a unordered set of vectors
// Each vector is of integer type
// We are passing a hash function as
// an argument to the unordered set
unordered_set<vector<int>,
hashFunction> unorderedsetOfVectors;
// Initializing vectors
vector<int> myVector1 {3, 6, 9, 10};
vector<int> myVector2 {5, 10, 11, 7};
vector<int> myVector3 {3, 6, 9, 10};
vector<int> myVector4 {1, 9, 11, 22};
vector<int> myVector5 {50, 20, 30, 40};
// Inserting vectors into unorderedset
unorderedsetOfVectors.insert(myVector1);
unorderedsetOfVectors.insert(myVector2);
unorderedsetOfVectors.insert(myVector3);
unorderedsetOfVectors.insert(myVector4);
unorderedsetOfVectors.insert(myVector5);
// Calling print function
print(unorderedsetOfVectors);
return 0;
}
Producción:
[ 50 20 30 40 ]
[ 1 9 11 22 ]
[ 3 6 9 10 ]
[ 5 10 11 7 ]
Explicación:
Vector1 y vector3 son iguales en el ejemplo anterior. Como un conjunto desordenado contiene solo elementos únicos, por lo tanto, se imprimió solo una vez dentro del conjunto desordenado. Además, tenga en cuenta que el conjunto desordenado no ha seguido ningún orden particular de elementos.
Ejemplo 2: A continuación se muestra el programa C++ de un conjunto desordenado de vectores de tipo booleano.
C++
// C++ program to demonstrate the
// working of unordered set
// of vectors
#include <bits/stdc++.h>
using namespace std;
// Hash function
struct hashFunction
{
size_t operator()(const vector<bool>
&myVector) const
{
std::hash<bool> hasher;
size_t answer = 0;
for (int i : myVector)
{
answer ^= hasher(i) + 0x9e3779b9 +
(answer << 6) + (answer >> 2);
}
return answer;
}
};
// Function to iterate over
// vector elements
void printVector(vector<bool> myVector)
{
cout << "[ ";
for(auto element : myVector)
cout << element << ' ';
cout << "]\n";
}
// Function to iterate over unordered
// set elements
void print(unordered_set<vector<bool>,
hashFunction> &unorderedsetOfVectors)
{
for (auto it = unorderedsetOfVectors.begin();
it != unorderedsetOfVectors.end();
it++)
{
// Each element is a vector
printVector(*it);
}
}
// Driver code
int main()
{
// Declaring a unordered set of vectors
// Each vector is of bool type
// We are passing a hash function as
// an argument to the unordered set
unordered_set<vector<bool>,
hashFunction> unorderedsetOfVectors;
// Initializing vectors of bool type
vector<bool> myVector1
{true, true, true, true};
vector<bool> myVector2
{false, false, false, false};
vector<bool> myVector3
{true, true, true, false};
vector<bool> myVector4
{true, true, false, false};
vector<bool> myVector5
{true, true, false, true};
vector<bool> myVector6
{true, true, true, true};
// Inserting vectors into unordered set
unorderedsetOfVectors.insert(myVector1);
unorderedsetOfVectors.insert(myVector2);
unorderedsetOfVectors.insert(myVector3);
unorderedsetOfVectors.insert(myVector4);
unorderedsetOfVectors.insert(myVector5);
unorderedsetOfVectors.insert(myVector6);
// Calling print function
print(unorderedsetOfVectors);
return 0;
}
Producción:
[ 1 1 0 1 ]
[ 1 1 0 0 ]
[ 1 1 1 0 ]
[ 1 1 1 1 ]
[ 0 0 0 0 ]
Explicación:
Vector1 y vector6 son iguales en el ejemplo anterior. Como un conjunto desordenado contiene solo elementos únicos, por lo tanto, se imprimió solo una vez dentro del conjunto desordenado. Además, tenga en cuenta que el conjunto desordenado no ha seguido ningún orden particular de elementos.