具有整数键的 C++ 高效且紧凑的映射

Question

我有 200 组大约 50,000 个范围在 0 到 500,000 之间的唯一整数，我需要映射到另一个小值（一对整数，值不相关，因此不需要按需计算）。

我尝试使用 std::unordered_maps，这使用了大约 50MB（在 VS2015 堆诊断工具中测量），虽然性能很好，但我希望降低此内存使用量（打算成为一些小型 500MB 云服务器上的后台服务） 。

实际上我的初始版本是 200 个单独的std::unordered_map<int, std::pair<int, int>>.

一种选择似乎是排序数组并使用二分搜索，但还有其他选择吗？

Answer 1

我认为排序向量应该可以工作，如果你在排序后不改变向量的话。它确实非常节省空间，即没有指针开销。

如果您需要更好的性能，并且不介意某些第三方库。您可以尝试稀疏哈希映射，它以很少的空间开销实现哈希映射。