我注意到 Visual Studio (2010) 的 std::map 实现为其红黑树中的每个节点分配了一个新的单个内存块。也就是说，对于映射中的每个元素，将使用 Visual Studio STL 实现的 std::map 的默认分配方案通过运算符 new ... malloc 分配一个新的原始内存块。 。
这对我来说有点浪费：将节点分配在“（小）n”块中不是更有意义吗，就像 std::vector 实现在增长时过度分配一样？
所以我想澄清以下几点：
- 我关于默认分配方案的断言实际上是正确的吗？
- std::map 的“所有”STL 实现都是这样工作的吗？
- std 中是否有任何内容阻止 std::map 实现将其节点放入内存块中，而不是为每个节点分配新的内存块（通过其分配器）？ （复杂性保证等）？
注意：这与过早优化无关。 如果是关于优化，那么如果应用程序存在 (std::)map 内存碎片问题，是否有其他方法可以替代使用使用内存池的自定义分配器？这个问题不是关于自定义分配器，而是关于映射实现如何使用其分配器。 （或者我希望如此。）
I have noticed that the std::map implementation of Visual Studio (2010) allocates a new single block of memory for each node in its red-black tree. That is, for each element in the map a single new block of raw memory will be allocated via operator new ... malloc with the default allocation scheme of the std::map of the Visual Studio STL implementation.
This appears a bit wasteful to me: Wouldn't it make more sense to allocate the nodes in blocks of "(small) n", just as std::vector implementations over-allocate on growth?
So I'd like the following points clarified:
- Is my assertion about the default allocation scheme actually correct?
- Do "all" STL implementations of std::map work this way?
- Is there anything in the std preventing a std::map implementation from putting its nodes into blocks of memory instead of allocation a new block of memory (via its allocator) for each node? (Complexity guarantees, etc.)?
Note: This is not about premature optimization. If its about optimization, then its about if an app has problem with (std::)map memory fragmentation, are there alternatives to using a custom allocator that uses a memory pool? This question is not about custom allocators but about how the map implementation uses its allocator. (Or so I hope it is.)
发布评论
评论（5）
您的断言对于 std::map 的大多数实现都是正确的。
据我所知，标准中没有任何内容阻止地图使用您所描述的分配方案。但是，您可以使用自定义分配器获得您所描述的内容 - 但在所有地图上强制使用该方案可能会造成浪费。由于地图不知道如何使用它，某些使用模式可能会阻止对大多数未使用的块进行重新分配。例如，假设一次为 4 个节点分配块，但特定映射填充了 40 个节点，然后擦除了 30 个节点，最坏的情况是每个块留下一个节点，因为映射无法使指向该节点的指针/引用/迭代器无效最后一个节点。
Your assertion is correct for most implementations of std::map.
To my knowledge, there is nothing in the standard preventing a map from using an allocation scheme such as you describe. However, you can get what you describe with a custom allocator — but forcing that scheme on all maps could be wasteful. Because map has no a priori knowledge of how it will be used, certain use patterns could prevent deallocations of mostly-unused blocks. For example, say blocks were allocated for 4 nodes at a time, but a particular map is filled with 40 nodes, then 30 nodes erased, leaving a worst case of one node left per block as map cannot invalidate pointers/references/iterators to that last node.
当您将元素插入映射时，可以保证现有迭代器不会失效。因此，如果您在两个节点 A 和 C 之间插入一个元素“B”，而这两个节点恰好是连续的并且位于同一堆分配区域内，则您无法对它们进行洗牌以腾出空间，并且 B 将不得不放在其他地方。我不认为这有什么特别的问题，除了管理这种复杂性会增加实施的规模。如果删除元素，则迭代器也不会失效，这意味着任何内存分配都必须保留，直到其中的所有节点都被删除为止。您可能需要在每个“膨胀节点”/向量/任何您想要调用的内容中都有一个空闲列表 - 有效地复制至少一些 new/delete 当前为您执行的耗时操作。
When you insert elements into a map, it's guaranteed that existing iterators won't be invalidated. Therefore, if you insert an element "B" between two nodes A and C that happen to be contiguous and inside the same heap allocated area, you can't shuffle them to make space, and B will have to be put elsewhere. I don't see any particular problem with that, except that managing such complexities will swell the implementation. If you erase elements then iterators can't be invalidated either, which implies any memory allocation has to hang around until all the nodes therein are erased. You'd probably need a freelist within each "swollen node"/vector/whatever-you-want-to-call-it - effectively duplicating at least some of the time-consuming operations that new/delete currently do for you.
我非常确定我从未见过尝试将多个节点合并到单个分配块中的
std::map实现。至少我立即想不出它无法工作的原因，但我认为大多数实现者会认为它是不必要的，并将内存分配的优化留给分配器而不是担心它map本身有很多内容。诚然，大多数自定义分配器都是为了更好地处理大量小块的分配而编写的。您可能可以通过编写
map（当然还有set、multiset）来使绝大多数此类优化变得不必要。 > 和multimap），只使用更大的分配。 OTOH，鉴于优化小块分配的分配器很容易/常见/广泛可用，因此可能也没有太多动机以这种方式更改map实现。I'm quite certain I've never seen an implementation of
std::mapthat attempted to coalesce multiple nodes into a single allocation block. At least right offhand I can't think of a reason it couldn't work, but I think most implementors would see it as unnecessary, and leave optimization of memory allocation to the allocator instead of worrying about it much in themapitself.Admittedly, most custom allocators are written to deal better with allocation of a large number of small blocks. You could probably render the vast majority of such optimization unnecessary by writing
map(and, of course,set,multiset, andmultimap) to just use larger allocations instead. OTOH, given that allocators to optimize small block allocations are easily/common/widely available, there's probably not a lot of motivation to change themapimplementation this way either.我认为你唯一不能做的就是使迭代器无效，如果你必须重新分配存储空间，你可能必须这样做。话虽如此，我已经看到使用 std::map 接口中包装的单个排序对象数组的实现。当然，这样做是有一定原因的。
实际上，您可以做的只是使用自定义分配器实例化您的 std::map ，它将以一种特殊的、非浪费的方式为新节点找到内存。
I think the only thing you cannot do is to invalidate iterators, which you might have to do if you have to reallocate your storage. Having said that, I've seen implementations using single sorted array of objects wrapped in the std::map interface. That was done for a certain reason, of course.
Actually, what you can do is just instantiate your std::map with you custom allocator, which will find memory for new nodes in a special, non-wasteful way.
。有趣的是，我以完全不同的方式看待它。我发现它很合适并且不会浪费任何内存。至少在 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，似乎它们的 STL 映射具有相同的方法来为
std::map中的节点分配内存。如果可能的话，首先调整平台上的默认分配器。这里引用 Douglas Lea 很有用，他是 DL-Malloc
或者作为一个更困难的想法，您甚至可以尝试使用 Hoard 分配器测试您的应用程序。我的意思是只测试您的应用程序，看看在性能或碎片方面是否有任何好处。
Interestingly I see it in a completely different way. I find it is appropriate and it doesn't waste any memory. At least with defaul STL allocators on Windows (MS VS 2008), HP-UX (gcc with STLport) and Linux (gcc without STLport). What is important is that these allocators do care about memory fragmentation and it seems they can handle this question pretty well. For example, look for
Low-fragmentation Heapon Windows or SBA (Small block allocator) on HP-UX. I mean that frequently allocating and deallocating memory only for one node at a time doesn't have to result in memory fragmentation. I testedstd::mapmyself in one of my programs and it indeed didn't cause any memory fragmentation with these allocators.I have MS VisualStudio 2008 and its std::map behaves in the same way. On HP-UX I use gcc with and without STLport and it seem that their STL maps have the same approach to allocating memory for nodes in the
std::map.Start with tuning a default allocator on your platform if it is possible. It is useful here to quote the Douglas Lea who is an author of DL-Malloc
Or as a little bit more difficult idea you can even try to test your application with Hoard allocator. I mean just test your application and see if there is any benefit as for performance or fragmentation.