c++ - reticula - tipos moviles gutenberg
¿Eliminar un elemento en el medio de un std:: vector sigue siendo caro con los tipos móviles? (5)
En general, se considera que eliminar un elemento en medio de un std::vector es costoso, ya que necesita copiar cada elemento para llenar el agujero.
Con C ++ 11, std::vector moverá todos los elementos hacia abajo, lo que debería ser muy rápido (aunque solo sea en relación con la copia), al menos eso creo. Seguirá siendo lineal en el tiempo, claro, pero en general debería ser más rápido que la versión anterior.
¿Será esto cierto? ¿Ya no tengo que preocuparme por borrar algún objeto en el medio?
Depende de lo que hay en el vector. Si se trata de un POD o puntero, no puedo imaginar que suponga alguna diferencia. Si se trata de instancias de clase que son difíciles de copiar, pero se pueden mover muy rápido, esperaría una aceleración con C ++ 0x.
Sin embargo, creo que si eliminar elementos del medio de std :: vectores es un cuello de botella en su código, es probable que C ++ 0x no sea el arreglo correcto. Considere las estructuras de datos que manejan mejor dichos casos en su lugar, o std::iter_swap plus std::vector::pop_back si el orden de los elementos no es importante.
Efectivamente, en la gran mayoría de los casos, será mucho más rápido mover que copiar. Cualquier tipo que tenga información almacenada por referencia que de otra manera tendría que ser copiada puede evitar la copia, por ejemplo, casi todos los contenedores, punteros inteligentes, etc., y cualquier clase que involucre esos tipos.
Por supuesto, este sigue siendo el tiempo lineal, por lo que si tienes un millón de ints, no irá más rápido. Sin embargo, mover cosas como contenedores y punteros inteligentes puede ser varios órdenes de magnitud más rápido que copiarlos.
El primer punto que, a punto de decidir que necesita un vector o lista? Si no desea un acceso basado en índices a la estructura de datos, la lista sería buena ya que las eliminaciones están sucediendo en el medio del contenedor. También debes considerar otras variantes como árboles para decidir lo mejor para ti. Puede que esto no afecte demasiado a su rendimiento, pero solo por el hecho de compartir información, existe la posibilidad de que el contenido de la lista se difunda en varios archivos de página y, por lo tanto, el rendimiento se verá comprometido al utilizar gran cantidad de datos.
El constructor de referencia y movimiento de Rvalue puede mejorar el rendimiento de los contenedores. Puede evitar varias operaciones de copia innecesarias, etc.
Si toma en cuenta lo que usa el estándar para el costo, será exactamente tan costoso. La norma establece los costos en términos de las operaciones realizadas en el tipo contenido, y ese número de operaciones sigue siendo el mismo, es solo que cada una de ellas será más rápida.
Como ejemplo, considere en C ++ 03 el costo de insertar un elemento en el medio de un vector<string> . El estándar llama a O(N) , donde N es el tamaño del vector, pero el costo real es O(N * M) donde M es el tamaño de las cadenas. La razón para ignorar la M al analizar el costo de las operaciones en los contenedores es que depende del elemento contenido. Ese costo en C ++ 0x con un tipo movible será O(N) (las cadenas se pueden mover a las nuevas posiciones), pero la complejidad anunciada será O(N) en ambos casos.
Para un simple contraejemplo, si considera que la inserción en el medio de un vector es una operación costosa en C ++ 03, y considera std::vector<int> , luego la inserción en el medio de un vector en C + + 0x es igual de caro, no hay aceleración en ese caso.
También tenga en cuenta que cualquier mejora potencial dependerá de que sus objetos sean móviles (lo que no es necesario que sean) y de que algunas de las implementaciones de STL actuales ya están optimizadas de forma similar (sin soporte de idiomas), por ejemplo, Dinkumware la implementación (creo que fue esta) tiene algunas optimizaciones por las cuales cuando un std::vector<std::vector<T> > crece, crea el nuevo almacenamiento e inicializa con vectores vacíos (que no tienen memoria asignada por lo que el costo es mínimo) y luego swap los vectores en las regiones asignadas antiguas y nuevas, implementando efectivamente la semántica de movimientos .
Todavía soy un novato con las cosas de mover de C ++ 0x, pero realmente no puedo ver cómo obtendrá aceleraciones útiles aquí que son inherentes al vector .
Todo se debe a su tipo de elemento: no puedo imaginar que obtendrá una aceleración a menos que los objetos de su tipo de elemento sean más rápidos de mover que de copiar .