una - C++ manera más rápida de borrar o borrar un vector

eliminar una posicion de un vector

Question

Tengo un código donde rutinariamente llene un vector con entre 0 y 5000 elementos. Sé que el máximo nunca excede de 5000. En lugar de inicializar el vector varias veces, me gustaría hacerlo solo una vez

vector<struct> myvector;
myvector.reserve(5000);

Sin embargo, para volver a llenar el vector, primero tengo que borrar el vector sin alterar su capacidad. Por lo general, llamo myvector.clear ();

Esta es una operación O (n). ¿Hay algo simple que pueda hacer para aumentar el rendimiento de esto o esto es lo mejor que obtendrá?

Answer 1

El costo de clear() depende en gran medida de lo que sean los objetos almacenados, y en particular si tienen un destructor trivial. Si el tipo no tiene un destructor trivial, la llamada debe destruir todos los objetos almacenados y, de hecho, es una operación O (n), pero no se puede hacer nada mejor.

Ahora, si los elementos almacenados tienen destructores triviales, entonces la implementación puede optimizar el costo y clear() convierte en una operación O (1) barata (simplemente reiniciando el puntero de tamaño - end ).

Recuerde que para comprender la complejidad asintótica necesita saber de qué se trata. En el caso de clear() representa la cantidad de destructores llamados, pero si el costo (oculto) es 0, entonces la operación es no operativa.

Answer 2

Si su estructura tiene un destructor no trivial, debe llamarse para todos los elementos del vector independientemente de cómo se haya vaciado. Si su estructura solo tiene un destructor trivial, el compilador o la implementación de la biblioteca estándar puede optimizar el proceso de destrucción y proporcionarle una operación O (1).

Answer 3

Todo lo que haga para eliminar los elementos existentes del vector debe invocar (potencialmente) el destructor de cada elemento que se destruye. Por lo tanto, desde el punto de vista del contenedor, lo mejor que puede esperar es la complejidad lineal.

Eso solo deja la pregunta de qué tipo de artículos almacenas en el vector. Si almacena algo como int que el compilador puede / sabrá con anticipación no tiene un destructor para invocar, las posibilidades son al menos bastante buenas de que la eliminación termine con una complejidad constante.

Sin embargo, dudo que cambiar la sintaxis (p. Ej., clear() contra resize() vs. erase(begin(), end()) haga una diferencia significativa. La sintaxis no cambia el hecho de que (en ausencia de subprocesamiento) invocar N destructores es una operación O (N).