C++ Mapas (maps) y conjuntos (sets) desordenados

Requisitos:

• Unos conocimientos más o menos equivalentes a los entrenamientos de iniciación
• C++ Pilas (stacks) y colas (queues)

 

En el artículo de hoy veremos dos estructuras de datos que tiene C++: conjuntos desordenados (unordered sets) y mapas desordenados (unordered maps).

Conjuntos desordenados (unordered sets)

Los conjuntos desordenados (unordered sets) son la forma de C++ de representar una bolsa con objetos, como podría ser una bolsa de strings o de ints. A esta bolsa se le podrán añadir y sacar elementos, podremos saber cuántos hay, buscar uno en concreto y ver si está vacía. Sin embargo, C++ la guarda sin orden alguno (como su propio nombre nos indica) y no podremos tener elementos repetidos en dicha bolsa.

Para usar conjuntos desordenados en C++, habrá que importar el módulo <unordered_set> a nuestro programa. Para crear un conjunto desordenado, como cualquier otro objeto en C++, será necesario darle nombre. Siempre que creemos un conjunto desordenado estaremos creando un conjunto desordenado vacío. Podemos hacerlo de la siguiente manera:

unordered_set<int> conjuntoDesordenado;

En este ejemplo, el conjunto desordenado únicamente podrá guardar valores de tipo int. Los conjuntos desordenados podrán guardar objetos de una única clase, ya sea una creada por el usuario o una de la STL, como en este ejemplo.

Los conjuntos desordenados tienen una serie de operaciones que se pueden realizar con ellos:

• Añadir un elemento al conjunto: esto se hará mediante la operación insert(). Complejidad: O(1).
• Eliminar un elemento del conjunto: esto se hará mediante la operación erase(). Complejidad: O(1).
• Comprobar si un elemento está en el conjunto: esto se hará mediante la operación count(). Complejidad: O(1).
• Comprobar el tamaño del conjunto: esto se hará de la misma forma que con las pilas y montículos, es decir, mediante size() y empty(). Complejidad: O(1).

Al tener una complejidad O(1) en todas sus operaciones, los conjuntos desordenados (al igual que los mapas desordenados) son una opción muy atractiva para numerosos problemas. Para asegurarte de que lo has entendido bien, trata de predecir la salida del próximo fragmento de código antes de ejecutarlo en tu ordenador y comprobar así tu respuesta:

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

int main() {
    unordered_set<int> conjuntoDesordenado;
    conjuntoDesordenado.insert(1);
    conjuntoDesordenado.insert(2);
    cout << conjuntoDesordenado.size() << '\n';
    conjuntoDesordenado.erase(2);
    cout << conjuntoDesordenado.size() << '\n';
    conjuntoDesordenado.insert(1);
    conjuntoDesordenado.insert(3);
    if (conjuntoDesordenado.count(3)) cout << "Contiene 3\n";
    else cout << "No contiene 3\n";
    conjuntoDesordenado.erase(3);
    if (conjuntoDesordenado.empty()) {
        cout << "El conjunto desordenado no tiene elementos\n";
    } else{
        cout << "El conjunto desordenado tiene elementos\n";
    }
    return 0;
}

Problema para reforzar tus conocimientos: Distinct Numbers (CSES)

Problema reto: Team Tic Tac Toe (USACO Bronze)

Sección de ampliación: conjuntos con elementos repetidos

(Las secciones de ampliación son temas que pueden resultaros útiles pero que no están estrictamente dentro del temario de la semana, por lo que las podéis saltar y el manual se entenderá igual.)

En C++ también existen los conjuntos desordenados que permiten las repeticiones de elementos. Estos son los llamados unordered_multiset, también contenidos en el módulo <unordered_set>. Todas las operaciones y complejidades de unordered_sets explicadas ahora se les aplican, con la diferencia de que a la hora de eliminar elementos hay que tener cuidado de tener en cuenta si nos interesa eliminar una ocurrencia del elemento o todas.

Si nos interesa eliminar todas, basta usar erase() como en el ejemplo anterior. Sin embargo, si nos interesa eliminar una única ocurrencia, tendremos que hacer erase(find()). El próximo ejemplo igual lo explica con mayor claridad:

#include <iostream>
#include <unordered_set>

using namespace std;

int main() {
    unordered_multiset<int> conjunto;
    conjunto.insert(1);
    conjunto.insert(1);
    conjunto.insert(2);
    conjunto.insert(2);
    conjunto.erase(1);
    conjunto.erase(conjunto.find(2));
    if (conjunto.count(1)) cout << "Tiene un 1\n";
    else cout << "No tiene ningún 1\n";
    if (conjunto.count(2)) cout << "Tiene un 2\n";
    else cout << "No tiene ningún 2\n";
    return 0;
}

