¿Cuándo se debe usar vector / list?

17

Puedo entender cuándo usar listas, pero no entiendo cuándo es mejor usar vectores que usar listas en videojuegos: ¿cuándo es mejor tener acceso aleatorio rápido?

(Y entiendo por qué es más rápido insertar / eliminar en listas porque simplemente elimina / agrega punteros, pero aún tiene que encontrar el elemento correspondiente ...)

c++ algorithm data-structure jokoon
fuente
Vuelva a agregar la etiqueta de vector a esto: si la lista es una etiqueta válida, entonces el vector también lo es.
Kylotan
Presumiblemente, el vector se eliminó porque se usa para significar vector matemático, no std :: vector.
1
¿Qué tal si los rechazamos a los dos y los ponemos container?
deft_code
@Kylotan: Es como dijo Joe. Esta pregunta definitivamente era sobre vectores, pero no pertenecía a la etiqueta del vector.
doppelgreener
1
Entonces, ¿eliminamos cualquier etiqueta ambigua? Eso me parece una decisión equivocada: mejor que su búsqueda arroje demasiada información que no suficiente. Omitir resultados no deseados es más fácil que buscar ideas para encontrar sinónimos.
Kylotan

Respuestas:

29

Mi regla general, y estoy seguro de que habrá un debate sobre esto, es nunca usar listas (a menos que necesite eliminar con mucha frecuencia las cosas del medio de las listas grandes).

La velocidad que obtendrá al tener todos sus elementos en su contenedor en la memoria contigua (y, por lo tanto, más amigable con la memoria caché) vale la compensación de los costos adicionales de agregar / eliminar / cambiar el tamaño del vector.

Editar: solo para aclarar un poco más, por supuesto, debería ser evidente que cualquier tipo de pregunta "que es más rápida" debe probarse en cualquier plataforma con cualquier conjunto de datos pertinente a sus necesidades particulares. Si solo necesito una colección de elementos, simplemente uso vector (o deque, que es casi lo mismo) a menos que haya una buena razón para no hacerlo.

Tétrada
fuente
1
Creo que depende en gran medida de sus necesidades, si nunca necesita acceder a un elemento específico y solo necesita leerlos todos y agrega y elimina elementos con frecuencia, la lista es una mejor solución.
Frédérick Imbeault
11
@ Frédérick: Esa es la sabiduría estándar de C ++, pero también casi siempre está mal. Los vectores, especialmente cuando se trata de vectores de punteros (que casi siempre se usan para juegos), son extremadamente rápidos para eliminar cosas del medio: es tiempo lineal, pero es una sobrecarga muy pequeña por elemento. También es mucho más rápido iterar secuencialmente sobre un vector.
1
No estoy seguro de qué tipo de estructura está obteniendo exactamente: este tipo de optimización requiere ejemplos concretos para decir algo definitivamente. Por ejemplo, mi primera reacción a su caso de uso sería un conjunto desordenado, que permite una inserción, eliminación y búsqueda igualmente rápidas; en mi experiencia, los conjuntos son excelentes para objetos en editores. Pero como los editores tienen requisitos de rendimiento en tiempo real mucho más laxos, por ejemplo, está bien si responder a una pulsación del botón "Eliminar" lleva 1 / 20o de segundo o toma 1 / 2th de segundo el 10% del tiempo - este nivel de optimización También rara vez se aplica a ellos.
1
@ Frédérick Imbeault Modified no es un gran problema, es Add \ Remove que causa problemas. Desde agregar \ punto eliminado hasta el final del vector se copia para mantener el vector contiguo. Si el orden de los elementos no importa, puede intercambiar el elemento eliminado con el último elemento, luego abrirlo para eliminar y agregar al final para agregar.
stonemetal
44
Claro, tomar la dirección de un elemento en un vector y guardarlo no es seguro. Pero, en general, casi nunca haces eso, prefieres tener un vector de punteros de elementos y copiar el puntero (o algo similar).
Tetrad
8

Use una lista cuando la invalidación del iterador causada por la modificación de la mitad de su estructura de datos va a causar un problema, o necesita mantener sus elementos ordenados para que el truco de intercambio y pop para las eliminaciones rápidas de la colección intermedia no funcione y tenga un gran número de eliminaciones de colección media.

También puede considerar usar un Deque. Tiene características de rendimiento similares a un vector, pero no tiene la necesidad de memoria contigua del vector, y es un poco más flexible.

metal de piedra
fuente
+1 por ser la única persona que menciona las etiquetas: obtienes la memoria contigua y los beneficios de velocidad de búsqueda de los vectores, con inserción / eliminación rápida en ambos extremos.
5

Su elección debe reflejar sus necesidades. Todos los elementos de los vectores son continuos en la memoria y las listas tienen punteros a los elementos siguientes / anteriores para que cada uno tenga sus ventajas / desventajas:

Listas:

  • Cada elemento toma 2 enteros para señalar los elementos anteriores y siguientes, por lo que, comúnmente, son 8 bytes más para cada elemento en su lista
  • La inserción es lineal en el tiempo: O (n)
  • Eliminar es una operación constante: O (1)
  • Acceder al elemento x es lineal en el tiempo: O (n)

