std::map内存分配节点压缩？

Question

我注意到Visual Studio（2010）的std::map实现为其红黑树中的每个节点分配一个新的单独的内存块。也就是说，对于映射中的每个元素，都会通过operator new ... malloc使用std::map的默认分配方案来分配一个新的原始内存块。

这对我来说似乎有些浪费：难道不应该像std::vector实现一样，在块中以“(小) n”分配节点吗？

因此，我想澄清以下几点：

• 我的默认分配方案的说法是否正确？
• “所有”std::map的STL实现是否都是这样工作的？
• std中是否有任何东西阻止std::map实现将其节点放入内存块中，而不是为每个节点分配一个新的内存块（通过其分配器）？ （复杂度保证等）？

注意：这不是关于过早优化的问题。如果涉及优化，则涉及的是，如果应用程序存在(std::)map内存碎片问题，是否存在使用内存池的自定义分配器以外的替代方法？这个问题不是关于自定义分配器，而是关于映射实现如何使用其分配器的。(或者我希望它是这样的。)

- Martin Ba

---

作为替代方案，对于小型映射/集合，您可能希望使用Loki :: AssocVector，它在vector上实现了map接口（但不是其失效条件），以获得更好的性能。 - Matthieu M.

Answer 1

对于大多数std :: map实现，您的断言是正确的。

据我所知，标准中没有阻止map使用您描述的分配方案。但是，您可以通过自定义分配器来获得所需的方案 - 但将该方案强加于所有映射可能会很浪费。因为map没有先验知识，无法预测它将如何使用，某些使用模式可能会阻止释放大部分未使用的块。例如，假设为4个节点一次分配块，但特定的map填充了40个节点，然后删除了30个节点，留下最坏情况下每个块仅剩一个节点，因为map无法使指向该最后节点的指针/引用/迭代器失效。

- Fred Nurk

Answer 2

当您向地图中插入元素时，保证现有的迭代器不会失效。因此，如果您在两个连续且在同一堆分配区域内的节点A和C之间插入一个元素“B”，则不能将它们移动以腾出空间，而必须将B放在其他位置。我认为这没有什么特别的问题，除了管理这种复杂性将增加实现的复杂度。如果您删除元素，则迭代器也不能失效，这意味着任何内存分配都必须保留，直到其中所有节点都被删除。您可能需要在每个“扩展节点”/向量/无论您想称之为什么的东西中使用自由列表-有效地复制目前由new/delete为您执行的至少一些耗时操作。

- Tony Delroy

---

在没有或只有少量节点被删除的情况下，分配单个大块是否有帮助？在这种情况下，似乎可以不使用freelist，而只需增加块内的指针。 - Alex Jasmin

@Alexandre：只有在块仍然排序的情况下（记住，您无法重新排序，因为无法移动元素），少量节点被删除，并且没有进行“B”插入时，通过指针增量迭代才是理想的。如果地图是通过顺序插入填充的，则可能会发生这种情况，但否则似乎不太可能。现有连续“A”和“B”之间的“B”插入意味着在块中找到其他B，或在该点插入到另一个块的链接。跟踪任何一个都很痛苦。 - Tony Delroy

我认为你混淆了内存分配方案（池分配）和表示层（红黑树）。当你插入一个新节点时，没有必要在内存中重新排列节点，你只需要更新一些指针即可。 - Matthieu M.

@Matthieu：我很困惑，不知道我可能是如何混淆的。关于“不需要洗牌节点”——我已经非常明确地说过，如果没有破坏std::map现有的迭代器有效性保证，我们是不能洗牌节点的。在这种约束条件下，我探索了如何创建或暗示树结构：如果我们为树分配独立的节点，那么有更大的块就毫无意义，因此我们需要探索跟踪分配块内部元素的方式——可选的自由列表。如果你认为我们还需要一个指针的“子树”空间在分配块内和下面，那我同意... - Tony Delroy

