高效内存std :: map替代

Question

我正在使用std::map来存储大约2000万个条目。如果存储它们时没有任何容器开销，那么将需要大约650MB的内存。但是，由于它们是使用存储的std::map，因此会占用约15GB的内存（即过多）。

我使用an的原因std::map是因为我需要找到等于/大于/小于的键x。这就是为什么类似的东西sparsehash行不通的原因（因为使用它，我无法通过比较找到密钥）。

是否有替代使用std::map（或通常使用有序映射）的方法，从而减少了内存使用量？

编辑：写性能远高于读取性能更重要。它可能只会读取约10个条目，但我不知道它将读取哪些条目。

Answer 1

事实证明问题不是 std::map。

我意识到使用 3 个独立的映射来表示相同数据的不同部分，在将其缩小到 1 后，内存中的差异完全可以忽略不计。

进一步查看代码，我意识到我编写的用于释放非常昂贵的结构（映射的每个元素）的代码实际上不起作用。

修复该部分后，它现在使用 <1GB 内存，这是应该的！:)

TL;DR: std::map对此的开销完全可以忽略不计。问题是我自己的。

Answer 2

一种替代方法是使用Boost.Containersflat_map ：它支持与Boost.Containers 相同的接口，但由排序的连续数组（想想）而不是树支持。或者基于相同的想法手动推出您自己的解决方案。std::mapstd::vector

由于后端不同，其性能特点当然也不同。由您来评估它是否适用于您的情况。

Answer 3

您是在进行即时写还是一次完成查找？如果是后一种情况，则不需要映射，可以使用std::vector和一次性排序。

您可以将所有未排序的内容插入向量，在所有内容都排序之后一次排序（O（N * log N）以及std::map，但性能特性要好得多），然后在排序后的数组中查找（O（logN）作为std::map）。

尤其是如果您在读取之前知道元素的数量并且可以提前保留向量大小，那么效果会很好。或者，至少，如果您知道某个“上限”，可以保留的部分可能比实际需要的略多，但要避免重新分配。