Il s'agit de la deuxième partie de la série sur le choix du conteneur associatif (dictionnaire) le plus adapté en C++23. , et dans cette partie, nous aborderons en détail les conteneurs non ordonnés. Dans la première partie, nous avons abordé les conteneurs ordonnés Conteneurs non ordonnés Ces conteneurs ne fournissent aucun ordre défini pour leurs clés. De plus, l'ordre des clés peut changer à chaque modification, le programme ne doit donc jamais s'y fier. Ces conteneurs sont toujours implémentés sous forme de tables de hachage. En général, lors de l'ajout, de la suppression ou de la recherche d'une clé, une table de hachage calcule d'abord une valeur de hachage intégrale à partir de cette clé à l'aide de la fonction de hachage. Le hachage (ou plutôt sa partie) est ensuite utilisé comme index dans le tableau pré-alloué contigu. Chaque entrée de ce tableau est appelée un . Certaines entrées de ce tableau seront vides, certaines contiendront un seul élément et certaines peuvent correspondre à plusieurs éléments en raison de collisions de hachage. Cela se produit lorsque différentes clés ont des valeurs de hachage qui pointent vers le même index de tableau. Les tables de hachage utilisent diverses stratégies pour gérer les collisions de hachage (voir ). Le nombre d'éléments dans la table de hachage divisé par la taille totale du tableau est appelé le . Plus le facteur de charge est élevé, plus les collisions de hachage possibles sont nombreuses avec chaque élément nouvellement inséré. bucket cet article de Wikipédia facteur de charge Contrairement aux conteneurs ordonnés, les tables de hachage ne prennent pas en charge les requêtes de plage, les opérations de classement/sélection, l'itération sur les clés dans l'ordre et la recherche de la clé plus petite/plus grande que la clé donnée. En retour, les tables de hachage atteignent les meilleures performances réalisables : la complexité temporelle des opérations de recherche/insertion/suppression est ). Je dis « amortie » ici, car lorsque le nombre d'éléments devient trop important, une table de hachage doit réorganiser son contenu pour réduire le facteur de charge (en augmentant effectivement le tableau de compartiments). La complexité temporelle du réorganisation est . Cependant, on s'attend à ce que cela se produise rarement, donc en moyenne, chaque opération est toujours . Une autre raison de performances potentiellement réduites est une fonction de hachage avec une mauvaise distribution, ce qui augmentera la fréquence des collisions. amortie O(1) O(n) O(1) Cartes de hachage standard À partir de C++11, la bibliothèque standard fournit les tables de hachage suivantes : ( ), ( ), ( ) et ( ). associent une clé à la valeur, tandis que ne stockent que la clé et sont utiles pour vérifier si la clé est présente dans le conteneur, mais pas pour récupérer la valeur associée. Les conteneurs permettent de stocker plusieurs clés en double. std::unordered_map link std::unordered_set link std::unordered_multimap link std::unordered_multiset link Les tables les ensembles multiples Tous les conteneurs non ordonnés standard sont basés sur des nœuds et utilisent pour gérer les collisions de hachage, ce qui signifie qu'ils stockent chaque clé ou paire clé-valeur dans un nœud de liste chaînée distinct. La mémoire de chaque nouveau nœud est allouée individuellement, ce qui n'est pas particulièrement efficace. Cela rend également la structure de données peu adaptée au cache du processeur, car chaque accès à la clé nécessite une indirection supplémentaire. Voici à quoi peut ressembler la structure interne : un chaînage séparé unordered_map Sur la gauche, il y a un tableau de buckets, qui est pré-alloué à une taille fixe ( dans notre exemple). Initialement, tous les buckets sont vides. Lorsque nous commençons à ajouter des éléments à la table de hachage, certains buckets seront occupés. Dans l'exemple ci-dessus, il y a un élément avec la clé (qui est entré dans le bucket ), et deux éléments avec les clés et , tous deux ont fini dans le même bucket parce que leurs valeurs de hachage sont entrées en collision. Il y a aussi un élément avec la clé , qui a atterri dans le bucket Chaque bucket pointe vers la liste chaînée, qui ne contient idéalement pas plus d'un élément. Les buckets , , , et sont vides et pointent vers . 8 10 1 50 256 3 3 6 0 2 4 5 7 nullptr Supposons que nous devons trouver la valeur de la clé . 256 Tout d'abord, la carte calcule le hachage de la clé et obtient le reste en divisant la valeur de hachage par le nombre total de buckets ( dans notre cas). Dans notre exemple, la valeur restante est . 8 3 Ensuite, la carte commence à lire les éléments de la liste chaînée pointée par le bucket . 3 Le premier élément a la clé , qui n'est pas la même que la que nous recherchons, donc la carte va continuer à itérer. L'élément suivant a la clé , qui est exactement celle dont nous avons besoin. La valeur correspondante est . 50 256 256 xyz Si la clé ne se trouvait pas dans le dictionnaire, la carte atteindrait un bucket vide ou parcourrait la liste chaînée jusqu'à la fin. Dans les deux cas, la carte renverrait un itérateur , indiquant que la clé n'existe pas. end Vous remarquerez peut-être que le dernier élément de chaque liste pointe vers le premier élément de la liste suivante. Cela est fait dans certaines implémentations pour améliorer l'efficacité de l'itération. Au lieu de vérifier bucket par bucket lors de l'itération sur tous les éléments de la table de hachage, nous pouvons utiliser ces connexions pour passer d'une liste chaînée non vide à une autre beaucoup plus rapidement. Si nous continuons à ajouter des éléments à la table de hachage ci-dessus, à un moment donné, le deviendra trop élevé (par exemple, 80 %) et la table de hachage décidera de procéder à un nouveau hachage. Elle agrandira le tableau pré-alloué (par exemple de à éléments), recalculera les hachages pour tous les éléments existants et placera les éléments dans les nouveaux compartiments. facteur de charge 8 16 Les conteneurs standards offrent des garanties de stabilité des références et des itérateurs, mais elles sont plus faibles que celles offertes par les conteneurs ordonnés. Les références aux éléments existants ne sont jamais invalidées. Les itérateurs aux éléments existants ne peuvent être invalidés que lorsque l'ajout d'un nouvel élément provoque un rehash, ou lorsque le rehash est déclenché manuellement : #include <iostream> #include <unordered_map> int main() { std::unordered_map<std::string, int> map{ {"test", 123}, {"xyz", 456}, {"abc", 10} }; auto& value = map["abc"]; auto valueIt = map.find("abc"); // Might cause a rehash if the load factor // is too high map.emplace("zzz", 1000); // Triggers the rehash manually map.rehash(1000); // References remain valid in any case: std::cout << value << "\n"; // Iterators are invalidated: the line below // is undefined behavior and might crash std::cout << valueIt->second << "\n"; } Depuis C++17, les conteneurs non ordonnés permettent la manipulation des nœuds : il est possible de prendre un nœud d'une carte et de le déplacer vers une autre carte sans copier la clé et la valeur : #include <iostream> #include <unordered_map> int main() { std::unordered_map<std::string, int> map1{ {"test", 123}, {"xyz", 456}, {"abc", 10} }; // Take the node from map1: auto node = map1.extract("xyz"); // We can even change its key // (we can also change the value // if needed): node.key() = "xyzxyz"; std::unordered_map<std::string, int> map2; // Insert the node into another map: map2.insert(std::move(node)); // Prints "xyzxyz: 456": for (const auto& [k, v] : map2) { std::cout << k << ": " << v << "\n"; } } Voici ce qui se passe dans le programme ci-dessus : Une autre stratégie pour gérer les collisions de hachage est appelée . Dans les cartes de hachage à adressage ouvert, chaque compartiment stocke au plus un élément. Si le compartiment est déjà occupé, l'élément avec la même valeur de hachage va dans un autre compartiment libre. Ces cartes de hachage tentent de regrouper les éléments dans des blocs de mémoire contigus pour améliorer l'efficacité et rendre la structure de données plus conviviale pour le cache du processeur. La bibliothèque standard C++ ne fournit pas de cartes de hachage à adressage ouvert, mais il existe de nombreuses alternatives tierces. adressage ouvert Cartes de hachage tierces est une bibliothèque impressionnante qui fournit une large gamme d'implémentations de cartes de hachage. Boost.Unordered Il existe , , et , qui sont des analogues des conteneurs , et tout ce qui est écrit ci-dessus s'applique à eux. Ces conteneurs utilisent une structure interne un peu plus complexe avec des « groupes de compartiments » pour améliorer l'efficacité des itérations. boost::unordered_set boost::unordered_map boost::unordered_multiset boost::unordered_multimap std La bibliothèque fournit également , , et , qui sont des conteneurs d'adressage ouverts. La structure interne est différente des variantes d'adressage ouvert : boost::unordered_node_set boost::unordered_node_map boost::unordered_flat_set boost::unordered_flat_map Vous pouvez en savoir plus sur la structure interne . dans cet article de blog Les conteneurs basés sur des nœuds ( , ) utilisent toujours des nœuds, vers lesquels pointent les buckets. Ces conteneurs fournissent la même stabilité d'itérateur et de référence garantie que les conteneurs et fournissent également la même API pour la manipulation des nœuds (c'est-à-dire la méthode ). boost::unordered_node_set boost::unordered_node_map std extract Dans les conteneurs plats ( , ), les clés et les valeurs sont stockées directement dans le tableau bucket. Les conteneurs plats sont les plus efficaces, mais offrent les garanties les plus faibles : les itérateurs et les références à tous les éléments sont invalidés lors du rehachage. L'API de manipulation des nœuds n'est pas du tout fournie. Les conteneurs plats peuvent utiliser plus de mémoire que ceux basés sur des nœuds, en particulier si la clé ou la valeur est grande. boost::unordered_flat_set boost::unordered_flat_map sizeof (fournie par Meta) est une autre bibliothèque tierce qui implémente des conteneurs à adressage ouvert. Il existe quelques variantes de dictionnaire qui sont très proches des conteneurs de la bibliothèque Boost décrits ci-dessus : Folly F14 est identique à , est identique à . folly::F14NodeSet boost::unordered_node_set folly::F14NodeMap boost::unordered_node_map est identique à , et est identique à . folly::F14ValueSet boost::unordered_flat_set folly::F14ValueMap boost::unordered_flat_map / conserve les clés/valeurs regroupées dans un tableau contigu, et les buckets contiennent des index dans ce tableau. folly::F14VectorMap folly::F14VectorSet / est une classe parapluie. Elle choisit l'implémentation la plus efficace ( ou ) en fonction des paramètres que vous spécifiez (tels que les types de clé et de valeur). folly::F14FastMap folly::F14FastSet F14Value F14Vector Une fonctionnalité intéressante et efficace des tables de hachage F14 est . Par exemple, si vous devez rechercher la même clé plusieurs fois et que son hachage est coûteux (par exemple, une clé est une chaîne), vous pouvez la pré-hacher une fois, puis utiliser le dans tous les appels de table de hachage ultérieurs pour éviter de re-hacher la même clé plusieurs fois. Le point de départ est la méthode ( ). le pré-hachage F14HashToken prehash lien Vous pouvez en savoir plus sur la structure interne des conteneurs de hachage F14 dans . cet article de blog FB (fournie par Google) implémente également des conteneurs de hachage plats et basés sur des nœuds à adressage ouvert : , , , . Ils sont similaires à ceux de Boost et F14. Vous pouvez en savoir plus à leur sujet et . La bibliothèque Abseil Swiss Tables absl::flat_hash_map absl::flat_hash_set absl::node_hash_map absl::node_hash_set ici ici Une bibliothèque moins connue ( ) prétend être très efficace dans la plupart des scénarios. L'auteur de cette bibliothèque fournit des résultats de référence complets pour de nombreuses cartes de hachage dans différents cas d'utilisation ( ). Vous pouvez suivre ces résultats, mais prenez-les avec des pincettes. Testez toujours la carte de hachage que vous choisissez dans l'environnement de production. Les tests sont toujours synthétiques et ne couvrent pas les cas où le processeur et la mémoire effectuent d'autres tâches en plus des opérations de carte de hachage. Les tests ne couvrent pas non plus les cas où diverses parties de la mémoire de la carte de hachage ne se trouvent pas dans le cache du processeur, ce qui se produit fréquemment dans les programmes réels. ankerl github article de blog Qualité de la fonction de hachage La qualité de la fonction de hachage est importante pour maintenir la complexité temporelle des opérations de recherche . Les cartes de hachage plates sont particulièrement sensibles à la qualité de la fonction de hachage. Une fonction de hachage idéale peut être définie comme ceci : si un seul bit de la clé change, la valeur de hachage correspondante changera la moitié de ses bits de manière aléatoire. Une telle fonction de hachage est appelée . O(1) avalanche Malheureusement, certaines implémentations de la bibliothèque standard C++ des fonctions de hachage d'entiers et de pointeurs ne sont pas des fonctions d'avalanche. Par exemple, renvoie simplement la valeur du pointeur ou de l'entier directement sans aucune transformation supplémentaire : . libstdc++ github Les tables de hachage avancées, telles que les implémentations et , traitent ce problème en introduisant le trait . Si la fonction de hachage ne se déclare pas comme avalanching, la table de hachage effectuera une étape de mixage supplémentaire pour améliorer la qualité du hachage. Cela a un coût supplémentaire. Si vous implémentez une fonction de hachage personnalisée et que vous savez qu'elle est de bonne qualité, vous pouvez la marquer comme avalanching comme indiqué dans . Boost utilise le nom de propriété et la propriété F14 est nommée . Idéalement, vous devriez ajouter les deux. boost F14 hash_is_avalanching cet exemple is_avalanching folly_is_avalanching Si vous utilisez les types de clés pris en charge prêts à l'emploi (par exemple, , , pointeurs) et les fonctions de hachage par défaut fournies par ou , ils seront déjà marqués correctement selon les besoins, et vous n'aurez pas besoin d'y penser à moins que vous ne décidiez d'implémenter un type de clé personnalisé, qui nécessitera une fonction de hachage personnalisée. string int boost F14 Sécurité des fils En général, tous les conteneurs ci-dessus ne sont pas thread-safe et vous devrez implémenter une synchronisation externe (par exemple, en utilisant des mutex) si un thread peut modifier la table de hachage lorsqu'un autre thread y accède. Si tous les threads ne lisent que la carte, aucune synchronisation n'est nécessaire. Assurez-vous d'appeler uniquement les méthodes marquées avec . Toutes les méthodes non peuvent modifier le conteneur. Gardez à l'esprit que n'est pas et modifiera le conteneur. Un piège courant dans le code multithread est : const const operator[] const std::unordered_map<std::string, bool> map; // ... if (map["key"]) { // ... } Dans le code ci-dessus, l'objectif est de vérifier si la valeur correspondant à la est . Cependant, la à la si elle n'y est pas déjà. La valeur nouvellement ajoutée sera définie sur default ( dans l'exemple ci-dessus). Cela signifie qu'un tel code n'est pas thread-safe et n'est pas trop optimal. Une manière plus efficace et thread-safe de vérifier la même condition est la suivante : key true map["key"] ajoutera key map false if (auto it = map.find("key"); it != map.end() && it->second == true) { // ... } Ici, nous obtenons d'abord l'itérateur vers l'élément identifié par la « clé ». Nous vérifions ensuite si l'élément existe dans la carte ( ). it != map.end() Si c'est le cas, nous vérifions finalement sa valeur ( ). it->second == true Dans cet exemple, et ne modifient pas la carte, et la recherche devient thread-safe. Si l'objectif était uniquement de vérifier si la clé existe dans la carte, vous pourriez simplement appeler . find end map.contains("key") Cartes non ordonnées thread-safe Il existe quelques implémentations de cartes de hachage thread-safe. Une option est et de la . Les conteneurs Boost fournissent une API basée sur les visites qui est très différente de l'API fournie par la bibliothèque standard C++. boost::concurrent_flat_set boost::concurrent_flat_map bibliothèque Boost.Unordered Une autre option est ( ). Folly essaie de garder son API aussi proche que possible des conteneurs non ordonnés standard C++. folly::ConcurrentHashMap github est une grande bibliothèque de conteneurs sans verrou qui fournit plusieurs implémentations de tables de hachage sans verrou (par exemple , , , , ). Cette bibliothèque n'a pas été mise à jour depuis un certain temps et ne fournit pas de documentation détaillée, mais je la partage toujours car les conteneurs qu'elle propose sont uniques. Si votre cas d'utilisation implique une forte contention sur une table de hachage, essayez ces dictionnaires sans verrou proposés par . libcds MichaelHashMap SkipListMap SkipListSet FeldmanHashMap FeldmanHashSet libcds Si l'efficacité n'est pas un problème, vous pouvez synchroniser les accès aux cartes non thread-safe à l'aide de mutex. Vous pouvez également éviter complètement les accès simultanés, ce qui est souvent plus efficace que l'utilisation de conteneurs thread-safe ou l'ajout d'une synchronisation. Lequel dois-je utiliser ? Voyons les points résumés qui expliquent comment choisir le conteneur le plus approprié. Si vous devez associer une clé à la valeur, choisissez une , sinon, utilisez un . carte ensemble S'il est nécessaire de conserver des clés en double dans la carte, utilisez conteneurs. plusieurs Si vous avez besoin des garanties de stabilité d'itérateur et de référence les plus strictes possibles, utilisez des conteneurs basés sur des nœuds , , ou (tels que , , ou ). et seront probablement les plus efficaces. std boost folly abseil std::unordered_map boost::unordered_map boost::unordered_node_map folly::F14NodeMap boost::unordered_node_... folly Si la stabilité de l'itérateur et de la référence n'est pas importante (ce qui signifie que vous ne stockez pas d'itérateurs, de références ou de pointeurs vers des éléments de carte/ensemble en externe ou que vous ne vous attendez pas à ce qu'ils restent valides après la modification de la carte), alors choisissez un conteneur plat (tel que ou ). boost::unordered_flat_map folly::F14FastMap Les conteneurs plats utilisent plus de mémoire que ceux basés sur des nœuds, en particulier lorsque de la clé et/ou de la valeur est importante. Si l'utilisation de la mémoire est un problème, utilisez plutôt des conteneurs basés sur des nœuds. sizeof Les conteneurs F14 fournissent une fonctionnalité de pré-hachage pour une efficacité accrue. Si vous recherchez/ajoutez/supprimez des clés identiques plusieurs fois, F14 permettra d'économiser sur le coût de hachage en pré-hachant les clés. Tous les points ci-dessus s'appliquent à l'utilisation d'un conteneur monothread (ou à un accès en lecture multithread sans modifications simultanées). Si des modifications multithread sont requises, sélectionnez l'une des options thread-safe répertoriées ci-dessus. Elles peuvent présenter des performances variables dans le code de production réel, pensez donc à les tester dans votre application et à comparer les résultats.
