内存效率 std::map 替代方案
Memory efficient std::map alternative
我正在使用 std::map 来存储大约 2000 万个条目。如果在没有任何容器开销的情况下存储它们，将需要大约 650MB 的内存。但是，由于它们是使用 std::map 存储的，它会占用大约 15GB 的内存（即太多）。
我使用 std::map 的原因是因为我需要找到 to/larger/smaller 等于 x 的键。这就是为什么像 sparsehash 这样的东西不起作用的原因（因为使用它，我无法通过比较找到键）。
除了使用 std::map（或一般的有序映射）之外，是否有其他方法可以减少内存使用量？
编辑：写作表现比阅读表现重要得多。它可能只会读取 ~10 个条目，但我不知道它会读取哪些条目。
一种替代方法是使用 Boost.Containers 中的 flat_map：支持与 std::map 相同的接口，但由排序的连续数组支持（想想 std::vector ) 而不是一棵树。或者根据相同的想法手动推出您自己的解决方案。
它的性能特点当然是不同的，因为后端不同。是否适用于您的情况，由您来评估。
鉴于您的要求：
- 插入速度要快
- 要读的内容很多
- 回读可能很慢
- 您只读一次数据
我会考虑 typedef std::pair<uint64, thirty_six_byte_struct> element; 并填充一个 std::list<element>。这在性能方面将很难被击败。
为了回读，我将简单地遍历链表，检查每个点是否需要这些元素之一。这是一个 O(N) 遍历，但正如你所说，你只会这样做一次。
您是即时写入还是在查找完成前写入一次？如果是后者，你应该不需要地图，你可以使用 std::vector 和一次性排序。
您可以将所有未排序的内容插入到向量中，在所有内容都存在后一次性排序（O(N * log N) 以及 std::map，但性能特征要好得多），然后查找排序后的数组（O(logN) 作为 std::map）。
尤其是如果您在阅读之前就知道元素的数量并且可以预先保留矢量大小，那么效果会很好。或者至少如果你知道一些 "upper bound" 保留可能比实际需要多一点但避免重新分配。
原来问题不是std::map。
我意识到使用 3 个单独的映射来表示同一数据的不同部分，并且在将其缩减为 1 之后，内存差异完全可以忽略不计。
再看一下代码，我意识到我为释放一个非常昂贵的结构（映射的每个元素）而编写的代码实际上没有用。
修复那个部分，它现在使用 <1GB 的内存，这是应该的！ :)
TL;DR: std::map 的开销对此完全可以忽略不计。这个问题是我自己的。
我正在使用 std::map 来存储大约 2000 万个条目。如果在没有任何容器开销的情况下存储它们，将需要大约 650MB 的内存。但是，由于它们是使用 std::map 存储的，它会占用大约 15GB 的内存（即太多）。
我使用 std::map 的原因是因为我需要找到 to/larger/smaller 等于 x 的键。这就是为什么像 sparsehash 这样的东西不起作用的原因（因为使用它，我无法通过比较找到键）。
除了使用 std::map（或一般的有序映射）之外，是否有其他方法可以减少内存使用量？
编辑：写作表现比阅读表现重要得多。它可能只会读取 ~10 个条目，但我不知道它会读取哪些条目。
一种替代方法是使用 Boost.Containers 中的 flat_map：支持与 std::map 相同的接口，但由排序的连续数组支持（想想 std::vector ) 而不是一棵树。或者根据相同的想法手动推出您自己的解决方案。
它的性能特点当然是不同的，因为后端不同。是否适用于您的情况，由您来评估。
鉴于您的要求：
- 插入速度要快
- 要读的内容很多
- 回读可能很慢
- 您只读一次数据
我会考虑 typedef std::pair<uint64, thirty_six_byte_struct> element; 并填充一个 std::list<element>。这在性能方面将很难被击败。
为了回读，我将简单地遍历链表，检查每个点是否需要这些元素之一。这是一个 O(N) 遍历，但正如你所说，你只会这样做一次。
您是即时写入还是在查找完成前写入一次？如果是后者，你应该不需要地图，你可以使用 std::vector 和一次性排序。
您可以将所有未排序的内容插入到向量中，在所有内容都存在后一次性排序（O(N * log N) 以及 std::map，但性能特征要好得多），然后查找排序后的数组（O(logN) 作为 std::map）。
尤其是如果您在阅读之前就知道元素的数量并且可以预先保留矢量大小，那么效果会很好。或者至少如果你知道一些 "upper bound" 保留可能比实际需要多一点但避免重新分配。
原来问题不是std::map。
我意识到使用 3 个单独的映射来表示同一数据的不同部分，并且在将其缩减为 1 之后，内存差异完全可以忽略不计。
再看一下代码，我意识到我为释放一个非常昂贵的结构（映射的每个元素）而编写的代码实际上没有用。
修复那个部分，它现在使用 <1GB 的内存，这是应该的！ :)
TL;DR: std::map 的开销对此完全可以忽略不计。这个问题是我自己的。