Vectores:

  • Necesita menos memoria (sin punteros a otros elementos, es un algoritmo matemático simple)
  • Eliminar es lineal en el tiempo: O (n)
  • El acceso al elemento x es constante: O (1) (Esto se debe a que los elementos son continuos en la memoria, por lo que es una simple operación matemática vectorPtr + (x * bytesOfTheType))
  • La inserción puede estar en tiempo lineal, pero lo más común es que sea una operación constante: O (1) (Esto se debe a que el vector en una matriz pero siempre reserva 2 veces su capacidad cuando la matriz está llena, por lo que la copia de la matriz no es frecuente)

Por lo tanto, la lista es mejor cuando su programa necesita agregar y eliminar elementos con frecuencia, pero nunca acceda (o raramente acceda) a un elemento en particular sin la necesidad de los otros antes. El vector debe usarse para un mejor tiempo de acceso, pero carece de eficacia cuando necesita eliminar o agregar elementos.

Consulte esta publicación en stackoverflow, presenta un gráfico realmente agradable con preguntas básicas sobre sus necesidades que lo lleva a un contenedor específico según sus respuestas:

/programming/366432/extending-stdlist

Frédérick Imbeault
fuente
3
Ese gráfico realmente necesita comenzar con un nodo "¿Está almacenando punteros y menos de mil? No -> vector".
Sí, tal vez tengas razón, no consideré el tipo almacenado, también debería analizarse.
Frédérick Imbeault
2

Por lo general, las listas se usan para estructuras como colas donde hay muchas operaciones de agregar y quitar. Ejemplo: una lista siempre cambiante de entidades que deberían actualizarse. La lista en sí solo contiene entidades en la pantalla y, por lo tanto, cambia con frecuencia.

Los vectores (o matrices) son más adecuados para una colección que no cambia tanto y donde necesita acceso rápido a elementos individuales dentro de la colección. Ejemplo: un mapa de mosaicos donde debe buscar mosaicos en un índice dado.

La opinión de Tetrads puede ser cierta, pero depende del lenguaje de programación que se use. Veo que etiquetaste tu pregunta c++, pero intenté darte una respuesta que no sea específica del idioma.

bummzack
fuente
Bueno, también podría haber puesto C en él, pero no hay tales contenedores en C, pero eso es algo en lo que pensar: ¿hay algún tibrary similar a STL para C?
jokoon
He usado glib ( library.gnome.org/devel/glib ) en el pasado, que implementa una serie de estructuras de datos estándar para C. Lo odiaba porque generalmente es demasiado detallado y desesperadamente quiere ser C ++, pero es maduro y estable.
0

En los juegos de consola nunca, nunca usamos std :: list porque:

  1. realiza asignaciones de memoria cada vez que agrega un nuevo elemento. Las asignaciones de memoria son lentas.
  2. Está lleno de punteros. Los punteros son malos. un puntero es un error de caché. una falla de caché es mala.

Incluso std :: vector está perdiendo favor en las consolas porque:

  1. a menudo solo le interesan, por ejemplo, las posiciones de todos los objetos. por ejemplo, si quieres colisionar los objetos entre sí, en cuyo caso no te importa cuál sea su color. por lo tanto, desea que todas las posiciones estén contiguas en la memoria y que los colores estén en otro lugar lejos, para evitar contaminar el caché. pero std :: vector requiere que almacene todo para cada objeto en una porción contigua de memoria (por ejemplo, posición y color). Por lo tanto, si realiza un trabajo que solo lee las posiciones, también debe leer todos los colores en el caché, incluso si no los usas Esto es un desperdicio.
bmcnett
fuente
55
@bmcnett "[] .. pero std :: vector requiere que almacene todo para cada objeto en una porción contigua de memoria" - eso no es una cuestión del contenedor, es una cuestión de su diseño de datos, puede tener todas las posiciones en un trozo continuo de memoria con un std :: vector:struct point{float x, y, z, w}; std::vector<point> positions;
Maik Semder
a mi escuela le va a encantar esto :)
jokoon
2
-1 porque esta respuesta no agrega nada a la lista frente a la discusión de vectores que ya está aquí, y su afirmación sobre la contaminación del vector en el caché es incorrecta, como dice Maik.
no entendiste mi reclamo. Nunca dije que entre todos los contenedores std :: vector es particularmente culpable de contaminar el caché. todos los contenedores, y de hecho incluso las matrices, son igualmente culpables de eso. std :: vector está cayendo en desgracia debido a que los objetos C ++ están cayendo en desgracia. C ++ exige que los datos de cada objeto sean contiguos en la memoria. puede evitarlo evitando objetos C ++, por ejemplo, usando std :: vector <position> como se mencionó anteriormente.
bmcnett
3
Excepto pointes un objeto C ++ (como es std::vector, como es algo tan simple como float). Sé la distinción que estás tratando de trazar, pero estás haciendo un mal trabajo al explicarla.