Boost.Intrusive和unordered_map

Question

我希望使用侵入式unordered_map.由于某种原因,库中只有一个unordered_set.还有一个侵入式散列表,但我不确定它是否具有相同的功能,也没有相同的接口.
我错了,我错过了unordered_map链接？
如果我不是,那么有一个教程可以帮助我实现一个吗？

Answer 1

这是一个有趣的问题.Boost.Intrusive似乎没有提供任何有序或无序的地图界面.它有很多实现类型可以正常工作,因为它们都是有序的(红黑树,AVL树,splay树)和无序(hashtables).但没有地图,我无法告诉你原因.

我看到你有两个选择:

1. 只需使用hashtable:无序容器实现为哈希表(并且它们未被调用 的唯一原因hash_map是避免与已使用该名称的预先存在的库发生名称冲突).如果你想完成你的工作,这将有效.
2. 如果你真的想要实现自己的,你想看看Boost.Intrusive的unordered_set的接口描述.我没有看过实现,但几乎可以肯定它是一个或多个树类型的包装器. std::set并且std::map通常都是作为红黑树周围的包装器实现的(在我看过的所有标准库实现中:GCC,MSVC和Apache的stdcxx).还要了解libstdc ++如何将其树实现包装<map>在其中<set>.这是很多样板文件,其中大部分内容繁琐,但两种类型都将几乎所有的工作推迟到树上.类似的东西几乎肯定会发生在Boost.Intrusive上unordered_set.您需要看地图和组接口之间的差异,并用它作为修改的基础上unordered_set进入unordered_map.

我做了后者.这有点单调乏味,我强烈建议为它编写单元测试(或者窃取libstdc ++或Boost.Intrusive附带的单元测试).但这是可行的.我还强烈建议您在SGI(set,map)或libstdc ++中阅读集合和映射的需求文档

更新:我意识到他们为什么不做地图:侵入式容器要求您将数据结构的节点信息嵌入到您存储在其中的值类型中.对于地图,您必须为值和键执行此操作.这不是不可能的,但是a的标准实现map使用与set s 相同的内部类型.但是那些内部类型只有一个 value_type变量:存储键和值,它们将键和值复制到该变量中并将其存储在节点中.要做到这一点与侵入型(即不复制),你就必须修改实现类型是带套不兼容的:它具有存储键和值参考分开.所以要做到这一点,你还必须修改你使用的实现(可能hashtable).同样不是不可能,但图书馆设计师可能会试图避免严重的代码重复,因此在没有简单的方法实现这一点的情况下,他们很可能决定将地图留下.

那有意义吗？

Answer 2

自问这个问题已经有很长一段时间了,但我认为来这里的人应该对如何使用unordered_set地图感兴趣.解决方案是使用高级插入方法:只需将密钥及其值存储在同一个插入方法中value_type,然后使用insert_check和插入它insert_commit.