c++ - 双索引的最佳容器

Question

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

你会推荐什么？

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

Answer 1

我根据您的文章做出了几个假设:

• 复制和比较 key 的成本很低
• 对象在系统中应该只有一个拷贝
• 同一个key可能指向多个对象，但只有一个对象对应给定的key(一对多)
• 您希望能够高效地查找哪些对象对应给定的键，以及哪个键对应给定的对象

我建议:

• 使用链表或其他容器来维护系统中所有对象的全局列表。对象分配在链表上。
• 创建一个 std::multimap<Key, Object *>将键映射到对象指针，指向链接列表中的单个规范位置。
• 执行以下操作之一:
  • 创建一个 std::map<Object *, Key>这允许查找附加到特定对象的 key 。确保您的代码在 key 更改时更新此 map 。 (如果您需要多对多关系，这也可以是 std::multimap。)
  • 添加一个成员变量到Object包含当前 Key (允许 O(1) 查找)。确保您的代码在 key 更改时更新此变量。

由于您的文章提到“坐标”作为键，您可能也有兴趣阅读 Fastest way to find if a 3D coordinate is already used 上的建议。 .