内存高效的std::map替代方案

Question

我正在使用 std::map 存储大约 2000 万条目。如果不带任何容器开销存储它们，需要大约 650MB 的内存。然而，由于它们是使用 std::map 存储的，因此使用了大约 15GB 的内存（即太多了）。

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

有没有替代使用 std::map（或有序映射一般）会导致更少的内存使用？

编辑：写入性能比读取性能重要得多。它可能只读取 ~10 条目，但我不知道它将读取哪些条目。

- MiJyn

---

值与键相比有多大？ - Bathsheba

你使用哪些数据类型作为键/值？你需要执行哪些查询？你的数据集是静态的吗？ - m.s.

为什么你需要将其存储在内存中，而不是在任何数据库中处理？ - stas.yaranov

这是一个非常重要的考虑因素（也许需要修改问题以反映这一点）。对我来说，这可能会排除基于插入排序的解决方案。 - Bathsheba

如果在执行任何查询之前，所有数据都已经写入，您可以尝试使用deque（我通常建议使用排序的vector，但我不确定您的平台是否提供650MB的连续存储）来存储所有数据点 - 随后进行一次排序操作，然后使用upper_bound和/或lower_bound进行查询。 - Gavi Lock

Answer 1

结果发现问题不是在于std::map。

我意识到使用了三个分开的地图来表示同一数据的各个部分，将其缩减为一个后，内存差异完全可以忽略不计。

再仔细查看代码，发现我编写的释放非常昂贵的结构体（每个地图元素）的代码实际上并没有生效。

修复该部分后，它现在使用的内存少于1GB，正如它应该的那样！ :)

简而言之：std::map的开销对此完全可以忽略不计。问题出在我自己身上。

- MiJyn

Answer 2

一种替代方案是使用Boost.Containers中的flat_map：它支持与std::map相同的接口，但是由排序的连续数组（类似于std::vector）而不是树来支持。或者你也可以基于这个想法自己写一个解决方案。

由于后端不同，性能特性当然也会有所差异。需要您评估它是否适合您的情况。

- Angew is no longer proud of SO

---

虽然这可能会减少内存使用，但插入性能太慢了（我估计慢了几百倍）。 - MiJyn

Answer 3

你是在实时写入还是在查找之前一次性写入？如果是后者，你不需要使用 map，可以使用 std::vector 和一次性排序。你可以将所有未排序的元素插入向量中，在所有元素都在那里后进行一次排序（O(N * log N) 和 std::map 相同，但具有更好的性能特征），然后在排序数组（O(logN) 如 std::map）中查找。如果您知道读取之前元素的数量并且可以预先保留向量大小，则可能效果很好。或者至少如果您知道一些“上限”，可以略微超出实际所需但避免重新分配。

- EmDroid

Answer 4

鉴于您的要求：

1. 插入需要快速完成； 2. 有许多元素需要读取； 3. 读回可能很慢； 4. 您只会读取一次数据。

我建议使用 typedef std::pair<uint64, thirty_six_byte_struct> element; 并填充一个 std::list<element>。从性能上考虑，这将很难被超越。

对于读回，我建议简单地遍历链表，并在每个点检查是否需要其中一个元素。虽然这是 O(N) 的遍历，但正如您所说，您只需要执行一次。

- Bathsheba

---

似乎这是正确的数据结构，因为需求列表根本不在内存中。 - UKMonkey