C++ – How to i estimate memory usage of std::map


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?

Best Solution

The estimate would be closer to


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.