Comment `std::unordered_map` atteint-il des performances élevées tout en maintenant la validité de l'itérateur ?

Implémentation de std::unordered_map : un examen plus approfondi

Le conteneur std::unordered_map en C a suscité des discussions sur sa mise en œuvre et son efficacité. Pour faire la lumière sur ce sujet, explorons comment cette structure de données est réalisée.

Chaînage séparé avec des listes liées

À la base, unordered_map utilise une technique appelée chaînage séparé , également connu sous le nom de hachage ouvert. Cela implique de maintenir un tableau de compartiments, où chaque compartiment contient une liste chaînée d'éléments avec des clés de hachage en collision. Ce choix de conception découle de l'exigence de la norme C selon laquelle les itérateurs d'éléments restent valides même lorsque d'autres éléments sont insérés ou supprimés.

Redimensionnement et rehachage

Pour maintenir les performances , unordered_map utilise le redimensionnement et le rehachage. Le redimensionnement se produit lorsque le nombre d'éléments dépasse le nombre de compartiments actuel multiplié par le facteur de charge maximal, qui est par défaut de 1,0. Lors du remaniement, une nouvelle gamme de compartiments est créée avec une plus grande capacité, et tous les éléments existants sont remaniés et placés dans les compartiments appropriés.

Limitations

Lors du chaînage séparé est efficace pour les applications à usage général, il a des limites. Pour certains scénarios, le hachage fermé (adressage ouvert) peut offrir des avantages significatifs en termes de performances en termes de vitesse et d'utilisation de la mémoire. Cependant, l'adressage ouvert introduit des complexités, telles que la distinction entre les postes vacants et occupés et la gestion de la résolution des collisions.

La « surveillance » dans la norme

L'exigence de maintenir l'itérateur la validité a été qualifiée d'« oubli » par certains critiques. Cependant, le comité C a délibérément décidé de donner la priorité à la stabilité des itérateurs. Ce choix montre que unordered_map peut être utilisé dans des situations où les itérateurs et les références doivent rester intacts pendant les opérations d'insertion et de suppression.

Conclusion

L'implémentation de std::unordered_map équilibre la généralité, les performances et le respect de la norme C. Le chaînage séparé avec des listes chaînées garantit la validité de l'itérateur, tandis que le redimensionnement et le rehachage optimisent les performances. Malgré les limitations potentielles dans des scénarios spécifiques, unordered_map reste une structure de données polyvalente et largement utilisée pour gérer les insertions et les recherches basées sur le hachage.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!