¿Cómo puedo estimar el uso de memoria de std :: map?

Por ejemplo, tengo un std :: map con tamaño conocido (A) y tamaño de (B), mientras que el mapa tiene N entradas dentro. ¿Cómo estimaría su uso de memoria? Yo diría que es algo como

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

Pero, ¿cuál es el factor? ¿Diferente fórmula tal vez?

¿Tal vez es más fácil pedir un límite superior?

La estimación estaría más cerca de

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

Hay una sobrecarga para cada elemento que agrega, y también hay una sobrecarga fija para mantener la estructura de datos utilizada para la estructura de datos que almacena el mapa. Esto es típicamente un árbol binario, como un árbol rojo-negro . Por ejemplo, en la implementación GCC C ++ STL ELEMENT_OVERHEAD sería sizeof(_Rb_tree_node_base) y CONTAINER_OVERHEAD sería sizeof(_Rb_tree) . A la figura anterior también debe agregar la sobrecarga de las estructuras de administración de memoria utilizadas para almacenar los elementos del mapa.

Probablemente sea más fácil obtener una estimación midiendo el consumo de memoria de su código para varias colecciones grandes.

Podrías usar MemTrack , de Curtis Bartley. Es un asignador de memoria que reemplaza el predeterminado y puede rastrear el uso de la memoria hasta el tipo de asignación.

Un ejemplo de salida:

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

Si realmente desea conocer la huella de memoria de tiempo de ejecución, use un asignador personalizado y páselo al crear el mapa. Vea el libro de Josuttis y esta página suya (para un asignador personalizado).

¿Tal vez es más fácil pedir un límite superior?

El límite superior dependerá de la implementación exacta (por ejemplo, la variante particular del árbol equilibrado utilizado). Tal vez, ¿puede decirnos por qué necesita esta información para que podamos ayudarlo mejor?

Hace poco necesitaba responder a esta pregunta y simplemente escribí un pequeño progtwig de referencia usando std :: map que compilé en MSVC 2012 en modo de 64 bits.

Un mapa con 150 millones de nodos absorbidos ~ 15GB, lo que implica 8 bytes de 8 bytes, 8 bytes R, 8 bytes de clave int y 8 bytes de datos, totalizando 32 bytes, absorbidos aproximadamente 2 / 3rds de la memoria del mapa para nodos internos, dejando 1 / 3rd para las hojas.

Personalmente, me pareció sorprendentemente pobre en la eficiencia de la memoria, pero es lo que es.

Espero que esto sea una práctica regla de oro.

PD: La sobrecarga de un std :: map es la del tamaño de un solo nodo AFAICT.

La fórmula es más como:

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

donde factor es la sobrecarga de entrada. Los mapas C ++ se implementan típicamente como árboles rojo-negros. Estos son árboles binarios, por lo que habrá al menos dos punteros para los nodos izquierdo / derecho. También habrá algunas cosas de implementación, probablemente un puntero principal y un indicador de “color”, por lo que el factor puede ser algo así como

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

Sin embargo, todo esto depende en gran medida de la implementación: para estar seguro de que realmente necesita examinar el código para la implementación de su propia biblioteca.

El tamaño del mapa realmente depende de la implementación del mapa. Es posible que tenga diferentes tamaños en diferentes comstackdores / plataformas, según la implementación de STL que proporcionen.

¿Por qué necesitas este tamaño?