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

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

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

但是,这个因素是什么? 不同的公式可能?

也许要求上限更容易?

估计会更接近

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

每个添加的元素都有一个额外的开销,并且在维护用于存储映射的数据结构的数据结构方面也有固定的开销。 这通常是一个二叉树,如红黑树 。 例如,在GCC C ++ STL实现中, ELEMENT_OVERHEADsizeof(_Rb_tree_node_base)CONTAINER_OVERHEADsizeof(_Rb_tree) 。 对于上图,还应该添加用于存储映射元素的内存pipe理结构的开销。

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

您可以使用Curtis Bartley的MemTrack 。 这是一个内存分配器,取代了默认的内存分配器,可以跟踪内存使用情况,直到分配的types。

输出示例:

 ----------------------- 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% 

如果您确实想知道运行时内存占用情况,请在创build映射时使用自定义分配器并将其传入。 见Josuttis的书和他的这个页面(用于定制分配器)。

也许要求上限更容易?

上限取决于确切的实现(例如,所使用的平衡树的特定变体)。 也许,你可以告诉我们为什么你需要这个信息,所以我们可以帮助更好?

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

一个拥有1.5亿个节点的地图浸入了〜15GB,这意味着8字节的L,8字节的R,8字节的int键和8字节的数据,总共32字节, 为内部节点浸泡了大约2/3的地图内存,留下1/3的叶子。

就个人而言,我发现这是令人惊讶的记忆效率差,但它是什么。

希望这是一个方便的经验法则。

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

公式更像是:

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

其中因素是每项入口的开销。 C ++地图通常以红黑树的forms实现。 这些是二叉树,所以左/右节点至less有两个指针。 也会有一些实现的东西 – 可能是一个父指针和一个“颜色”指标,所以因素可能是类似的

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

然而,所有这些都是高度依赖于实现的 – 要确定您确实需要检查自己的库实现的代码。

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

你为什么需要这个尺寸?