OIA-Wiki

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
====== Representación de conjuntos (Set) ======

  * **Conocimientos mínimos**: nociones básicas de complejidad
  * **Conocimientos recomendados**: [[algoritmos-oia:busqueda-binaria|Búsqueda binaria]]


===== Motivación =====

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 [[algoritmos-oia:grafos:bfs|BFS]] o [[algoritmos-oia:grafos:dfs|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 [[algoritmos-oia:busqueda-binaria|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.

===== Implementación en C++ =====

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.

==== Crear un conjunto ====
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í:

<code cpp>
set<string> miSet;
</code>

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

==== Insertar un elemento ====

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.

<code cpp>
string a = "luna";
miSet.insert("casa");
miSet.insert("pato");
miSet.insert(a);
...
</code>

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:

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

Notar que, a diferencia de lo que ocurre con los [[curso-cpp:contenedor-vector|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.
==== Borrar un elemento ====

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

<code cpp>
string a = "luna";
miSet.erase(a);
miSet.erase("casa");
...
</code>

Ahora el conjunto tiene solo un elemento, ''pato''.


==== Buscar un elemento ====

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'.

<code cpp>
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;
}
</code>

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

==== Recorrer todos los elementos del set ====

Existe más de una forma de recorrer los elementos de un set. Veremos la que fue introducida en [[cpp-avanzado:c++11|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 [[http://www.cplusplus.com/reference/set/set/begin/|aquí]].

<code cpp>
for (string x : miSet) {
  // hacer lo que haga falta
}
</code>

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

==== Otras operaciones ====

  * **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.

==== Multiset ====

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).


FIXME[Dar ejemplos]
OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Herramientas de la página
