c++ - C/C++ MultiMap 库

Question

我存储了 1.11 亿个键值对(一个键可以有多个值 - 最大 2/3)，它们的键是 50 位整数，值是 32 位(最大)整数。现在，我的要求是:

1. 快速插入(键，值)对[允许重复]
2. 基于键快速检索值。

有没有解决这个问题的 C/C++ 库(使用 MultiMap、B+ Tree、B Tree、R+ Tree 等)？我可以为此提供 5/6 GB 的主内存。更多信息:my previous post .

Answer 1

因为“5/6 GB”实际上意味着 5 或 6 GB...

具有 50 位键和 32 位值的 111000000 个键/值对将占用 (111000000 * (50+32))/(8*1024*1024*1024) = 1.05 GB 或存储为紧密压缩(位)数组时的内存.

你的内存是那个的 5 倍。

在 64 位系统上，一个 10 层深度的基于跳跃列表的 map 在最坏的情况下需要 (111000000 * (64+32+10*16))/(8*1024*1024*1024) = 3.308 GB，而你仍然会有超过 GB 的 RAM 来处理堆管理开销。

所以我建议获取任何可用的 multimap 并尝试使用它 - 在我看来，您有足够的内存来处理您的情况，而无需使用任何额外的技巧。

--编辑--

Actually, I don't know C/C++

那么，如果您不懂 C++，您希望如何使用包含 111000000 个键的映射？您必须阅读一些内容。

标准库包括 std::multimap，boost 库中有几个类。 Qt 4 包括基于跳跃列表的 QMap。尝试使用其中任何一个。