45

例如，我有一个已知 sizeof(A) 和 sizeof(B) 的 std::map，而 map 里面有 N 个条目。你如何估计它的内存使用量？我会说这就像

(sizeof(A) + sizeof(B)) * N * factor

但因素是什么？也许不同的公式？

也许要求上限更容易？

4

7 回答 7

37

估计会更接近

(sizeof(A) + sizeof(B) + ELEMENT_OVERHEAD) * N + CONTAINER_OVERHEAD

您添加的每个元素都有一个开销，并且还有一个固定的开销来维护用于存储映射的数据结构的数据结构。这通常是二叉树，例如红黑树。例如，在 GCC C++ STL 实现ELEMENT_OVERHEAD中将会是sizeof(_Rb_tree_node_base)并且CONTAINER_OVERHEAD将会是sizeof(_Rb_tree). 在上图中，您还应该添加用于存储地图元素的内存管理结构的开销。

通过测量各种大型集合的代码内存消耗可能更容易得出估计值。

于 2009-04-06T07:46:51.130 回答
20

您可以使用Curtis Bartley 的MemTrack。它是一种内存分配器，可以替换默认分配器，并且可以跟踪内存使用情况到分配类型。

输出示例：

-----------------------
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%
于 2009-04-06T09:21:57.173 回答
16

如果您真的想知道运行时内存占用情况，请使用自定义分配器并在创建映射时将其传入。请参阅 Josuttis 的书和他的这一页（对于自定义分配器）。

也许要求上限更容易？

上限将取决于确切的实现（例如使用的平衡树的特定变体）。也许，您可以告诉我们您为什么需要这些信息，以便我们提供更好的帮助？

于 2009-04-06T07:51:42.523 回答
8

我最近需要自己回答这个问题，并简单地使用我在 MSVC 2012 下以 64 位模式编译的 std::map 编写了一个小型基准程序。

一个有 1.5 亿个节点的 map 占用了 ~ 15GB，这意味着 8 byte L、8 byte R、8 byte int key 和 8 byte datum，总共 32 个字节，为内部节点占用了 map 内存的大约 2/3，留下1/3的叶子。

就个人而言，我发现这是非常糟糕的内存效率，但事实就是如此。

希望这可以成为一个方便的经验法则。

PS：std::map 的开销是单个节点大小 AFAICT 的开销。

于 2013-09-03T18:42:17.763 回答
0

公式更像：

(sizeof(A) + sizeof(B) + factor) * N

其中 factor 是每个条目的开销。C++ 映射通常实现为红黑树。这些是二叉树，因此左/右节点至少有两个指针。还会有一些实现的东西——可能是一个父指针和一个“颜色”指示器，所以因素可能是这样的

(sizeof( RBNode *) * 3 + 1) / 2

然而，所有这些都高度依赖于实现——要确定你真的需要检查你自己的库实现的代码。

于 2009-04-06T07:53:43.360 回答
0

我也在寻找一些东西来计算std::map. 我已经尝试了Diomidis Spinellis的答案中解释的内容，并在此处扩展了他的答案，这可能对其他人有所帮助。

我通过添加几行代码来扩展他的答案。

#include <bits/stl_tree.h>
int main(int argc, char *argv[])
{
    std::cout << sizeof(std::_Rb_tree_node_base) << std::endl;
    return 0;
}

输出（在我的 ARM Cortex A-9 iMX6Solo-X 处理器上运行 Linux [4.9.175] 和编译器：）arm-fslc-linux-gnueabi-gcc (GCC) 7.3.0：

16

考虑到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
于 2020-03-31T12:30:48.597 回答
-2

地图的大小实际上取决于地图的实现。您可能在不同的编译器/平台上有不同的大小，具体取决于它们提供的 STL 实现。

为什么需要这个尺寸？

于 2009-04-06T07:44:56.237 回答