No es una estructura de datos que caiga con frecuencia, y siempre se puede simular con un mapa desordenado, pero siendo tan similar a un conjunto ordenado en cuanto a los nombres de las operaciones y cómo usarlos, valía la pena mencionarlos y que los tuvierais en vuestra caja de herramientas como programadores.

Mapas desordenados (unordered maps)

Los mapas desordenados (unordered maps) son la forma de C++ de representar una bolsa con parejas de (nombre, valor), como podría ser una bolsa de (nombre de futbolista, equipo en el que juega). Normalmente se utilizan para guardar alguna propiedad de cada nombre, ligándola así a este. A esta bolsa se le podrán añadir y sacar elementos, podremos saber cuántos hay, buscar un nombre en concreto y ver si está vacía. Sin embargo, C++ la guarda sin orden alguno (como su propio nombre nos indica) y no podremos tener nombres repetidos (pero sí valores) en dicha bolsa.

Para usar mapas desordenados en C++, habrá que importar el módulo <unordered_map> a nuestro programa. Para crear un mapa desordenado, como cualquier otro objeto en C++, será necesario darle nombre. Siempre que creemos un mapa desordenado estaremos creando un mapa desordenado vacío. Podemos hacerlo de la siguiente manera:

unordered_map<int, string> mapaDesordenado;

En este ejemplo, el mapa desordenado únicamente podrá guardar nombres de tipo int y valores de tipo string. Los mapas desordenados podrán guardar nombres y valores de una única clase, ya sea una creada por el usuario o una de la STL, como en este ejemplo.

Los mapas desordenados tienen una serie de operaciones que se pueden realizar con ellos:

• Añadir una pareja de (nombre, valor) al conjunto: esto se hará con el comando mapa[nombre] = valor. Este comando también se podrá usar para cambiar el nombre ligado a un valor. Complejidad: O(1).
• Eliminar un elemento del conjunto: esto se hará mediante la operación erase(). Complejidad: O(1).
• Comprobar si un elemento está en el conjunto: esto se hará mediante la operación count(). Complejidad: O(1).
• Encontrar el valor ligado a un nombre: basta con usar mapa[nombre]. Complejidad: O(1).
• Comprobar el tamaño del conjunto: esto se hará de la misma forma que con las pilas y montículos, es decir, mediante size() y empty(). Complejidad: O(1).

Al tener una complejidad O(1) en todas sus operaciones, los mapas desordenados (al igual que los conjuntos desordenados) son una opción muy atractiva para numerosos problemas. Para asegurarte de que lo has entendido bien, trata de predecir la salida del próximo fragmento de código antes de ejecutarlo en tu ordenador y comprobar así tu respuesta:

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

int main() {
    unordered_map<int, string> mapaDesordenado;
    mapaDesordenado[1] = "Plan";
    mapaDesordenado[2] = "ta";
    cout << mapaDesordenado[1] << '\n';
    mapaDesordenado[1] = "Mar";
    cout << mapaDesordenado[1] << mapaDesordenado[2] << '\n';
    cout << mapaDesordenado.size() << '\n';
    mapaDesordenado.erase(2);
    cout << mapaDesordenado.size() << '\n';
    mapaDesordenado[3] = "abc";
    if (mapaDesordenado.count(3)) cout << "Contiene el nombre 3\n";
    else cout << "No contiene el nombre 3\n";
    return 0;
}

Problema para reforzar tus conocimientos: Liga de pádel (Acepta el reto)

Problema reto: Cities and States (USACO Silver)

Sección de ampliación: cómo funcionan las estructuras ordenadas en detalle

(Las secciones de ampliación son temas que pueden resultaros útiles pero que no están estrictamente dentro del temario de la semana, por lo que las podéis saltar y el manual se entenderá igual.)

Por detrás, los mapas y conjuntos desordenados son hash tables y hash sets respectivamente. Puedes saber más sobre qué significa esto aquí.

Sección de ampliación: cómo hacer que tus códigos sean algo más rápidos

(Las secciones de ampliación son temas que pueden resultaros útiles pero que no están estrictamente dentro del temario de la semana, por lo que las podéis saltar y el manual se entenderá igual.)

Aprenderemos en detalle por qué ocurre esto en el manual sobre análisis amortizado, pero por ahora te puede ser útil saber que si estimas que tu conjunto/mapa desordenado (este truco no sirve para los ordenados) albergará en torno a n elementos (este número lo puedes sacar mirando las restricciones del problema), hacer conjunto.reserve(K) o mapa.reserve(K), siendo K una potencia de 2 cercana a n, antes de empezar a añadir elementos podrá ser la diferencia entre un TLE y un AC.

Este es el segundo artículo del manual del entrenamiento intermedio sobre Estructuras de datos de la STL. El siguiente a leer de esta unidad es C++ Mapas (maps) y conjuntos (sets) ordenados.