如何估计 std::map 的内存使用情况？

Question

例如，我有一个已知 sizeof(A) 和 sizeof(B) 的 std::map，而 map 内部有 N 个条目。 您如何估计其内存使用情况？ 我想说的是，

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

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

也许要求上限更容易？

Answer 1

估计会更接近。

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

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

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

Answer 2

您可以使用 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%

Answer 3

如果您确实想了解运行时内存占用量，请使用自定义分配器并在创建映射时将其传入。 请参阅 Josuttis 的书和他的此页面（有关自定义分配器） 。

也许要求上限更容易？

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

Answer 4

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

具有 1.5 亿个节点的地图占用约 15GB，这意味着 8 字节 L、8 字节 R、8 字节 int key 和 8 字节数据，总共 32 字节，占用了地图内存的大约 2/3内部节点，留下 1/3 给叶子。

就我个人而言，我发现这内存效率出奇的差，但事实就是如此。

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

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

Answer 5

该公式更像是：

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

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

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

但是，所有这些都高度依赖于实现 - 为了确定你确实需要检查你自己的库的代码执行。

Answer 6

我也在寻找一些东西来计算 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;
}

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

16

考虑 std::map，我对 ELEMENT_OVERHEAD 的大小感兴趣，因为它随着地图中存在的元素数量线性增长。 发现 ELEMENT_OVERHEAD 相当于 sizeof(std::_Rb_tree_node_base)，因此对于我的系统来说其值为 16。

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

Answer 7

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

为什么需要这个尺寸？