How can i estimate memory usage of std::map?

Question

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)) * N * factor 

But what is the factor? Different formula maybe?

Maybe it's easier to ask for upper bound?

Answer 1

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_OVERHEAD would be sizeof(_Rb_tree_node_base) and CONTAINER_OVERHEAD would 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.

It's probably easier to arrive at an estimate by measuring your code's memory consumption for various large collections.

Answer 2

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.

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%