Pregunta ¿Cuál es la complejidad de std :: vector :: clear () cuando T es un tipo primitivo?


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.

Si esto es posible, ¿también es posible para std :: unordered_map?


13
2018-06-27 23:03


origen


Respuestas:


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 cambiar el tamaño de un vector a cero es lineal en la cantidad de elementos actualmente almacenados en vector. Por lo tanto, establecer vectorEl tamaño a cero no ofrece ninguna ventaja sobre las llamadas clear() - los dos son esencialmente lo mismo.

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 la especialización de plantilla parcial.

La implementación de clear() navega hacia el std::_Destroy(from, to) funcionar en bits/stl_construct.h, que realiza una optimización de tiempo de compilación no trivial: declara una clase de plantilla auxiliar _Destroy_aux con el parámetro de plantilla de tipo bool. La clase tiene un especialización parcial para true y un 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, el cuerpo contiene un bucle invocando Tdestructor llamando std::_Destroy(ptr).

El truco viene línea 126:

std::_Destroy_aux<__has_trivial_destructor(_Value_type)>::
__destroy(__first, __last);

La clase auxiliar se crea una instancia basada en el resultado de la __has_trivial_destructor comprobar. El inspector regresa true para tipos incorporados, y false para tipos con destructor no trivial. Como resultado, la llamada a __destroy se convierte en un no-op para int, doubley otros tipos de POD.

los std::unordered_map es diferente de la vector en el sentido de que puede necesitar eliminar estructuras que representen "cubos hash" de objetos POD, en lugar de eliminar objetos ellos mismos*. 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 ello.


* La respuesta exacta depende de la implementación: implementación de tablas hash resolución de colisión basado en el direccionamiento abierto (sondeo lineal, sondeo cuadrático, etc.) puede 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.


6
2017-11-20 19:35



la versión de gcc std::_Destroy, que es lo que finalmente es utilizado por clear(), intenta crear una plantilla sobre si el tipo tiene un destructor trivial, por lo que en ese caso la complejidad es constante incluso sin un pase de optimización. Sin embargo, no sé qué tan bien funciona la plantilla.


0
2018-06-27 23:33