11

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

4

2 回答 2

7

这是一个有趣的问题。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. 您将需要查看 map 和 set 接口之间的差异，并将其用作修改unordered_set为unordered_map.

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

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

那有意义吗？

于 2009-07-31T17:24:22.143 回答
6

很久没有问这个问题了，但我认为来这里的人应该对如何使用 anunordered_set作为地图感兴趣。解决方案是使用高级插入方法：只需将一个键和它的值存储在同一个中，然后使用andvalue_type插入它。insert_checkinsert_commit

于 2012-07-26T12:44:11.220 回答