Boost.Intrusive and unordered_map

Question

Je cherche à utiliser un uneredered_map intrusif. Pour une raison quelconque, il existe uniquement un unordered_set dans la bibliothèque. Il y a aussi un hashtable intrusif mais je ne suis pas sûr qu'il ait la même fonctionnalité, il n'a pas non plus la même interface.
Est-ce que je me trompe et le lien unordered_map m'a échappé?
Si ce n’est pas le cas, existe-t-il un didacticiel qui m’aide à en installer un?

Answer 1

C'est une question intéressante. Boost.Intrusive ne semble pas fournir d’interface cartographique, ordonnée ou non. Il possède de nombreux types d'implémentation qui fonctionneront parfaitement, car les cartes sont à la fois ordonnées (arbres rouge-noir, arbres AVL, arbres évasés) et non ordonnées (tables de hachage). Mais pas de cartes et je ne saurais vous dire pourquoi.

Vous avez deux choix comme je le vois:

1. Il suffit d'utiliser hashtable: les conteneurs non ordonnés sont implémentés sous forme de tables de hachage (et la seule raison pour laquelle ils ne sont pas appelés hash_map est d'éviter les conflits de noms avec les bibliothèques préexistantes utilisant déjà ce nom. ). Cela fonctionnera si vous voulez que votre travail soit effectué.
2. Si vous voulez vraiment implémenter le vôtre, jetez un œil à la description de l'interface de unordered_set . Je n'ai pas examiné la mise en œuvre, mais il s'agit certainement d'une enveloppe autour d'un ou plusieurs types d'arbres. std::set et std::map sont tous deux généralement implémentés en tant que wrappers autour d'un arbre rouge-noir (dans toutes les implémentations de bibliothèque standard que j'ai consultées: les codes GCC, MSVC et Apdd). Découvrez également comment libstdc ++ encapsule l’implémentation de l’arbre dans <map> et dans <set>. C'est beaucoup de passe-partout, beaucoup de travail fastidieux, mais les deux types confient presque tout le travail à l'arbre. Il est presque certain que quelque chose d'analogue se produit avec Boost.Intrusive's unordered_set. Vous devrez examiner les différences entre les interfaces map et set et vous en servir comme base pour la modification de unordered_map en map.

J'ai fait le dernier. C'est un peu fastidieux, et je recommande fortement d'écrire des tests unitaires (ou de voler ceux fournis avec libstdc ++ ou Boost.Intrusive). Mais c'est faisable. Je recommande également vivement de lire les documents de configuration relatifs aux ensembles et aux cartes, à l’adresse SGI ( définie , carte ) ou pour libstdc ++

Mise à jour: j'ai compris pourquoi ils ne réalisaient pas de mappage: les conteneurs intrusifs nécessitent l'intégration des informations relatives au nœud de la structure de données dans le type de valeur que vous y stockez. Pour les cartes, vous devrez le faire pour les valeurs et les clés . Ce n’est pas que cela soit impossible, mais l’implémentation standard pour un set utilise le même type interne que comme le font les value_type s. Mais ces types internes n’ont que une <=> variable: pour stocker les clés et les valeurs, ils copient la clé et la valeur dans cette variable et les stockent dans les nœuds. Pour faire cela avec un type intrusif (c'est-à-dire sans copier), vous devez modifier ce type d'implémentation pour le rendre incompatible avec les ensembles: il doit stocker les références aux clés et aux valeurs séparément . Pour ce faire, vous devez également modifier l’implémentation que vous utilisez (probablement <=>). Encore une fois, ce n’est pas impossible, mais les concepteurs de bibliothèques essaient probablement d’éviter les doubles emplois de code. En l’absence d’un moyen simple de les implémenter, ils ont très probablement décidé de ne pas utiliser de cartes.

Est-ce que cela a du sens?

Answer 2

Cela fait longtemps que cette question n'a pas été posée, mais je pense que les personnes qui viennent ici devraient être intéressées par la façon d'utiliser un unordered_set comme carte. La solution consiste à utiliser les méthodes d'insertion avancées : il suffit de stocker une clé et sa valeur dans le même value_type, et insérez-la à l'aide de insert_check et insert_commit .