Tout ce qui est implémenté comme Loki's AssocVector mais avec les fonctionnalités de Bimap de Boost?

Question

Je me demande si quelqu'un connaît un code de bibliothèque qui a les caractéristiques de performance fournies par Loki's AssocVector (Localité de référence des éléments, surcharge de mémoire par élément inférieure par rapport à une carte) mais avec la fonctionnalité BiMap de Boost carte des deux côtés de la relation)? Ou utiliserait-on un vecteur std :: trié de paires std :: et ajouterais-tu des fonctionnalités pour chercher le vecteur en utilisant l'un ou l'autre des éléments de la paire comme clé pour avancer?

Answer 1

Cela dépend vraiment de ce que vous voulez faire rapidement. Loki::AssocVector a O (n) insérer et supprimer, tandis que boost::bimap a O (1) lorsque vous l'utilisez avec des tables de hachage. Si vous pouvez vivre avec O (n) opérations sur une "vue" de votre structure de données et O (lg n) sur l'autre, alors votre solution proposée fonctionnera bien et prendra peu de mémoire. Il peut être très rapide pour les petits ensembles de données, si les opérations sur une vue dominent.

Vous pouvez également utiliser Boost.Intrusive ou boost::bimap avec des allocateurs spécialisés.