2

在处理一些遗留代码时，我遇到了内存问题，主要是（我相信）由于 STL 映射的广泛使用（特别是“maps-of-maps”。）

我正在将 Boost flat_map 视为一种可能的解决方案。有没有人对 flat_maps 有任何第一手经验，特别是在速度和/或内存使用方面的改进方面？我当然意识到这可能非常依赖于存储的数据类型和存储方式，但仍然对人们的实际体验感到好奇。

谁能指出一些可靠的例子？

举个例子：这个map-of-a-map的代码有几种情况；也就是说，值是另一个映射的映射。

通过用一对向量替换“内部”映射，我将内存占用减少了 10:1（3G 到 300M）。当然，这会减慢搜索速度，但对于这种特殊情况，这似乎并不重要。它涉及大约一天的重构和仔细测试。

Boost 的 flat_map 听起来可能正是我所需要的，但除了 Boost 网站上的类描述之外，我似乎找不到太多关于它的信息。寻找一些第一手的反馈。

4

2 回答 2

3

Boostflat_map是一个基于二叉树的映射实现，除了二叉树存储为键值对的（排序的）向量。

你基本上可以找出关于性能的答案（相对于std::map你自己基于这个事实：

  • 迭代地图或大部分地图应该是超快的，相对
  • 查找通常应该相对较快
  • 添加或删除值在理论上要慢得多，但在实践中 - 假设您的键和值类型很小并且映射元素的数量不是很高 - 可能在速度上相当（或者在小型映射上甚至更好 - 通常在插入时不需要分配)
  • 等等

在您的情况下-地图的地图-您将失去“将事物展平”的一些好处，因为您将拥有一个带有指向内部地图的指针的外部地图（如果不是更多的间接级别） ; 但是平面地图至少可以帮助您减少这种情况。此外，假设您有两个级别的映射，您可以安排它以便连续存储所有内部映射（通过适当地构建内部映射或使用您自己的分配器实例化它们，这是一个更棘手的事情）；在这种情况下，您可以用映射索引替换指向映射的指针，从而减少它们占用的空间量并使编译器的工作更轻松。

您可能还想阅读 Boost 的文档flat_map；你也可以像我一样使用力量并阅读源代码（以及底层的源代码flat_tree）；我flat_map自己其实没有经验。

于 2017-01-29T18:11:53.423 回答
1

我知道这是一个老问题，但这可能对发现这个问题的人有用。

我发现这flat_map在搜索、查找和迭代大型地图方面有了很大的改进。地图在内存中使用连续数据的事实也使得插入速度比您预期的要快，因为数据局部性很大。如果您在地图中执行的插入操作多于查找操作，那么它可能不适合您。

话虽如此，由于数据局部性，将随机值重复插入已排序的向量比链表上的相同更快 - 尽管大 O 可能会告诉你。（在 VS2017 和 G++ 4.8 中测试）。

于 2018-02-12T13:53:42.003 回答