c++ - boost::bimap 对单射函数是否过度杀伤力？

Question

设 T_1 和 T_2 是两种类型，f: Dom(T_1) -> Dom(T_2) 是一个非双射的单射函数；为了便于讨论，假设我将 f 表示为不同的对，而不是用于计算它的代码。现在，我需要能够相对快速地应用 f 和 f^{-1}，所以我在考虑每个方向的 map 。然后我想到我可能需要一个数据结构来同时处理这两个映射 - 因为我有多个这样的 f。

我很自然地认为“嗯，我确定 Boost 一定有类似的东西”，事实上，Boost 有一个 Bimap结构。问题是，一个用于一般的二元关系；此外，它必须考虑重复插入的可能性，而无需每次都重新优化结构，而在我的情况下，我只插入一次，然后进行多次查找。所以，我觉得 bimap 对我来说可能有点矫枉过正，而且没有针对我的用例进行优化。是真的吗？

注意事项:

• 我对以空间为代价的时间复杂度(和实际时间)很感兴趣。
• 关于非单射 f 的相同问题(f^{-1} 是非函数关系)。

Answer 1

正常的 C++ 容器行为(通过您关于对象大小的提示得到加强)是存储每个键和值(这些概念仅在非单射情况下是不同的)一次 .单独的插入和查找阶段建议使用连续存储(如果没有别的，用于缓存位置)。 “以空间为代价的时间”表示您需要一个哈希表。

所以存储一个数组pair<T1,T2>和一对低负载系数，open-addressed哈希表将键和值(分别)映射到数组中的索引。这些中的每一个都不过是一个索引数组(或在分配(完整)数组后计算的指针)并且具有不错的缓存性能。

非单射情况

按(非唯一)T2 对对进行排序(或至少分组)值，并在哈希表中存储(对于每个这样的唯一值)运行的开始的索引。然后所有对应的T1可以一起找到对象(停止在第一个不同的 T2 或数组的末尾)。

如果有很多T2 == 的对象并且它们可互换，您可以改为存储单独的 pair<T1,index> 数组和 pair<T2,index> ，每个都将索引存储到另一个，如上所述。 两个 哈希表中的每个条目然后将索引存储到 T1 中数组，因为在哈希查找和 T2 之后始终需要检查哪个键是否相等一对中的对象可以立即明确地从与 T1 一起存储的索引中获得.