desempeño de declarar objetos

Jan 03 2021

Estaba codificando en una especie de conquista universitaria y noté algo, cuando declaro un mapa en un bucle como el de abajo:

for (int i = 0; i < n; i++)
{
    map<int, bool> hashMap;
    //...
}

toma más tiempo que:

map<int, bool> hashMap;
for (int i = 0; i < n; i++)
{
    hashMap.clear();
    //...
}

así que me preguntaba por qué declarar un objeto en un bucle tiene un rendimiento peor que simplemente reinicializarlo.

Respuestas

2 dxiv Jan 04 2021 at 10:59

En la primera versión del código, el constructor y el destructor del hashMapse llaman ntiempos, mientras que en la segunda versión se llaman solo una vez.

La pregunta natural es por qué destruir y construir un nuevo mapobjeto sería notablemente diferente a limpiar y reutilizar un mismo objeto. Esto puede responderse definitivamente solo inspeccionando el mapcódigo real de la implementación que se está utilizando, por lo que lo siguiente es solo una suposición plausible.

std::mapgeneralmente se implementa usando árboles rojo-negro , y es común que las implementaciones de árbol rojo-negro usen un nodo centinela para NIL-leaves, ver por ejemplo ¿ Beneficio de un nodo centinela en un árbol rojo negro? . Este centinela debe asignarse cada vez que se construye un árbol y luego liberarse tras su destrucción. Por el contrario, clear'ing a map, en cambio, vacía el árbol pero reutiliza los objetos internos asociados.

Para obtener un ejemplo de la vida real de tal implementación, el _Treeconstructor de Microsoft llama al apropiadamente nombrado _Alloc_sentinel_and_proxy();. Dado que se mapderiva de _Tree, se llama cada vez mapque se construye un objeto.