C++ 我如何估计 std::map 的内存使用情况？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/720507/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How can i estimate memory usage of std::map?
提问by Drakosha
For example, I have a std::map with known sizeof(A) and sizeof(B), while map has N entries inside. How would you estimate its memory usage? I'd say it's something like
例如，我有一个已知 sizeof(A) 和 sizeof(B) 的 std::map，而 map 里面有 N 个条目。你如何估计它的内存使用情况？我会说这就像
(sizeof(A) + sizeof(B)) * N * factor
But what is the factor? Different formula maybe?
但因素是什么？也许不同的公式？
Maybe it's easier to ask for upper bound?
也许要求上限更容易？
采纳答案by Diomidis Spinellis
The estimate would be closer to
估计会更接近
(sizeof(A) + sizeof(B) + ELEMENT_OVERHEAD) * N + CONTAINER_OVERHEAD
There is an overhead for each element you add, and there is also a fixed overhead for maintaining the data structure used for the data structure storing the map. This is typically a binary tree, such as a Red-Black Tree. For instance, in the GCC C++ STL implementation ELEMENT_OVERHEADwould be sizeof(_Rb_tree_node_base)and CONTAINER_OVERHEADwould be sizeof(_Rb_tree). To the above figure you should also add the overhead of memory management structures used for storing the map's elements.
您添加的每个元素都有开销，并且还有用于维护用于存储映射的数据结构的数据结构的固定开销。这通常是一个二叉树，例如红黑树。例如，在 GCC C++ STL 实现ELEMENT_OVERHEAD中sizeof(_Rb_tree_node_base)，CONTAINER_OVERHEAD将会是sizeof(_Rb_tree). 对于上图，您还应该添加用于存储地图元素的内存管理结构的开销。
It's probably easier to arrive at an estimate by measuring your code's memory consumption for various large collections.
通过测量各种大型集合的代码内存消耗，可能更容易得出估计值。
回答by Xavier Nodet
You could use MemTrack, by Curtis Bartley. It's a memory allocator that replaces the default one and can track memory usage down to the type of allocation.
您可以使用Curtis Bartley 的MemTrack。它是一种内存分配器，它取代了默认分配器，可以跟踪内存使用情况直至分配类型。
An example of output:
输出示例：
-----------------------
Memory Usage Statistics
-----------------------
allocated type blocks bytes
-------------- ------ -----
struct FHRDocPath::IndexedRec 11031 13.7% 2756600 45.8%
class FHRDocPath 10734 13.3% 772848 12.8%
class FHRDocElemPropLst 13132 16.3% 420224 7.0%
struct FHRDocVDict::IndexedRec 3595 4.5% 370336 6.2%
struct FHRDocMDict::IndexedRec 13368 16.6% 208200 3.5%
class FHRDocObject * 36 0.0% 172836 2.9%
struct FHRDocData::IndexedRec 890 1.1% 159880 2.7%
struct FHRDocLineTable::IndexedRec 408 0.5% 152824 2.5%
struct FHRDocMList::IndexedRec 2656 3.3% 119168 2.0%
class FHRDocMList 1964 2.4% 62848 1.0%
class FHRDocVMpObj 2096 2.6% 58688 1.0%
class FHRDocProcessColor 1259 1.6% 50360 0.8%
struct FHRDocTextBlok::IndexedRec 680 0.8% 48756 0.8%
class FHRDocUString 1800 2.2% 43200 0.7%
class FHRDocGroup 684 0.8% 41040 0.7%
class FHRDocObject * (__cdecl*)(void) 36 0.0% 39928 0.7%
class FHRDocXform 516 0.6% 35088 0.6%
class FHRDocTextColumn 403 0.5% 33852 0.6%
class FHRDocTString 407 0.5% 29304 0.5%
struct FHRDocUString::IndexedRec 1800 2.2% 27904 0.5%
回答by dirkgently
If you really want to know the runtime memory footprint, use a custom allocator and pass it in when creating the map. See Josuttis' book and thispage of his (for a custom allocator).
如果您真的想知道运行时内存占用，请使用自定义分配器并在创建映射时将其传入。请参阅 Josuttis 的书和他的这一页（用于自定义分配器）。
Maybe it's easier to ask for upper bound?
也许要求上限更容易？
The upper bound will depend on the exact implementation (e.g. the particular variant of balanced tree used). Maybe, you can tell us why you need this information so we can help better?
上限将取决于确切的实现（例如所使用的平衡树的特定变体）。也许，您可以告诉我们您为什么需要这些信息，以便我们更好地提供帮助？
回答by user2548100
I recently needed to answer this question for myself, and simply wrote a small benchmark program using std::map I compiled under MSVC 2012 in 64-bit mode.
我最近需要自己回答这个问题，简单地使用我在 MSVC 2012 下以 64 位模式编译的 std::map 编写了一个小型基准程序。
A map with 150 million nodes soaked up ~ 15GB, which implies the 8 byte L, 8 byte R, 8 byte int key, and 8 byte datum, totaling 32 bytes, soaked up about 2/3rds of the map's memory for internal nodes, leaving 1/3rd for leaves.
一个有 1.5 亿个节点的映射占用了大约 15GB，这意味着 8 字节 L、8 字节 R、8 字节 int 密钥和 8 字节数据，总共 32 字节，为内部节点吸收了大约 2/3 的映射内存，留下1/3的叶子。
Personally, I found this to be surprisingly poor memory efficiency, but it is what it is.
就个人而言，我发现这是令人惊讶的低内存效率，但事实就是如此。
Hope this makes for a handy rule-of-thumb.
希望这是一个方便的经验法则。
PS: The overhead of a std::map is that of a single node's size AFAICT.
PS： std::map 的开销是单个节点的大小 AFAICT 的开销。
回答by abhiarora
I was also looking for something to calculate the size of the std::map. I have tried what was explained in Diomidis Spinellis's answer and expanded his answer over here which could be helpful to others.
我也在寻找一些东西来计算std::map. 我已经尝试了Diomidis Spinellis的回答中解释的内容，并将他的回答扩展到这里，这可能对其他人有所帮助。
I am expanding on his answer by adding few lines of code.
我通过添加几行代码来扩展他的答案。
#include <bits/stl_tree.h>
int main(int argc, char *argv[])
{
std::cout << sizeof(std::_Rb_tree_node_base) << std::endl;
return 0;
}
Outputs (On my ARM Cortex A-9 iMX6Solo-X processor running Linux [4.9.175] and compiler: arm-fslc-linux-gnueabi-gcc (GCC) 7.3.0):
输出（在我的 ARM Cortex A-9 iMX6Solo-X 处理器上运行 Linux [4.9.175] 和编译器：）arm-fslc-linux-gnueabi-gcc (GCC) 7.3.0：
16
Considering std::map<A, B>, I am interested in size of ELEMENT_OVERHEADas it grows linearly with the number of elements present in the map. ELEMENT_OVERHEAD was found to be equivalent of sizeof(std::_Rb_tree_node_base)as hence has a value of 16 for my system.
考虑到std::map<A, B>，我对 的大小感兴趣，ELEMENT_OVERHEAD因为它随着地图中存在的元素数量线性增长。ELEMENT_OVERHEAD 被发现等价于sizeof(std::_Rb_tree_node_base)as 因此我的系统的值为 16。
(sizeof(A) + sizeof(B) + ELEMENT_OVERHEAD) * N + CONTAINER_OVERHEAD
回答by abhiarora
The formula is more like:
公式更像是：
(sizeof(A) + sizeof(B) + factor) * N
where factor is the per entry overhead. C++ maps are typically implemented as red-black trees. These are binary trees, so there will be at least two pointers for the left/right nodes. There will also be some implementation stuff - probably a parent pointer and a "colour" indicator, so factor may be something like
其中 factor 是每个条目的开销。C++ 映射通常实现为红黑树。这些是二叉树，因此至少有两个指向左/右节点的指针。还会有一些实现的东西——可能是一个父指针和一个“颜色”指示器，所以因子可能是这样的
(sizeof( RBNode *) * 3 + 1) / 2
However, all this is highly implementation dependent - to find out for sure you really need to examine the code for your own library implementation.
然而，所有这些都高度依赖于实现——为了确定你真的需要检查你自己的库实现的代码。
回答by C?t?lin Piti?
The size of the map really depends on the implementation of the map. You might have different sizes on different compilers/platforms, depending on which STL implementation they are providing.
地图的大小实际上取决于地图的实现。您在不同的编译器/平台上可能有不同的大小，具体取决于它们提供的 STL 实现。
Why do you need this size?
为什么需要这个尺寸？
