Estoy aprendiendo STL ahora. Leí sobre el contenedor set. Tengo alguna pregunta cuando quieres usar set? Después de leer description of set, parece inútil porque podemos sustituirlo por vector. ¿Podría decir pros y cos para contenedores vector vs set? Gracias¿Cuál es la diferencia entre std :: set y std :: vector?
A set se ordena. Es garantizado para permanecer en un pedido específico, de acuerdo con un functor que usted proporcione. No importa qué elementos agregue o elimine (a menos que agregue un duplicado, que no está permitido en un set), siempre se ordenará.
A vector tiene exactamente y solo el orden que usted le da explícitamente. Los artículos en un vector son donde los pones. Si los pones fuera de servicio, entonces están fuera de servicio; ahora necesita sort el contenedor para ponerlos nuevamente en orden.
Es cierto que set tiene un uso relativamente limitado. Con la disciplina adecuada, uno puede insertar elementos en un vector y mantenerlo ordenado. Sin embargo, si constantemente inserta y elimina elementos del contenedor, vector se encontrará con muchos problemas. Hará una gran cantidad de copia/movimiento de elementos y demás, ya que es solo una matriz.
El tiempo que se tarda en insertar un elemento en un vector es proporcional al número de elementos que ya están en el vector. El tiempo que lleva insertar un artículo en un set es proporcional al log₂ del número de elementos. Si la cantidad de artículos es grande, esa es una gran diferencia. log₂ (100,000) es ~ 16; esa es una gran mejora de velocidad. Lo mismo ocurre con la eliminación.
Sin embargo, si realiza todas las inserciones a la vez, en el momento de la inicialización, no hay problema. Puede insertar todo en vector, ordenarlo (pagando ese precio una vez) y luego usar algoritmos estándar para ordenar vectors para encontrar elementos e iterar sobre la lista ordenada. Y aunque la iteración sobre los elementos de un set no es exactamente lenta, iterar sobre un vector es más rápido.
Así que hay casos en que un vector ordenado supera un set. Dicho esto, realmente no debería molestarse con el gasto de este tipo de optimización a menos que sepa que es necesario. Por lo tanto, use un set a menos que tenga experiencia con el tipo de sistema que está escribiendo (y sepa que necesita ese rendimiento) o tenga datos de creación de perfiles que le indiquen que necesita un vector y no un set.
¿Pero no se pide el 'conjunto 'solo como un detalle de implementación? Matemáticamente hablando, un conjunto no tiene orden. –
@PaulManta: A 'std :: set' no está definido por las matemáticas; está definido por la especificación C++. Y la especificación indica que está ordenado. –
@NicolBolas: ¿Por qué es "El tiempo que se tarda en insertar un elemento en un vector es proporcional al número de elementos que ya están en el vector". ? - ¿Quiere decir usar insert() siempre e insertar no al final? ¿No puedes usar push_back() y agregarlo en O (1)? especialmente porque el usuario controla el pedido. –
Son diferentes cosas: usted decide cómo se ordenan los vectores, y también puede poner tantas cosas iguales en un vector como desee. Los conjuntos se ordenan de acuerdo con las reglas internas de ese conjunto (puede establecer las reglas, pero el conjunto se ocupará del orden), y no puede poner varios elementos iguales en un conjunto.
Por supuesto, podría mantener un vector de elementos únicos, pero su rendimiento sufriría mucho cuando realice operaciones orientadas a conjuntos. Por ejemplo, supongamos que tiene un conjunto de 10000 elementos y un vector de 10000 elementos desordenados distintos. Ahora suponga que necesita verificar si un valor X está entre los valores en el conjunto (o entre los valores en el vector). Cuando X no se encuentra entre los elementos, la búsqueda del vector sería 100 veces más lenta. Vería diferencias de rendimiento similares al calcular uniones e intersecciones establecidas.
En resumen, los conjuntos y vectores tienen diferentes propósitos. Puede usar un vector en lugar de un conjunto, pero requeriría más trabajo y probablemente perjudicaría el rendimiento de forma bastante severa.
+1 por singularidad. No puedo creer que nadie más se haya molestado en señalarlo. ¡para vergüenza! la singularidad es el principal beneficio. y no devaluar eso, pero incluso la facilidad concomitante de 'erase' /' emplace'.me lleva a utilizar '[unordered_] set', aunque en teoría podría ser más lento, aunque normalmente en partes de configuración donde la velocidad no es ¡Preocupación y solo me preocupa que apenas pueda leer el código más tarde! p.ej.quiero asegurarme de que un artículo se coloque en el contenedor, pero solo una vez; parece mucho mejor escribir 'set.emplace (it)' que 'if (vec.find (it)! = vec.end()) {vec.emplace (it)}' (y más aún para 'erase'!) –
es más rápido buscar un elemento en un conjunto que un vector (O (log (n)) vs O (n)). Para buscar un elemento en un vector, debe iterar todos los elementos en el vector, pero el conjunto utiliza un árbol rojo-negro para optimizar la búsqueda, solo se buscarán algunos elementos para encontrar una coincidencia.
El conjunto está ordenado, lo que significa que solo puede iterarlo desde el más pequeño al más grande por orden o en el orden inverso.
Pero el vector no está ordenado, puede desplazarse por el orden de inserción.
forma cpluplus.com conjunto:
conjuntos son contenedores que almacenan elementos únicos siguientes un orden específico.
por lo que el conjunto se ordena y el artículo están representados de forma única
mientras vect:
vectores son contenedores de secuencias que representan matrices que pueden cambiar en tamaño.
modo vector está en el orden que lo llena y puede contener varios artículos idénticos
prefieren establecer:
prefieren vectores:
Dado que ha leído sobre el conjunto, también lea el mapa. ¡Entonces intenta comparar de nuevo! –
[Elija su contenedor con cuidado] (https://docs.google.com/open?id=0B_ZAqgwpqtF4MjQ5NmNlM2ItNTQxNS00MmEyLWFiODctNDk4YTY5MDRlYzQz) –
@NicolBolas Edité el enlace. Sin embargo, me obligaste a hacer un trabajo extra: D –