提问人：einpoklum 提问时间：4/27/2018 最后编辑：einpoklum 更新时间：4/28/2018 访问量：163
boost：：bimap 对于注入函数来说是否矫枉过正？
Is boost::bimap overkill for injective functions?
问：
设 T_1 和 T_2 是两种类型，f： Dom（T_1） -> Dom（T_2） 是一个不是双射的注入函数;为了便于讨论，假设我得到一个 f 的表示作为不同的对，而不是用于计算它的代码。现在，我需要能够相对快速地同时应用 f 和 f^{-1}，所以我正在考虑每个方向的地图。然后我想到，我可能想要将这两个地图的数据结构放在一起 - 因为我有多个这样的 f。
我自然而然地想到“嗯，我敢肯定 Boost 一定有这样的东西”，事实上，Boost 有一个 Bimap 结构。问题是，一个是用于一般二元关系的;此外，它必须考虑重复插入的可能性，而无需每次都重新优化结构，而在我的情况下，我只插入一次，然后进行多次查找。所以，我觉得 bimap 对我来说可能有点矫枉过正，而且没有针对我的用例进行优化。这是真的吗？
笔记：
- 我对时间复杂性（和实际时间）感兴趣，但以牺牲空间为代价。
- 非注入式 f 也有同样的问题（其中 f^{-1} 是非函数关系）。
答：
0赞
Davis Herring
4/28/2018
#1
正常的 C++ 容器行为（通过您关于对象大小的提示得到强化）是仅存储一次每个键和值（这些概念仅在非注入情况下是不同的）。单独的插入和查找阶段建议连续存储（如果没有其他方法，则用于缓存位置）。“以牺牲空间为代价的时间”说你想要一个哈希表。
因此，存储一个数组和一对低负载因数、开放寻址的哈希表，将键和值（分别）映射到数组中的索引。它们中的每一个都只不过是一个索引数组（或在分配（完整）数组后计算的指针），并且具有不错的缓存性能。pair<T1,T2>
非注射式案例
按（非唯一）值对进行排序（或至少分组），并将运行开始的索引存储在哈希表中（对于每个此类唯一值）。然后可以一起找到所有相应的对象（停在第一个不同的对象或数组的末尾）。T2T1T2
如果有许多对象是 和 它们是可互换的，您可以改为存储单独的 和 数组，每个数组将索引存储到另一个中，如上所述。然后，两个哈希表中的每个条目都将索引存储到数组中，因为在哈希查找后始终需要哪个键来检查相等性，并且一对中的对象可以立即明确地从与 一起存储的索引中获取。T2==pair<T1,index>pair<T2,index>T1T2T1
评论