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几乎肯定会发生类似的事情。您需要查看map和set接口之间的差异，并将其用作修改unordered_map into map的基础。

我做了后者。这有点单调乏味，我强烈建议为它编写单元测试（或者窃取libstdc ++或Boost.Intrusive附带的单元测试）。但这是可行的。我还强烈建议您在SGI上阅读集合和地图的需求文档（ set ，地图）或 libstdc ++

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

这有意义吗？

Answer 2

自问这个问题以来已经有很长一段时间了，但我认为来这里的人应该对如何使用unordered_set作为地图感兴趣。解决方案是使用高级插入方法：一个只需要存储一个键及其在同一个value_type中的值，并使用 insert_check 和 insert_commit 。