Mise en œuvre de std:: unordered map

la norme prescrit effectivement std::unordered_set et std::unordered_map les mises en œuvre qui utilisent le hachage ouvert, ce qui signifie un ensemble de seaux, dont chacun détient la tête d'une liste logique (et typiquement actuelle). Cette exigence est subtile: c'est une conséquence du facteur de charge Max par défaut étant 1,0 et de la garantie que le tableau ne sera pas rabâché à moins d'être poussé au-delà de ce facteur de charge: ce serait impraticable sans chaînage, comme les collisions avec le hachage fermé deviennent écrasant lorsque le facteur de charge approche 1:

23.2.5 / 15: les éléments insert et emplace ne doivent pas affecter la validité des itérateurs si (N+n) < z * B , où N est le nombre d'éléments dans le conteneur avant l'opération d'insertion, n est le nombre d'éléments insérés, B est le nombre de godets du conteneur, et z est le facteur de charge maximal du conteneur.

parmi le effets du constructeur au 23.5.4.2 / 1: max_load_factor() retourne 1.0 .

(pour permettre une itération optimale sans passer par dessus des seaux vides, L'implémentation de GCC remplit les seaux avec des itérateurs dans une liste unique liée par des liens contenant toutes les valeurs: les itérateurs pointent vers l'élément immédiatement avant les éléments de ce seaux, de sorte que le pointeur suivant peut être rebranché si la dernière valeur du seau est effacée.)

concernant le texte que vous citez:

non, ce n'est pas du tout le moyen le plus efficace pour mettre en œuvre une carte de hachage pour les utilisations les plus courantes. Malheureusement, une petite" erreur " dans la spécification de unordered_map nécessite ce comportement. Le comportement requis est que les itérateurs vers les éléments doivent rester valides lors de l'insertion ou de la suppression d'autres éléments

Il n'y a pas de "surveillance"... ce qui est fait est très délibéré et fait avec pleine conscience. Il est vrai que d'autres compromis auraient pu être trouvés, mais l'approche du hachage / chaînage ouvert est un compromis raisonnable pour un usage général, qui permet de faire face de façon relativement élégante aux collisions provenant de fonctions de hachage médiocres, n'est pas trop gaspilleuse avec des types de clés/valeurs petites ou grandes, et gère arbitrairement-de nombreuses paires insert / erase sans dégrader graduellement les performances comme le font de nombreuses implémentations de hachage fermé.

comme preuve de la conscience, de la proposition de Matthew Austern ici :

Je ne suis pas au courant d'une mise en œuvre satisfaisante de l'adressage ouvert dans un cadre générique. En abordant présente un certain nombre de problèmes:

• il est nécessaire de faire la distinction entre un poste vacant et un poste occupé.

• Il est nécessaire de restreindre la table de hachage à les types avec un constructeur par défaut, et de construire chaque élément de tableau à l'avance, ou bien de maintenir un tableau dont certains éléments sont des objets et d'autres sont de la mémoire brute.

• l'adresse ouverte rend la gestion des collisions difficile: si vous insérez un élément dont le code de hachage correspond à un emplacement déjà occupé, vous avez besoin d'une politique qui vous indique où essayer la prochaine fois. C'est un problème résolu, mais les meilleures solutions connues sont compliquées.

• la gestion des collisions est particulièrement compliquée lorsqu'il est permis d'effacer des éléments. (Voir Knuth pour une discussion.) Une classe de conteneur pour la bibliothèque standard devrait permettre à l'effacement.

• les schémas de gestion de Collision pour l'adressage ouvert ont tendance à supposer un tableau de taille fixe qui peut contenir Jusqu'à N éléments. Une classe de conteneur pour la bibliothèque standard devrait être en mesure de croître comme nécessaire lorsque de nouveaux éléments sont insérés, jusqu'à la limite de la mémoire disponible.

résoudre ces problèmes pourrait être un projet de recherche intéressant, mais, en l'absence d'expérience de mise en œuvre dans le contexte de C++, il serait inapproprié de standardiser une classe de conteneurs à adresse ouverte.

spécifiquement pour insert-seulement des tables avec des données assez petites pour stocker directement dans les seaux, une valeur sentinelle commode pour les seaux inutilisés, et une bonne fonction de hachage, une approche de hachage fermé peut être environ un ordre de grandeur plus rapide et l'utilisation considérablement moins de mémoire, mais ce n'est pas d'usage général.

Une comparaison complète et à l'élaboration de la table de hachage des options de conception et de leurs conséquences est hors sujet, pour S. O. comme il est beaucoup trop large pour répondre correctement ici.