关于C#：最佳的双索引容器

设置容器中允许双索引的最佳方法(在C中)是什么？具体来说，我有一个对象列表，每个对象由一个键索引(每个键可能有多个)。这意味着多图。但是，这样做的问题是，这可能意味着查找对象的位置可能要比线性查找差。我宁愿避免重复数据，因此让每个对象保持其自身的坐标并不得不在地图中移动会很不好(更不用说在对象函数中移动自己的对象可能会间接调用析构函数！)。我希望有一个容器可以通过对象指针和坐标维护索引，并且对象本身可以保证稳定的引用/指针。然后，每个对象可以将迭代器存储到索引(包括坐标)中，并进行足够抽象，然后知道它在哪里。 Boost.MultiIndex似乎是最好的主意，但它非常令人恐惧，我也不想浪费我的实际对象必须是const。

您会推荐什么？

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

我正在根据您的文章做出几个假设：

• 密钥复制和比较便宜
• 系统中对象应该只有一个副本
• 相同的键可能引用许多对象，但是只有一个对象对应给定的键(一对多)
• 您希望能够有效地查找哪些对象对应于给定的键，以及哪个键对应于给定的对象

我建议：

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

由于您的文章提到"坐标"作为键，因此您可能也有兴趣阅读"最快"方法的建议，以查找是否已使用3D坐标。

一种选择是使用两个引用shared_ptrs的std :: maps。像这样的事情可能会让你前进：

编辑：我刚刚注意到多图的要求，它仍然表达了这个主意，因此我将其保留。

很难理解您到底在用它做什么，但似乎boost bimap是您想要的。除了特定的用例外，它基本上可以提高多索引的使用率，并且更易于使用。它允许基于第一个元素或第二个元素进行快速查找。为什么要通过对象的地址查找对象在地图中的位置？使用抽象，让它为您完成所有工作。只需注意一下：映射中所有元素的迭代为O(N)，因此可以保证O(N)(不会更糟)查找您正在考虑的方式。