c++ - 数据结构 : Many (A) to many (B) relationship, 每个链接也有自己的数据 (C)

Question

什么是适合保持多对多关系的数据结构(A-B)，关系的每个链接都有自己的用户数据 (C)?

我最关心性能。

例子1

场景中有多个二维圆。
它们可以相互生长和重叠(circle A & circle B)。
我必须跟踪重叠区域 (C)，例如颜色。

例子2

有很多投资者(A)和股票(B)。
每个投资者 (A) 都拥有一家公司 (B) 的所有权/职业 (C)。

示例 3

这是一个真实的情况。我不认为你需要阅读它。
我提供它以防万一。

我正在使用基于实体组件的架构。

有很多摇杆(A)，每个摇杆可以点击按钮(B)。

请注意，按钮 (B) 是游戏屏幕上的按钮。 (不是操纵杆硬件按钮)

我必须跟踪(使用 C)按钮是否被操纵杆“悬停”，并执行回调。

我必须跟踪的原因之一是:是否应该回调有标准。
它与标准 Windows 按钮相同:-

• 悬停时释放按钮 ... 和 ...
• 开始点击时悬停在同一个按钮上。

另一个原因是:鼠标可以同时悬停多个按钮。我也必须记录悬停的持续时间。 (用于图形)

A,B 和C 都是组件。

A 和 B 的数量在编译时未知。

我糟糕的解决方案

第一种解决方案:

HashMap<A*,HashMap<B*,C*>> database;

有点不对称。 (在B之前查询A)

第二种解决方案:

class CustomStruct{  A* a; B* b; }
HashMap<CustomStruct,C*> database;

无法有效地从 A 查询 C。

第三种解决方案:

HashMap<A*,C*> databaseAC;
HashMap<B*,C*> databaseBC;

将其拆分为两个 HashMap，通过昂贵的相交两个表 查询(A,B)->C。

第四种解决方案:

class A{HashMap<B*,C*> databaseBC;};
class B{HashMap<A*,C*> databaseAC;};

可能不错？

其他想法:

我应该使用 HashMap 吗？我应该尝试更多开箱即用的东西吗？
我的一些解决方案有前途吗？ (专家会选哪一位？)
最佳解决方案是否“取决于”访问/查询模式？

Answer 1

具有链接属性的多对多关系是无向图。适用于图形实现的所有选项。该对象的图形术语是“节点”。关系对是“边”。

• 矩阵:根据索引映射您的对象。例如。使用指针或引用数组获取对象的索引，然后在程序中传递索引以引用对象。将边表示为属性记录的方阵。由于您的图形是无向的，因此矩阵可以是三角形的。有 a fairly cool way of addressing elements of a triangular matrix stored in a 1d vector ，虽然用这种方法改变节点数是昂贵的。另一种方法是使用指向不同长度行的指针数组。

• 邻接表:使用与上面相同的索引->对象映射数组。将邻接表示为索引集的数组。同样，由于您的图形是无向的，因此您只需要存储邻接对 i -> j其中 i <= j .

邻接列表还有其他选项，但数组和索引很方便(索引比指针更易于调试)、内存效率高(32 位索引允许 40 亿个节点；64 位指针允许更多，但是在大多数应用程序中浪费了 2 倍的空间)，而且速度非常快(与基于 HashMap 的解决方案相比)。

两者之间的选择完全取决于边缘的密度。矩阵非常快，但如果密度低，矩阵的大部分是空的。只是初始化它可能会变得昂贵。因此，如果几乎所有节点对都有边，请使用矩阵。如果连接稀疏，则邻接表获胜。