c++ - C/C++ 多地图库

Question

我存储了 1.11 亿个键值对（一个键可以有多个值 - 最大 2/3），其键是 50 位整数，值是 32 位（最大）整数。现在，我的要求是：

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

是否有任何 C/C++ 库可以解决这个问题（使用 MultiMap、B+ 树、B 树、R+ 树等）？我可以为此提供 5/6 GB 的主内存。欲了解更多信息：我以前的帖子。

Answer 1

C 中的普通哈希表每个元素需要 50+32 (+14padding) + 32 +32 位。（+ 可能是 32 位对齐）。即每个元素 160（或 192）位：= 每个元素 20（或 24）字节。哈希表将花费您 111*20（或 111*24）MB 的内存。那是 2.2 GB 或 2.7 GB。

Answer 2

您的要求不包括任何订购集合的需要。使用哈希映射。如果您找不到现成的，那么创建一个并不是什么大挑战。

Answer 3

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

具有 50 位键和 32 位值的 111000000 个键/值对在存储为紧密打包（位）数组时将占用 (111000000 * (50+32))/(8*1024*1024*1024) = 1.05 GB 或内存。

你的内存是那个的 5 倍。

在 64 位系统上基于 10 级深度跳过列表的映射在最坏的情况下将占用 (111000000 * (64+32+10*16))/(8*1024*1024*1024) = 3.308 GB，您仍然会有超过千兆字节的 RAM 来处理堆管理开销。

所以我建议抓住任何可用的多图并尝试使用它——在我看来，你有足够的内存来处理你的情况，而无需使用任何额外的技巧。

- 编辑 -

其实我不懂C/C++

好吧，如果您不懂 C++，您希望如何使用包含 111000000 个键的映射？你必须做一些阅读。

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