desempenho de declarar objetos

Jan 03 2021

Eu estava codificando em algum tipo de conquista de universidade e percebi algo, quando declaro um mapa em um loop, como abaixo:

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

leva mais tempo do que:

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

então eu queria saber por que declarar um objeto em um loop tem um desempenho pior do que apenas reinicializá-lo?

Respostas

2 dxiv Jan 04 2021 at 10:59

Na primeira versão do código, o construtor e o destruidor do hashMapsão chamados de ntempos, enquanto na segunda versão são chamados apenas uma vez.

A questão natural é por que destruir e construir um novo mapobjeto seria visivelmente diferente do que limpar e reutilizar um e o mesmo objeto. Isso pode ser definitivamente respondido apenas pela inspeção do mapcódigo real da implementação que está sendo usada, portanto, o que se segue é apenas um palpite plausível.

std::mapgeralmente é implementado usando árvores vermelhas e pretas , e é comum para implementações de árvores vermelhas e pretas usarem um nó sentinela para folhas NIL, veja por exemplo Benefício de um nó sentinela em uma árvore vermelho preto? . Essa sentinela deve ser alocada cada vez que uma árvore é construída e, em seguida, liberada após a destruição. Em contraste, clear'ing a map, em vez disso, esvazia a árvore, mas reutiliza os objetos internos associados.

Para obter um exemplo da vida real de tal implementação, o _Treeconstrutor da Microsoft chama o nome apropriadamente _Alloc_sentinel_and_proxy();. Como seu mapderiva de _Tree, ele é chamado sempre que um mapobjeto é construído.