Para una lista vinculada simple en la que el acceso aleatorio a los elementos de la lista no es un requisito, ¿hay ventajas significativas (de rendimiento o de otro tipo) para usar std::list en lugar de std::vector? Si se requiere un recorrido hacia atrás, ¿sería más eficiente utilizar std::slist y reverse() la lista antes de iterar sobre sus elementos?Rendimiento relativo de std :: vector vs. std :: list vs. std :: slist?
Como siempre, la mejor respuesta a las preguntas sobre el rendimiento es profile, ambas implementaciones para su caso de uso y vea cuál es más rápido.
En general, si usted tiene inserciones en la estructura de datos (que no sea al final), entonces vector puede ser más lenta, si no en la mayoría de los casos se espera vector para llevar a cabo mejor que list aunque sólo sea por data locality issues, esto significa que si dos los elementos que están adyacentes en el conjunto de datos son adyacentes en la memoria, entonces el siguiente elemento ya estará en la memoria caché del procesador y no tendrá que paucar la memoria en la memoria caché.
también tener en cuenta que la sobrecarga de espacio para un vector es constante (3 punteros) mientras que la sobrecarga de espacio para un list se paga por cada elemento, esto también reduce el número de elementos completos (datos más generales) que puede residir en el caché en cualquier momento.
Tenga en cuenta también que incluso las inserciones son más rápidas en un vector que en una lista vinculada si debe buscarse la ubicación para insertar.Por ejemplo, tomar un montón de enteros aleatorios e insertarlos en orden en un vector o una lista vinculada: el vector siempre será más rápido, independientemente de la cantidad total de elementos, debido a errores de caché al buscar el punto de inserción en la lista enlazada – Collin
Más o menos el único lugar donde una lista vinculada es más rápida es cuando está haciendo un montón de empalmes, ya que eso no implica una gran cantidad de fallas de caché, y cada empalme es una operación de tiempo constante (que puede mover un gran número de elementos de una lista vinculada a otra). – Collin
"También tenga en cuenta que el espacio por encima de un vector es constante" Solo si tiene mucho cuidado. Para uso casual, tiene una sobrecarga de espacio lineal, igual que una 'lista'. Ver: push_back lineal amortizado. –
Simplemente no. La lista tiene ventajas sobre Vector, pero el acceso secuencial no es uno de ellos, si eso es todo lo que estás haciendo, entonces un vector es mejor.
Sin embargo ... un vector es más caro para agregar elementos adicionales que una lista, especialmente si se está insertando en el medio.
Comprender cómo se implementan estas colecciones: un vector es una matriz secuencial de datos, una lista es un elemento que contiene los datos y punteros a los siguientes elementos. Una vez que comprenda eso, comprenderá por qué las listas son buenas para inserciones y malas para el acceso aleatorio.
(así, iteración inversa de un vector es exactamente el mismo que para la iteración hacia adelante - el iterador solo resta el tamaño de los elementos de datos cada vez, la lista todavía tiene que saltar al siguiente elemento a través del puntero)
Esta es la respuesta correcta, y 99% del tiempo, correcta. Si necesita un recorrido hacia atrás, ejecute su ciclo for hacia atrás. Las matrices/vectores proporcionan acceso aleatorio, acceso secuencial muy rápido y acceso secuencial igualmente rápido desde cualquier punto de inicio aleatorio en el vector. Las listas que me gustan tienen solo un fuerte ', y eso es eliminar miembros o insertar miembros en algún punto de la lista. Ellos casi apestan por todo lo demás. Lento, lento, lento. Hacer crecer una matriz/vector es tan fácil como un nuevo malloc() y memmove(). Usando Vprime, Vgrow, puede reasignarlos y copiarlos de un lado a otro. – RocketRoy
Si necesita un recorrido hacia atrás, es poco probable que una ranura sea la estructura de datos para usted.
Una lista convencional (doblemente) vinculada le proporciona un tiempo constante de inserción y eliminación en cualquier lugar de la lista; un vector solo da inserción y eliminación de tiempo constante amortizado al final de la lista. Para un vector de inserción y el tiempo de eliminación es lineal en cualquier lugar que no sea el final. Esta no es toda la historia; también hay factores constantes. Un vector es una estructura de datos más simple que tiene ventajas y desventajas según el contexto.
La mejor manera de entender esto es comprender cómo se implementan. Una lista vinculada tiene un puntero siguiente y uno anterior para cada elemento. Un vector tiene una matriz de elementos direccionados por índice. De esto se puede ver que ambos pueden hacer avances y retrocesos eficaces, mientras que solo un vector puede proporcionar un acceso aleatorio eficiente. También puede ver que la sobrecarga de memoria de una lista vinculada es por elemento, mientras que para el vector es constante. Y también puede ver por qué el tiempo de inserción es diferente entre las dos estructuras.
Un punto importante es que las listas tienen punteros adicionales por elemento, mientras que un vector solo tiene tres punteros para toda la estructura de datos. – Motti
Sí, eso es cierto: mi respuesta dice: "Una lista vinculada tiene un puntero anterior para cada elemento. Un vector tiene una matriz de elementos direccionados por índice". Claramente, falta la palabra "y" (!) Y voy a aclarar los punteros adicionales. – janm
Ver esta pregunta para obtener más información acerca de los costos:
What are the complexity Guarantees of the standard containers
Si usted tiene una slist y ahora quiere realizar el desplazamiento en sentido inverso por qué no cambiar el tipo de enumerar todas partes?
estructura de datos por defecto para pensar en C++ es el Vector.
considerar los siguientes puntos ...
1] Transversal:
nodos de lista se encuentran dispersos por todas partes en la memoria y, por tanto, la lista de recorrido conduce a caché no alcanza. Pero el cruce de vectores es suave.
2] inserción y supresión:
media de 50% de elementos debe ser desplazado cuando se hace eso a un vector, pero cachés son muy buenos en eso! Pero, con listas, necesita recorrer hasta el punto de inserción/eliminación ... así que de nuevo ... caché falla! ¡Y sorprendentemente los vectores ganan este caso también!
3] Almacenamiento:
Cuando se utiliza listas, hay 2 punteros por elementos (hacia adelante & hacia atrás) lo que una lista es mucho más grande que un vector! Los vectores necesitan solo un poco más de memoria que los elementos reales.
Yout debe tener una razón para no usar un vector.
Creo que te refieres a la falta de caché, pero como desarrollador de juegos independientes, el código que escribo también ha tenido algunas fallas de efectivo. –
http://java.dzone.com/articles/c-benchmark-%E2%80%93-stdvector-vs Kindof dice lo mismo que Bjarne, pero con mejores números y código fuente para las pruebas. – gulgi
@gulgi, ese enlace merece una respuesta por separado, no solo un comentario. Sería bueno tener el gráfico y las breves explicaciones aquí en Stackoverflow. –
Algunos puntos de referencia rigurosos sobre el tema: http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html
Como se ha señalado por otros, significa std almacenamiento de memoria contigua: : vector es mejor para la mayoría de las cosas. Prácticamente no existe una buena razón para usar std :: list, excepto para pequeñas cantidades de datos (donde todos pueden caber en la caché) y/o donde el borrado y la reinserción son frecuentes. Las garantías de complejidad no se relacionan con el rendimiento en el mundo real debido a la diferencia entre la memoria caché y las velocidades de memoria principal (200x) y cómo el acceso de memoria contigua afecta el uso de la memoria caché. Ver Chandler Carruth (Google) hablar sobre el tema aquí: https://www.youtube.com/watch?v=fHNmRkzxHWs
y datos de Mike Acton Diseño Orientado a hablar aquí: https://www.youtube.com/watch?v=rX0ItVEVjHc
(finales de comentario, sólo para el registro): Enlace a una conferencia por Bjarne Stroustrup: "Por qué deberías evitar las listas vinculadas", donde afirma que los vectores siempre son mejores que las listas. La razón que da es que, en promedio, la búsqueda del punto de inserción domina el esfuerzo, y el desplazamiento de los elementos (en vectores) es insignificante * en comparación *. Además, el caché falla, pero eso ya se menciona en la respuesta siguiente. Video: http://www.youtube.com/watch?v=YQs6IC-vgmo –
Aunque la lista es casi siempre más lenta que el vector (excepto cuando se realizan altos niveles de splicing) hay una vez que NECESITA absolutamente una lista: estable iteradores. Si necesita conservar copias de los iteradores que siempre apuntarán al mismo elemento (a menos que se eliminen), esto no es una garantía que puede proporcionar el vector (por ejemplo, una llamada a push_back puede invalidar todos los iteradores). El uso de agrupaciones de memoria puede obtener la velocidad de una lista mucho más cercana a la de un vector. – coderforlife