Representación de conjuntos (Set)

• Conocimientos mínimos: nociones básicas de complejidad
• Conocimientos recomendados: Búsqueda binaria

Un problema común a enfrentar a la hora de resolver un problema es saber si un elemento está en un conjunto o no. Por ejemplo, si cierto elemento está en la lista de elementos visitados (muy útil para algoritmos como BFS o DFS) o más en general si un número se encuentra en una lista de números. Más aún, muchas veces debemos responder a esta pregunta numerosas veces durante la ejecución del programa, así que es importante que lo podamos hacer rápidamente.

Plantearemos un problema y veremos diferentes formas de resolverlo. Imaginemos que tenemos un idioma en el cual existe una lista de palabras válidas, y el resto de las palabras no lo son. Queremos hacer un programa que resuelva muy rápidamente si algunas palabras son válidas o no.

Por ejemplo, si la lista de palabras válidas es:

            {casa, pato, luna, comida, la, el, un, firma, sistema, lapicera}

y las palabras que quiero saber si son válidas son: firma, melanie, los, pato, una forma de saber si cada palabra es válida sería recorrer toda la lista. Si llegamos al final de la misma sin encontrar la palabra, significa que no es válida. Si la encontramos, sabremos que es válida y podemos parar la búsqueda allí. Esta sería una forma correcta de resolver el problema pero demoraría mucho tiempo: para cada elemento que queremos saber si está en la lista, hay que recorrerla entera. Si la lista es larga y tengo muchos elementos para preguntar, este enfoque se hace impracticable. Por lo tanto, es $O(n)$ cada búsqueda si hay $n$ palabras válidas. Si hay $m$ búsquedas para hacer, da una complejidad total de $O(n \cdot m)$.

Otra forma de resolver el problema sería ordenar la lista y hacer búsqueda binaria en ella. Así, cada búsqueda tomaría $O(\log n)$ en vez de $O(n)$, lo que nos daría un costo total de $O(m \log n)$ si sumamos todas las búsquedas. No olvidemos que tuvimos que ordenar la lista (que toma $O(n \log n)$ si tiene n elementos), así que el costo final será de $O(n \log n + m \log n)$.

Esta solución es muy buena, porque por ejemplo si tuviéramos $n = m = 1000000$, la primera solución usaría aproximadamente $1000000000000$ operaciones mientras que la segunda solo $20000000$.

Ahora bien, imaginemos que la lista de palabras no está fija, porque la real academia de este idioma va agregando palabras nuevas y removiendo otras. Ahora no solo tendremos que resolver el problema que teníamos antes, sino que además deberemos ir cambiando la lista de palabras. Como para poder usar búsqueda binaria nuestra lista tiene que estar ordenada, eso significa que con cada palabra nueva tenemos que volver a ordenarla (para pensar: no hace falta llamar al sort de C++ y pagar un costo de $O(n \log n)$ cada vez, porque podemos resolverlo en $O(n)$. Se imaginan cómo?). Así, volvimos a una solución muy lenta como la primera que habíamos discutido (ambas serán $O(n \cdot m)$ para esta nueva versión del problema).

Neceistamos una mejor solución para esto. Queremos encontrar una estructura de datos que permita

• Insertar un elemento rápidamente
• Buscar un elemento rápidamente
• Borrar un elemento rápidamente

Por suerte, C++ ya tiene implementada una estructura que hace todo esto en $O(\log n)$! No explicaremos cómo está programada internamente esta estructura pero sí aprenderemos a usarla, que es lo que necesitaremos.

La estructura que veremos se llama set, que significa conjunto en inglés. Se encuentra en la biblioteca set, por lo que al comienzo de nuestro programa deberemos incluirla así: #include <set>.

Veamos cómo realizar cada una de las operaciones prometidas.

Para crear un set, debemos indicar de qué tipo serán los elementos contenidos. Es importante notar que todos los elementos que se inserten deberán ser de un mismo tipo. En nuestro ejemplo, como tenemos un conjunto de palabras, será un set de strings. Se define así:

set<string> miSet;

En este punto, miSet no contiene ningún elemento pero ya está listo para ser usado.

Para insertar un elemento usamos el método insert, y entre paréntesis pasamos el elemento a insertar. Notemos que también podemos pasar una variable definida anteriormente.

string a = "luna";
miSet.insert("casa");
miSet.insert("pato");
miSet.insert(a);
...

Esto dará como resultado un conjunto con los elementos {casa, pato, luna}. El mismo conjunto podría haberse obtenido directamente indicando los elementos entre llaves al declarar la variable:

string a = "luna";
set<string> miSet2 = {a, "casa", "pato"};

Notar que, a diferencia de lo que ocurre con los vectores, que guardan listas, set guarda un conjunto de elementos, sin importar el orden. Por lo tanto, miSet2 == miSet, aunque los elementos se vayan agregando en otro orden.

Para borrar un elemento, el procedimiento es muy similar. Usamos el método erase y le pasamos el elemento a ser borrado.

string a = "luna";
miSet.erase(a);
miSet.erase("casa");
...

Ahora el conjunto tiene solo un elemento, pato.

Para buscar un elemento, lo buscaremos en toda la estructura con el méotdo 'find' y si paramos antes de llegar al final, significa que el elemento está en ella. El final del conjunto es representado por 'end'.

string x = "olimpiada";
...
if (miSet.find(x) != miSet.end()) {
    cout << "la palabra" << x << " es una palabra valida" << endl;
}
else {
    cout << "la palabra" << x << " no es una palabra valida" << endl;
}

Así, con este condicional podemos decidir qué código ejecutaremos dependiendo de si el elemento está en el conjunto o no.

Existe más de una forma de recorrer los elementos de un set. Veremos la que fue introducida en C++11 pues es la más simple, pero si conocen qué es un iterador, pueden ver otra forma de recorrer todos los elementos del set aquí.

for (string x : miSet) {
  // hacer lo que haga falta
}

Esto literalmente significa “para cada string x en miSet, hago lo que indica el cuerpo del for”.

• Saber si el set está vacío: miSet.empty() devuelve true si el conjunto está vacío y false si no.
• Vaciar el set: miSet.clear() remueve todos los elementos del set, dejándolo vacío.

Para más detalles, todas las operaciones están disponibles en http://www.cplusplus.com/reference/set/set/. Ahí se aclara la complejidad de cada operación y hay más ejemplos de código. Está en inglés.

Existe también multiset, que tiene operaciones prácticamente iguales a set, pero con la diferencia de que multiset permite elementos repetidos, a diferencia de set, que no puede nunca tener más de una copia de un mismo valor (y si se agrega un elemento que ya está en un set, no ocurre nada, en lugar de agregarse otra copia más).

[Dar ejemplos]