c++ - librerias - ¿Cuál es la diferencia entre std:: set y std:: vector?

stl class c++

Question

Estoy aprendiendo STL ahora. Leí sobre set contenedor. Tengo una pregunta cuando quieres usar set ? Después de leer la descripción del conjunto , parece que es inútil porque podemos sustituirlo por un vector . ¿Podrías decir pros y cos para contenedores vector vs set ? Gracias

Answer 1

Se ordena un set . Se garantiza que 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á.

Un vector tiene exactamente y solo la ordenación que le das explícitamente. Los elementos en un vector son donde los pones. Si los pone fuera de servicio, entonces están fuera de servicio; ahora necesita sort el contenedor para volver a ponerlos en orden.

Es cierto que el set tiene un uso relativamente limitado. Con la disciplina adecuada, uno podría insertar elementos en un vector y mantenerlos ordenados. Sin embargo, si constantemente está insertando y eliminando elementos del contenedor, vector se encontrará con muchos problemas. Se hará una gran cantidad de copia / movimiento de elementos y así sucesivamente, ya que en realidad 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 elemento en un set es proporcional al registro de la cantidad de elementos. Si la cantidad de artículos es grande, es una gran diferencia. log₂ (100,000) es ~ 16; Esa es una gran mejora en la 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 el vector , ordenarlo (pagando ese precio una vez), y luego usar algoritmos estándar para los vectors ordenados para encontrar elementos e iterar sobre la lista ordenada. Y mientras que la iteración sobre los elementos de un set no es exactamente lenta, iterar sobre un vector es más rápida.

Así que hay casos en que un vector ordenado vence a un set . Dicho esto, realmente no debería preocuparse por el gasto de este tipo de optimización a menos que sepa que es necesario. Entonces use un set menos que tenga experiencia con el tipo de sistema que está escribiendo (y, por lo tanto, sepa que necesita ese rendimiento) o tenga datos de perfiles en la mano que le indiquen que necesita un vector y no un set .

Answer 2

Son cosas diferentes: 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 ordenamiento), y no puede colocar varios elementos iguales en un conjunto.

Por supuesto, podría mantener un vector de elementos únicos, pero su rendimiento se vería muy afectado al realizar operaciones orientadas a la configuración. Por ejemplo, suponga que tiene un conjunto de 10000 artículos y un vector de 10000 artículos 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 está entre los elementos, la búsqueda del vector sería 100 veces más lenta. Vería diferencias de rendimiento similares en el cálculo de uniones e intersecciones de conjuntos.

Para resumir, 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 dañaría el rendimiento bastante severamente.

Answer 3

es más rápido buscar un elemento en un conjunto que un vector (O (log (n)) vs O (n)). Para buscar un elemento contra un vector, debe iterar todos los elementos en el vector, pero el conjunto usa el árbol rojo-negro para optimizar la búsqueda, solo se buscará un elemento 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 el orden invertido.

Pero el vector no está ordenado, puede desplazarse por el orden de inserción.

Answer 4

formar conjunto cpluplus.com :

Los conjuntos son contenedores que almacenan elementos únicos siguiendo un orden específico.

por lo que el conjunto está ordenado y el artículo está representado de forma única

mientras que vect:

Los vectores son contenedores de secuencia que representan matrices que pueden cambiar de tamaño.

así que el vector está en el orden en que lo rellenas Y puede contener múltiples elementos idénticos

prefiera el conjunto

• Si desea filtrar múltiples valores idénticos.
• si desea analizar los elementos en un orden específico (hacer esto en vector requiere ordenar específicamente vector).

prefiero vector:

• Si quieres mantener valores idénticos.
• si desea analizar los elementos en el mismo orden en que los empujó (asumiendo que no procesa el orden vectorial)