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

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.