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

Best container for double-indexing

设置容器中允许双索引的最佳方法(在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。像这样的事情可能会让你前进：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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;
};

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

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