Meilleur conteneur pour la double indexation

Question

Quelle est la meilleure façon (en C++) de configurer un conteneur permettant une double indexation? Plus précisément, j'ai une liste d'objets, chacun indexé par une clé (éventuellement multiple par clé). Cela implique un multimap. Le problème avec ceci, cependant, est que cela signifie une recherche peut-être pire que linéaire pour trouver l'emplacement d'un objet. Je préfèrerais éviter la duplication de données, donc garder chaque objet à sa propre coordonnée et se déplacer dans la map serait mauvais (sans compter que le déplacement de votre propre objet peut appeler indirectement votre destructeur dans une fonction membre!). Je préfère un conteneur qui conserve un index à la fois par pointeur d'objet et par coordonnées, et que les objets eux-mêmes garantissent des références/pointeurs stables. Ensuite, chaque objet pourrait stocker un itérateur à l'index (y compris la coordonnée), suffisamment abstrait, et savoir où il se trouve. Boost.MultiIndex semble être la meilleure idée, mais c'est très effrayant et je ne veux pas que mes objets réels aient besoin d'être const.

Que recommanderiez-vous?

EDIT: Boost Bimap semble bien, mais fournit-il une indexation stable? C'est-à-dire que si je change la coordonnée, les références à d'autres éléments doivent rester valides. La raison pour laquelle je veux utiliser des pointeurs pour l'indexation est que les objets n'ont pas d'ordre intrinsèque, et qu'un pointeur peut rester constant pendant que l'objet change (permettant son utilisation dans un MultiIndex Boost, qui, IIRC, fournit une indexation stable).

Answer 1

Je fais plusieurs hypothèses en fonction de votre writeup:

• clés ne coûtent pas cher à copier et à comparer
• Il devrait y avoir qu'une seule copie de l'objet dans le système
• La même clé peut se référer à de nombreux objets, mais un seul objet correspond à une clé donnée (un-à-plusieurs)
• Vous voulez pouvoir rechercher efficacement quels objets correspondent à une clé donnée et quelle touche correspond à un objet donné

Je suggère:

• Utilisez une liste chaînée ou un autre récipient pour maintenir une liste globale de tous les objets du système. Les objets sont alloués dans la liste chaînée.
• Créez un std::multimap<Key, Object *> qui mappe les clés aux pointeurs d'objet, en pointant vers l'emplacement canonique unique dans la liste chaînée.
• Effectuez l'une des:
  • Créer un std::map<Object *, Key> qui permet la recherche la clé attachée à un objet particulier. Assurez-vous que votre code met à jour cette carte lorsque la clé est modifiée. (Cela peut également être un std::multimap si vous avez besoin d'une relation plusieurs-à-plusieurs.)
  • Ajoutez une variable membre au Object qui contient le Key actuel (permettant les recherches O (1)). Assurez-vous que votre code met à jour cette variable lorsque la clé est modifiée.

Depuis votre writeup mentionné « coordonnées » comme les touches, vous pourriez également être intéressé par les suggestions à Fastest way to find if a 3D coordinate is already used.

Answer 2

Il est difficile de comprendre exactement ce que vous faites avec, mais il semble que booster bimap est ce que vous voulez. Il s'agit en fait d'augmenter le multi-index sauf un cas d'utilisation spécifique, et plus facile à utiliser. Il permet une recherche rapide basée sur le premier élément ou le deuxième élément. Pourquoi cherchez-vous l'emplacement d'un objet dans une carte par son adresse? Utilisez l'abstraction et laissez-le faire tout le travail pour vous. Juste une note: l'itération sur tous les éléments d'une carte est O (N) donc il serait garanti O (N) (pas pire) de regarder la façon dont vous envisagez de le faire.

Answer 3

Une option serait d'utiliser deux std :: maps qui référencent shared_ptrs. Quelque chose comme cela peut vous aider à aller:

template<typename T, typename K1, typename K2> 
class MyBiMap 
{ 
public: 
    typedef boost::shared_ptr<T> ptr_type; 

    void insert(const ptr_type& value, const K1& key1, const K2& key2) 
    { 
     _map1.insert(std::make_pair(key1, value)); 
     _map2.insert(std::make_pair(key2, value)); 
    } 

    ptr_type find1(const K1& key) 
    { 
     std::map<K1, ptr_type >::const_iterator itr = _map1.find(key); 
     if (itr == _map1.end()) 
      throw std::exception("Unable to find key"); 
     return itr->second; 
    } 

    ptr_type find2(const K2& key) 
    { 
     std::map<K2, ptr_type >::const_iterator itr = _map2.find(key); 
     if (itr == _map2.end()) 
      throw std::exception("Unable to find key"); 
     return itr->second; 
    } 

private: 
    std::map<K1, ptr_type > _map1; 
    std::map<K2, ptr_type > _map2; 
}; 

Edit: Je viens de remarquer l'exigence de multimap, cela exprime encore l'idée, donc je vais le laisser.