Diferencias

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

--- cpp-avanzado:set [2017/02/09 22:33]
santo [Motivación]
+++ cpp-avanzado:set [2017/12/28 00:10] (actual)
181.114.206.1 ↷ Links adapted because of a move operation
@@ Línea 2: / Línea 2: @@
   * **Conocimientos mínimos**: nociones básicas de complejidad
-  * **Conocimientos recomendados**: búsqueda binaria
+  * **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 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.
+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.
@@ Línea 40: / Línea 40: @@
 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 50: / Línea 50: @@
 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 58: / 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:
+<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 78: / Línea 84: @@
 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 99: @@
 ==== 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 110: / 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