哈希表/无序映射的解耦版本

Question

我正在编写一个嵌入式应用程序，但我使用的环境目前不支持C++11。

我需要实现哈希/无序映射（普通的std::map由于性能原因不适用），但似乎找不到干净的方法。

Boost库不想工作而必须引入整个库。即使是SGI的原始STL hash_map也需要多个头文件，并且重复了标准库功能，导致函数调用不明确。这真是一团糟。

为了方便实现、版本控制、质量控制、验证和确认等，我真的需要利用现有的标准库，并存在只有少数头文件的地方，我可以将其放在与所有其他源/头文件相同的文件夹中。是否存在这样的东西，或者我没有希望？ 我已经搜索了很长时间，但没有结果。

非常感谢任何帮助。如有必要，我可以进一步澄清。

- llakais

---

我从未遇到过平衡导致明显的性能问题的情况。你确定这是事实吗？RB-Tree 的平衡非常快，它只会在树非常不平衡时才进行平衡。 - Mooing Duck

你的环境中是否有 stdext::hashmap 或类似的东西？MSVC 已经拥有它超过10年了。 - Mooing Duck

很遗憾，环境中没有stdext或类似的东西。我猜这是因为它是针对嵌入式系统的，而且更为专业化，因此一般扩展要少得多。 - llakais

在某些情况下，无序性可能会更快。在其他一些情况下，哈希映射会慢得多。这取决于许多因素。我认为在一般情况下，无序性往往更快。 - Mooing Duck

尝试使用[Google Sparsehash]（http://code.google.com/p/google-sparsehash/）或[MCT]（https://launchpad.net/libmct/）进行编程。两者都是带有哈希映射的小型库，但它们实现了封闭哈希，而不像`std :: unordered_map` - 这可能是一个问题，请参阅比较。 - user319799

Answer 1

你看过GNU实现吗？在我的Ubuntu机器上，unordered_map.h没有包含任何内容。这个文件位于...

    /usr/include/c++/4.6/bits/unordered_map.h

这是关于 IT 的内容，大约有 400 行，尽管在 /usr/include/c++/4.6/ 中的 "unordered_map" 文件有更多的头文件，但你可以调整它们。

我认为你可以从 GNU.org (?) 找到实现的源代码并自己编译？

- CS Pei

---

我也会在我的Ubuntu上检查一下，谢谢你的提示！ - llakais

很抱歉这么晚才查看......我认为你是对的，确实需要包含顶级文件夹中的“unordered_map”文件，但我认为有些调整可以减少我需要引入的文件总数。无论如何，这比使用旧的SGI STL好得多。再次感谢。 - llakais