时间戳

首页 > 解决方案 > boost::bimap 对内射函数来说是不是矫枉过正？

c++ - boost::bimap 对内射函数来说是不是矫枉过正？

问题描述

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

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

笔记：

标签： c++data-structuresbimapboost-bimap

解决方案

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

因此，存储一个数组pair<T1,T2>和一对低负载因子、开放地址的哈希表，将键和值（分别）映射到数组中的索引。这些中的每一个都只是一个索引数组（或在分配（完整）数组之后计算的指针），并且具有不错的缓存性能。

非内射情况

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

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

推荐阅读