Entiendo que la complejidad de la operación clear() es lineal en el tamaño del contenedor, ya que se debe invocar a los destructores. Pero, ¿qué hay de los tipos primitivos (y POD)? Parece que lo mejor sería establecer el tamaño del vector en 0, para que la complejidad sea constante.¿Cuál es la complejidad de std :: vector <T> :: clear() cuando T es un tipo primitivo?
Si esto es posible, ¿también es posible para std :: unordered_map?
La versión de gcc de std::_Destroy, que es lo que finalmente usa clear(), intenta aplicar una plantilla sobre si el tipo tiene un destructor trivial, por lo que en ese caso la complejidad es constante incluso sin una aprobación de optimización. Sin embargo, no sé qué tan bien funciona la plantilla.
Parece que lo mejor sería establecer el tamaño del vector en 0, para que la complejidad sea constante.
En general, la complejidad de resizing a vector to zero es lineal en el número de elementos almacenados actualmente en el vector. Por lo tanto, establecer el tamaño vector en cero no ofrece ninguna ventaja sobre la llamada clear() - los dos son esencialmente iguales.
Sin embargo, al menos una implementación (libstdC++, fuente en bits/stl_vector.h) le da una complejidad O (1) para tipos primitivos mediante el empleo de especialización de plantilla parcial.
La implementación de clear() navega su camino a la función std::_Destroy(from, to) en bits/stl_construct.h, que realiza una optimización en tiempo de compilación no trivial: se declara una clase de plantilla auxiliar _Destroy_aux con el parámetro de plantilla de tipo bool. La clase tiene una especialización parcial para true y una especialización explícita para false. Ambas especializaciones definen una única función estática llamada __destroy. En caso de que el parámetro de la plantilla sea true, el cuerpo de la función está vacío; en caso de que el parámetro sea false, body contains a loop invoking T's destructor llamando al std::_Destroy(ptr).
El truco viene en line 126:
std::_Destroy_aux<__has_trivial_destructor(_Value_type)>::
__destroy(__first, __last);
La clase auxiliar se crea una instancia basado en el resultado de la comprobación __has_trivial_destructor. El comprobador devuelve true para tipos incorporados, y false para tipos con destructor no trivial. Como resultado, la llamada al __destroy se convierte en una operación no operativa para int, double y otros tipos de POD.
El std::unordered_map es diferente de la vector ya que puede que tenga que eliminar las estructuras que representan "cubos de hash" de objetos POD, en contraposición a los propios * eliminación de objetos. La optimización de clear a O(1) es posible, pero depende en gran medida de la implementación, por lo que no contaría con ella.
* La respuesta exacta depende de la implementación: tablas hash de aplicación basado en collision resolution (sondeo lineal, cuadrática de sondeo, etc.) direccionamiento abierto puede ser capaz de eliminar todos los cubos en O(1); Sin embargo, las implementaciones basadas en el encadenamiento separado tendrían que eliminar los segmentos una a una.