Meilleur conteneur pour la double indexation

Question

Quel est le meilleur moyen (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 plusieurs par clé). Cela implique une carte multiple. 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. Par conséquent, si chaque objet conservait ses propres coordonnées et devait se déplacer dans la carte, il serait mauvais (de plus, le déplacement de votre propre objet peut appeler indirectement votre destructeur dans une fonction membre!). Je préférerais un conteneur qui gère un index à la fois par pointeur et par coordonnée, et que les objets eux-mêmes garantissent des références / pointeurs stables. Ensuite, chaque objet peut stocker un itérateur dans l'index (y compris la coordonnée), suffisamment résumé 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 soient constants.

Que recommanderiez-vous?

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

Answer 1

Je fais plusieurs hypothèses en fonction de votre rédaction:

• Les clés ne coûtent pas cher pour copier et comparer
• Il ne devrait y avoir qu'une seule copie de l'objet dans le système
• La même clé peut faire référence à plusieurs 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 clé correspond à un objet donné

Je suggérerais:

• Utilisez une liste chaînée ou un autre conteneur pour gérer une liste globale de tous les objets du système. Les objets sont alloués sur la liste liée.
• Créez-en une std::multimap<Key, Object *> qui mappe les clés sur les pointeurs d'objet, en pointant vers l'emplacement unique canonique de la liste liée.
• Faites l'une des actions suivantes:
  • Créez-en une std::map<Object *, Key> permettant de rechercher la clé associée à un objet particulier. Assurez-vous que votre code met à jour cette carte lorsque la clé est modifiée. (Cela pourrait aussi être un std::multimap si vous avez besoin d’une relation plusieurs à plusieurs.)
  • Ajoutez une variable membre au Object qui contient les Key actuelles (autorisant les recherches O (1)). Assurez-vous que votre code met à jour cette variable lorsque la clé est modifiée.

Depuis votre écriture mentionnée " coordonnées " En tant que clés, vous pourriez également être intéressé par les suggestions de Le moyen le plus rapide de trouver si une coordonnée 3D est déjà utilisée .

Answer 2

Il est difficile de comprendre ce que vous faites exactement avec cela, mais cela semble être un coup de pouce bimap est ce que vous voulez. En gros, il s'agit d'un multi-index boost, sauf dans des cas d'utilisation spécifiques, et plus simple à utiliser. Il permet une recherche rapide basée sur le premier ou le deuxième élément. Pourquoi recherchez-vous l'emplacement d'un objet sur une carte en fonction de son adresse? Utilisez l’abstraction et laissez-la faire tout le travail à votre place. Remarque: l'itération de tous les éléments d'une carte est O (N). Il serait donc garanti que O (N) (pas pire) regarde de la façon dont vous envisagez de le faire.

Answer 3

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

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;
};

Éditer: Je viens de remarquer l’exigence de la multi-carte, cela exprime toujours l’idée, je vais donc la laisser.