The best container for dual indexing

Question

What is the best way (in C ++) to configure a container for double indexing? In particular, I have a list of objects, each of which is indexed by a key (possibly several keys). This implies a multimap. The problem with this, however, is that it means that perhaps worse than a linear search to find the location of an object. I would prefer to avoid duplicating data, so it would be bad for each object to maintain its own coordinate and have to move on the map (not to mention that moving your own object can indirectly call your destructor while in the function- member!). I would prefer some container that maintains an index with both a pointer to an object and a coordinate, and that the objects themselves guarantee stable links / pointers.Then each object can store an iterator in the index (including the coordinate), it is enough to abstract and know where it is. Boost.MultiIndex seems like a better idea, but it's very scary, and I don't want my actual objects to need const.

What would you recommend?

EDIT: Boost Bimap seems nice, but does it provide stable indexing? That is, if I change the coordinate, links to other elements must remain valid. The reason I want to use pointers for indexing is because the objects otherwise do not have an internal order, and the pointer can remain constant while the object changes (allowing it to be used in Boost MultiIndex, which, IIRC, provides stable indexing) .

Answer 1

I make a few assumptions based on your entry:

• Keys are cheap to copy and compare.
• The system must have only one copy of the object
• , (--)
• , , .

:

• - . .
• std::multimap<Key, Object *>, , .
• :
  • std::map<Object *, Key>, , . , . ( std::multimap, " ".)
  • - Object, Key ( O (1)). , .

"" , , 3D- .

Answer 2

, , , boost bimap - , . , , . . ? . : O (N), , O (N) ( ), , .

Answer 3

- std:: maps, shared_ptrs. - :

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

: , , .