Boost.Intrusive和unordered_map

Question

我想要使用一个侵入式的unordered_map。但是库中只有一个unordered_set。还有一个侵入式的哈希表，但我不确定它是否具有相同的功能，而且它的接口也不同。
如果我错了并且错过了unordered_map的链接，那请告诉我。
如果我没有错，是否有教程可以帮助我实现一个unordered_map？

- the_drow

Answer 1

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

在我看来，你有两个选择：

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++。 更新： 我意识到他们为什么不使用地图：侵入式容器要求您将数据结构的节点信息嵌入存储在其中的值类型中。 对于映射，您必须同时对键和值进行此操作。 这并非不可能，但是标准实现 map 使用与 set 相同的内部类型。 但是，这些内部类型只有一个 value_type 变量：为了存储键和值，它们将键和值复制到该变量中，并将其存储在节点中。 要使用侵入式类型（即无需复制）执行此操作，您必须修改该实现类型以与集合不兼容：它必须单独存储键和值的引用。 因此，要执行此操作，您还必须修改所使用的实现（可能是 hashtable）。 再次强调，这并非不可能，但是在没有简单方法实现此操作的情况下，库设计人员很可能决定放弃使用映射。

这样说清楚了吗？

- quark

---

那么这不值得麻烦吗？因为我在考虑时间与质量的权衡。 - the_drow

这是一项相当大的工作。标准容器的接口有很多微妙之处。我认为具有侵入式特性的容器也是如此。如果时间很紧迫，选择选项1。如果你有时间并且想真正学到很多东西，那就选择选项2。 - quark

我是否漏掉了一些显而易见的东西？你肯定可以将键存储在你放置在值类型中的钩子中，它只是钩子的另一部分... 在我看来，侵入式容器的主要优点是它们避免了节点的分配和释放，将键复制到节点中似乎很好... 当然，我需要一个映射，他们做了各种聪明的集合，但没有映射，这真是令人痛苦！ - Len Holgate

Answer 2

虽然这个问题已经被问了很长时间，但我认为来到这里的人应该对如何将unordered_set用作映射表感兴趣。解决方案是使用高级插入方法：只需在同一个value_type中存储键和其值，并使用insert_check和insert_commit进行插入。

- Alexandre Hamez

---

从技术上讲，您甚至不需要高级插入，只需要高级查找（执行find(key)）即可。 - John Zwinck