我在谈论你回答中的这部分内容：“因此，如果您在两个节点A和C之间插入一个元素“B”，它们碰巧是连续的并且位于同一堆分配区域内，则无法将它们洗牌以腾出空间，而B将不得不放在其他地方。” 在内存中不需要洗牌A或C，OP没有要求将A、B和C放置在连续的位置上，因此可以将B放在另一个块（内存分配方案）中，然后更新A和C指针以包括B在树（红黑树层）中。我确实同意帖子中的管理部分。 - Matthieu M.

Answer 3

我相当确定我从未见过实现std::map尝试将多个节点合并到单个分配块中的情况。至少我一时半会想不出它为什么不能工作，但我认为大多数实现者会认为这是不必要的，并且将内存分配的优化留给分配器而不是在map内部过于担心。

诚然，大多数自定义分配器都是编写来更好地处理大量小块的分配。通过编写map（当然还有set，multiset和multimap），您可能可以使绝大多数这样的优化变得不必要，只需使用较大的分配即可。另一方面，鉴于优化小块分配的分配器易于/常见/广泛可用，因此可能没有太多动力以这种方式更改map实现。

- Jerry Coffin

Answer 4

我认为你唯一不能做的事情就是使迭代器无效，如果你必须重新分配存储空间，那么你可能需要这样做。话虽如此，我见过使用单个排序对象数组包装在std::map接口中的实现。当然，这是有原因的。

实际上，你可以使用自定义分配器来实例化你的std::map，它将以一种特殊的、非浪费的方式为新节点找到内存。

- cababunga

---

如果你在谈论uSTL，那么它的创建者认为复杂性保证是可选的，并且不理解无效语义！这只是一个可怕的库。每个容器都是在vector上实现的：list继承vector，而deque是list的宏！你不能使用单个排序数组正确编写std::map。 - Fred Nurk

如果你不是在谈论uSTL，那你在哪里见过它？ - Fred Nurk

几年前我在一家公司工作时，他们开发了一个实现。但我记得在其他地方看到过类似的东西，也许那是uSTL，我不确定。 - cababunga

Answer 5

这对我来说似乎有点浪费。按照 std::vector 实现方式，将节点分配到“(小) n”块中，会更有意义，不会吗？

有趣的是，我从完全不同的角度看待它。我认为它是合适的，并且不浪费任何内存。至少在 Windows（MS VS 2008）、HP-UX（带有 STLport 的 gcc）和 Linux（没有 STLport 的 gcc）上使用默认 STL 分配器时是如此。重要的是这些分配器关心内存碎片问题，而且似乎能够很好地处理这个问题。例如，在 Windows 上查找“低碎片堆”或在 HP-UX 上查找 SBA（小块分配器）。我的意思是，只为一个节点频繁地分配和释放内存不一定会导致内存碎片。我在我的一个程序中自己测试了 std::map，它确实没有使用这些分配器导致任何内存碎片。

“默认分配方案”的断言是否正确？

我有MS VisualStudio 2008，它的std::map表现方式相同。在HP-UX上，我使用带有和不带有STLport的gcc，它们似乎对于在std::map中为节点分配内存采用了相同的方法。

是否有任何std中的内容 防止std::map实现将其节点放入内存块中 而不是为每个节点分配新的内存块（通过其分配器）？

如果可能的话，请从调整平台上的默认分配器开始。在这里引用Douglas Lea的话语非常有用，他是DL-Malloc的作者。

......首先我用C++编写了许多专用分配器，通常是通过为各种类重载operator new来实现的。然而，我很快意识到，在构建我当时正在编写的一些通用编程支持类时，为每个新类构建一个特殊的分配器并不是一个好策略，因为这些类往往是动态分配和大量使用的。(从1986年到1991年，我是GNU C++库libg++的主要作者。)需要一个更广泛的解决方案——编写一个足够好的分配器，在正常的C++和C负载下表现良好，以便程序员不会在非常特殊的情况下被诱导编写专用分配器。

或者，您甚至可以尝试使用Hoard分配器测试您的应用程序。我的意思是，只需测试您的应用程序，并查看是否存在性能或碎片化方面的任何优势。

- user184968