我希望使用侵入性的 unordered_map。由于某种原因,库中只有一个 unordered_set 。还有一个侵入式哈希表,但我不确定它是否具有相同的功能,而且它没有相同的接口。
我错了吗,我错过了 unordered_map 链接吗?
如果我没有,是否有教程可以帮助我实现?
这是一个有趣的问题。 Boost.Intrusive似乎没有提供任何地图接口,无论是有序还是无序。它有很多实现类型,无论是有序映射(红黑树、AVL 树、展开树)还是无序映射(哈希表),都可以很好地工作。但没有地图,我无法告诉你原因。
在我看来,你有两个选择:
- 只需使用
hashtable
:无序容器被实现为哈希表(这是它们不被实现的唯一原因called hash_map
是为了避免与已经使用该名称的现有库发生名称冲突)。如果你想完成你的工作,这会起作用。
- 如果你真的想实现自己的,你想看看Boost.Intrusive的接口描述无序集 http://www.boost.org/doc/libs/1_39_0/doc/html/intrusive/unordered_set_unordered_multiset.html。我没有看过它的实现,但它几乎可以肯定是一种或多种树类型的包装。
std::set
and std::map
两者通常都实现为红黑树的包装器(在我看过的所有标准库实现中:GCC、MSVC 和 Apache 的 stdcxx)。还要了解 libstdc++ 如何将其树实现包装在<map>
and in <set>
。它有很多样板文件,其中大部分都很乏味,但这两种类型都将几乎所有工作都推迟到树上。 Boost.Intrusive 几乎肯定会发生类似的情况unordered_set
。您将需要查看map和set接口之间的差异,并将其作为修改的基础unordered_set
into unordered_map
.
我已经做了后者。这有点乏味,我强烈建议为其编写单元测试(或者窃取 libstdc++ 或 Boost.Intrusive 附带的单元测试)。但这是可行的。我还强烈建议您阅读 SGI 中的集合和地图的要求文档(set http://www.sgi.com/tech/stl/set.html, map http://www.sgi.com/tech/stl/map.html)或对于libstdc++ 库 http://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-3.4/group___assoc__containers.html
Update:我意识到为什么他们不做映射:侵入式容器要求您将数据结构的节点信息嵌入到您存储在其中的值类型中。对于地图,您必须对两个值执行此操作和钥匙。并不是说这是不可能的,而是一个标准实现map
使用same内部类型为set
是的。但那些内部类型只有one value_type
变量:为了存储键和值,它们将键和值复制到该变量中并将其存储在节点中。要使用侵入式类型(即不复制)来做到这一点,您必须修改该实现类型以使其与集不兼容:它必须存储对键和值的引用分别地。因此,要做到这一点,您还必须修改您使用的实现(可能hashtable
)。同样并非不可能,但库设计者可能会试图避免严重的代码重复,因此在缺乏简单方法来实现这一点的情况下,他们很可能决定将地图排除在外。
那有意义吗?
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)