Boost flat_map容器

Question

在处理一些遗留代码时，我遇到了内存问题，主要原因是(我相信)大量使用STL映射(特别是“maps of -map”)。

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

有没有人能给我举一些可靠的例子？

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

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

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

Answer 1

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

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

• 迭代地图或大部分地图的速度应该非常快，insert)
• etc.

上的

• 通常相对较快，
• 添加或移除值的速度在理论上要慢得多，但在实践中-假设您的键和值类型很小，并且地图元素的数量不是很多-在速度上可能与之相当(或者在小型地图上甚至更快-在#en1#上通常不需要进行分配

在地图的情况下，你将失去一些“展平事物”的好处，因为你将有一个外部地图，其中有一个指向内部地图的指针(如果不是更多级别的间接的话)；但平面地图至少可以帮助你减少这种情况。此外，假设您有两个级别的map，您可以将其安排为连续地存储所有内部map(通过适当地构造内部map，或者通过使用您自己的分配器实例化它们，这是一件比较棘手的事情)；在这种情况下，您可以用map索引替换指向map的指针，从而减少它们占用的空间量，并使编译器的工作变得更容易。

你可能还想读Boost的documentation of flat_map；而且你也可以像我一样使用force来读the source (和source of the underlying flat_tree) --我自己实际上没有flat_map经验。

Answer 2

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

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

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