Muestra las diferencias entre dos versiones de la página.
Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
cpp-avanzado:set [2017/10/29 19:32] santo |
cpp-avanzado:set [2017/12/28 00:10] (actual) 181.114.206.1 ↷ Links adapted because of a move operation |
||
---|---|---|---|
Línea 7: | Línea 7: | ||
===== 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 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. | 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 88: | Línea 88: | ||
... | ... | ||
if (miSet.find(x) != miSet.end()) { | 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 { | else { | ||
- | cout << "la palabra << x << " no es una palabra valida" << endl; | + | cout << "la palabra" << x << " no es una palabra valida" << endl; |
} | } | ||
</code> | </code> | ||
Línea 116: | 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. | 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] |