¿Cómo es la supresión aleatoria de un std::vector es más rápido que un std::list?

Question

¿Cómo es que la supresión aleatoria de un std::vector es más rápido que un std::list?Lo que estoy haciendo para aumentar su velocidad es intercambiar el elemento aleatorio con la última y, a continuación, eliminar el último.Yo habría pensado que la lista será más rápido ya que la supresión aleatoria es lo que fue construido para.

for(int i = 500; i < 600; i++){
    swap(vector1[i], vector1[vector1.size()-1]);
    vector1.pop_back();
}

for(int i = 0; i < 100; i++){
        list1.pop_front();
}

Los resultados (en segundos):
Vec intercambio eliminar:0.00000909461232367903
Lista normal de eliminar:0.00011785102105932310

Answer 1

Lo que está haciendo no es aleatoria, aunque eliminación. Que está eliminando del final, que es lo que los vectores se construyen para (entre otras cosas).

Y cuando el canje, que está haciendo una sola operación de indexación al azar, que es también lo que los vectores son buenos.

Answer 2

La diferencia entre std::list y std::vector no es simplemente bajar el rendimiento.También tienen diferentes iterador de la invalidación de la semántica.Si usted borra un elemento de una std::list, todos los iteradores apuntando a otros elementos en la lista siguen siendo válidos.No es así con std::vector, donde el borrado de un elemento invalida todos los iteradores señalando después de ese elemento.(En algunas implementaciones, que aún puede servir como válidos los iteradores, pero de acuerdo a la norma que ahora son inservibles, y una comprobación de la aplicación debe afirmar si usted trata de usar.)

Por lo que la elección del recipiente es también que ver con lo que la semántica se requieren.

Answer 3

Eso no es al azar. Trate vector1.erase (vector.begin () + rand ()% vector.size ()); en su lugar.

Answer 4

La lista erase hará que eliminar el elemento de la lista de borrado, esto va a invocar una llamada al operador delete. El borrado de vectores que nos provoca un intercambio y luego un decremento número entero -. Esto es mucho más rápido

Answer 5

En realidad, si desea más aceleraciones que debiera elementos de índice en el vector a través de iteradores . Ellos son conocidos por tener un mejor rendimiento para algunas arquitecturas.