Как я могу оценить использование памяти std::map?

Оценка будет ближе к

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

Для каждого добавляемого элемента существуют дополнительные затраты, а также фиксированные затраты на поддержание структуры данных, используемой для структуры данных, хранящей карту. Обычно это бинарное дерево, такое как красно-черное дерево. Например, в реализации GCC C++ STL ELEMENT_OVERHEAD будет sizeof(_Rb_tree_node_base), а CONTAINER_OVERHEAD будет sizeof(_Rb_tree). К приведенному выше рисунку следует также добавить накладные расходы на структуры управления памятью, используемые для хранения элементов карты.

Вероятно, проще получить оценку, измерив потребление памяти вашим кодом для различных больших коллекций.

Вы можете использовать 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%

Если вы действительно хотите узнать объем памяти, занимаемой во время выполнения, используйте собственный распределитель и передайте его при создании карты. См. книгу Джосуттиса и эту страницу (для пользовательского распределителя) .

Может быть, проще попросить верхнюю границу?

Верхняя граница будет зависеть от точной реализации (например, от конкретного используемого варианта сбалансированного дерева). Может быть, вы можете сказать нам, почему вам нужна эта информация, чтобы мы могли помочь лучше?

Недавно мне нужно было ответить на этот вопрос для себя, и я просто написал небольшую тестовую программу, используя std::map, которую я скомпилировал под MSVC 2012 в 64-битном режиме.

Карта со 150 миллионами узлов поглощает ~ 15 ГБ, что подразумевает 8 байтов L, 8 байтов R, 8 байтов ключа int и 8 байт данных, всего 32 байта, поглощая около 2/3 памяти карты для внутренние узлы, оставляя 1/3 для листьев.

Лично я обнаружил, что это удивительно низкая эффективность памяти, но это то, что есть.

Надеюсь, это станет удобным эмпирическим правилом.

PS: Накладные расходы std::map - это размер одного узла AFAICT.

Формула больше похожа на:

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

где factor — накладные расходы на запись. Карты C++ обычно реализуются как красно-черные деревья. Это бинарные деревья, поэтому будет как минимум два указателя на левый/правый узлы. Также будут некоторые вещи для реализации - возможно, родительский указатель и "цветовой" индикатор, поэтому фактор может быть чем-то вроде

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

Однако все это сильно зависит от реализации — чтобы убедиться в этом, вам действительно нужно изучить код реализации вашей собственной библиотеки.

Я также искал что-то, чтобы рассчитать размер 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;
}

Выходные данные (на моем процессоре ARM Cortex A-9 iMX6Solo-X под управлением Linux [4.9.175] и компилятора: arm-fslc-linux-gnueabi-gcc (GCC) 7.3.0):

16

Учитывая std::map<A, B>, меня интересует размер ELEMENT_OVERHEAD, так как он линейно растет с количеством элементов, присутствующих на карте. Было обнаружено, что ELEMENT_OVERHEAD эквивалентен sizeof(std::_Rb_tree_node_base), поэтому для моей системы имеет значение 16.

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

Размер карты действительно зависит от реализации карты. У вас могут быть разные размеры на разных компиляторах/платформах, в зависимости от того, какую реализацию STL они предоставляют.

Зачем вам этот размер?