Diferencias

Muestra las diferencias entre dos versiones de la página.

--- cpp-avanzado:set [2017/02/09 14:26]
melanie
+++ cpp-avanzado:set [2017/12/28 00:10] (actual)
181.114.206.1 ↷ Links adapted because of a move operation
@@ Línea 1: / Línea 1: @@
-======Conjuntos y Diccionarios (Set y Map) ======
+====== Representación de conjuntos (Set) ======
-  * Conocimientos mínimos: nociones básicas de complejidad
+  * **Conocimientos mínimos**: nociones básicas de complejidad
-  * Conocimientos recomendados: búsqueda binaria
+  * **Conocimientos recomendados**: [[algoritmos-oia:busqueda-binaria|Búsqueda binaria]]
-===== Representación de conjunto (set) ======
+===== Motivación =====
-==== 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.
-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.
@@ Línea 17: / Línea 15: @@
               {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)$.
+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)$.
+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$.
@@ Línea 33: / Línea 31: @@
 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++ ====
+===== 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>''.
@@ Línea 39: / Línea 37: @@
 Veamos cómo realizar cada una de las operaciones prometidas.
-=== Crear un conjunto ===
+==== 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>
+<code cpp>
 set<string> miSet;
 </code>
@@ Línea 48: / Línea 46: @@
 En este punto, ''miSet'' no contiene ningún elemento pero ya está listo para ser usado.
-=== Insertar un elemento ===
+==== 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>
+<code cpp>
 string a = "luna";
 miSet.insert("casa");
@@ Línea 60: / Línea 58: @@
 </code>
-Esto dará como resultado un conjunto con los elementos ''{casa, pato, luna}''.
+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:
-=== Borrar un elemento ===
+<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>
+<code cpp>
 string a = "luna";
-miSet.remove(a);
+miSet.erase(a);
-miSet.remove("casa");
+miSet.erase("casa");
 ...
 </code>
@@ Línea 76: / Línea 80: @@
-=== Buscar un elemento ===
+==== 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>
+<code cpp>
 string x = "olimpiada";
 ...
 if (miSet.find(x) != miSet.end()) {
-    cout << "la palabra << x << " es una palabra valida" << endl;
+    cout << "la palabra" << x << " es una palabra valida" << endl;
 }
 else {
-    cout << "la palabra << x << " no es una palabra valida" << endl;
+    cout << "la palabra" << x << " no es una palabra valida" << endl;
 }
 </code>
@@ Línea 93: / Línea 97: @@
 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 ===
+==== 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 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í]].
+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>
+<code cpp>
 for (string x : miSet) {
   // hacer lo que haga falta
@@ Línea 105: / Línea 109: @@
 Esto literalmente significa "para cada string x en miSet, hago lo que indica el cuerpo del for".
-=== Otras operaciones ===
+==== Otras operaciones ====
   * **Saber si el set está vacío**: ''miSet.empty()'' devuelve ''true'' si el conjunto está vacío y ''false'' si no.
@@ Línea 112: / Línea 116: @@
 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

Diferencias

Herramientas de la página