双索引的最佳容器

Question

设置允许双索引的容器的最佳方法是什么（在 C++ 中）？具体来说，我有一个对象列表，每个对象都由一个键索引（每个键可能有多个）。这意味着多图。然而，这样做的问题在于，这意味着可能比线性查找更糟糕，以找到对象的位置。我宁愿避免重复数据，因此让每个对象保持自己的坐标并且必须在地图中移动自己会很糟糕（更不用说移动自己的对象可能会在成员函数中间接调用析构函数！）。我宁愿一些容器通过对象指针和坐标来维护索引，并且对象本身保证稳定的引用/指针。然后每个对象可以存储一个迭代器到索引（包括坐标），充分抽象，并知道它在哪里。Boost.MultiIndex 似乎是最好的主意，但它非常可怕，我不希望我的实际对象需要是常量。

你会推荐什么？

编辑：Boost Bimap 看起来不错，但它是否提供稳定的索引？也就是说，如果我更改坐标，对其他元素的引用必须保持有效。我想使用指针进行索引的原因是因为对象没有内在排序，并且指针可以在对象更改时保持不变（允许它在 Boost MultiIndex 中使用，IIRC 确实提供了稳定的索引）。

Answer 1

我根据你的文章做出了几个假设：

• 复制和比较密钥的成本很低
• 系统中对象应该只有一个副本
• 同一个键可以引用多个对象，但只有一个对象对应一个给定的键（一对多）
• 您希望能够有效地查找哪些对象对应于给定的键，以及哪些键对应于给定的对象

我建议：

• 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.