c++ - boost flat_map 容器

Question

在处理一些遗留代码时，我遇到了内存问题，这主要是(我相信)由于广泛使用 STL map (特别是“ map 中的 map ”)。

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

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

举个例子:在这个map-of-a-map的代码中有几种情况；也就是说，一个 map ，其中的值是另一个 map 。

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

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

Answer 1

Boost 的 flat_map 是一个基于二叉树的映射实现，除了二叉树存储为键值对的(排序的) vector 。

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

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

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

您可能还想阅读 Boost 的 documentation of flat_map ;你也可以使用武力阅读the source (和 source of the underlying flat_tree )-就像我一样；我实际上没有 flat_map 经验。