Best container for double-indexing

Question

What is the best way (in C++) to set up a container allowing for double-indexing? Specifically, I have a list of objects, each indexed by a key (possibly multiple per key). This implies a multimap. The problem with this, however, is that it means a possibly worse-than-linear lookup to find the location of an object. I'd rather avoid duplication of data, so having each object maintain it's own coordinate and have to move itself in the map would be bad (not to mention that moving your own object may indirectly call your destructor whilst in a member function!). I would rather some container that maintains an index both by object pointer and coordinate, and that the objects themselves guarantee stable references/pointers. Then each object could store an iterator to the index (including the coordinate), sufficiently abstracted, and know where it is. Boost.MultiIndex seems like the best idea, but it's very scary and I don't wany my actual objects to need to be const.

What would you recommend?

EDIT: Boost Bimap seems nice, but does it provide stable indexing? That is, if I change the coordinate, references to other elements must remain valid. The reason I want to use pointers for indexing is because objects have otherwise no intrinsic ordering, and a pointer can remain constant while the object changes (allowing its use in a Boost MultiIndex, which, IIRC, does provide stable indexing).

Answer 1

Its difficult to understand what exactly you are doing with it, but it seems like boost bimap is what you want. It's basically boost multi-index except a specific use case, and easier to use. It allows fast lookup based on the first element or the second element. Why are you looking up the location of an object in a map by its address? Use the abstraction and let it do all the work for you. Just a note: iteration over all elements in a map is O(N) so it would be guaranteed O(N) (not worse) to look up the way you are thinking of doing it.

Answer 2

I'm making several assumptions based on your writeup:

• Keys are cheap to copy and compare
• There should be only one copy of the object in the system
• The same key may refer to many objects, but only one object corresponds to a given key (one-to-many)
• You want to be able to efficiently look up which objects correspond to a given key, and which key corresponds to a given object

I'd suggest:

• Use a linked list or some other container to maintain a global list of all objects in the system. The objects are allocated on the linked list.
• Create one std::multimap<Key, Object *> that maps keys to object pointers, pointing to the single canonical location in the linked list.
• Do one of:
  • Create one std::map<Object *, Key> that allows looking up the key attached to a particular object. Make sure your code updates this map when the key is changed. (This could also be a std::multimap if you need a many-to-many relationship.)
  • Add a member variable to the Object that contains the current Key (allowing O(1) lookups). Make sure your code updates this variable when the key is changed.

Since your writeup mentioned "coordinates" as the keys, you might also be interested in reading the suggestions at Fastest way to find if a 3D coordinate is already used.

Answer 3

One option would be to use two std::maps that referenced shared_ptrs. Something like this may get you going:

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: I just noticed the multimap requirement, this still expresses the idea so I'll leave it.