c++ - Boost.Intrusive 和 unordered_map

Question

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

Answer 1

这是一个有趣的问题。 Boost.Intrusive 似乎没有提供任何 map 接口(interface)，无论是有序的还是无序的。它有很多实现类型，可以很好地作为有序(红黑树、AVL 树、splay 树)和无序(哈希表)映射。但是没有 map ，我无法告诉你原因。

我认为你有两个选择:

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

我已经完成了后者。这有点乏味，我强烈建议为它编写单元测试(或窃取 libstdc++ 或 Boost.Intrusive 附带的单元测试)。但这是可行的。我还强烈建议阅读 SGI(set、map)或 libstdc++ 上的集合和映射的需求文档。

更新:我意识到他们为什么不做映射:侵入式容器要求您将数据结构的节点信息嵌入到您存储在其中的值类型中。对于映射，您必须对值 和键 都执行此操作。并不是说这是不可能的，而是 map 的标准实现使用与 set 相同的 内部类型做。但是那些内部类型只有一个 value_type变量:为了存储键和值，他们将键和值复制到该变量中并将其存储在节点中。要使用侵入式类型(即不复制)来做到这一点，您必须修改该实现类型以使其与集合不兼容:它必须单独存储对键和值的引用。所以要做到这一点，你还必须修改你使用的实现(可能是 hashtable )。同样并非不可能，但库设计者可能会尝试避免严重的代码重复，因此在没有简单的方法来实现这一点的情况下，他们很可能决定将映射排除在外。

这有意义吗？