Рассчитать использование памяти древовидной структуры в C ++

Question

У меня есть древовидная структура

struct TrieNode {
    std::unordered_map<std::string, TrieNode> children;
    std::vector<std::string> terminals;
};

Некоторые сведения о его использовании:

• Дерево не изменяется после его заполнения.
• Ключи на неупорядоченной карте - короткие строки (не превышающие 5 символов).

Эта структура может стать очень большой. И мне нужно рассчитать его размер в памяти. Этот размер не должен быть очень точным. Существуют ли какие-либо подходы для этого?

Если нет, я думал об этих вариантах:

1. Я могу отслеживать изменения этой структуры отдельно.
2. Используйте специальный распределитель для контейнеров, который отслеживает пространство (есть ли общая реализация для этого?). Оператор
3. Overload new для моей структуры, чтобы отслеживать память (не уверен, как отслеживать вставки в vector после этого).
4. Рассчитать размер после заполнения дерева путем обхода всего дерева (в крайнем случае, для большого дерева это займет очень много времени, но результат будет более точным).

Какой подход лучше?

Answer 1

Последний. У меня есть следующие причины:

1. Это самый простой из четырех подходов.
2. , поскольку дерево фиксируется после заполнения, ленивая оценка размера имеет больше смысла, потому что:
   • когда размер не используется, мы можем сэкономить время, затрачиваемое на вычисление размера.
   • Это не займет дополнительного времени, поскольку сложность времени также равна O(n), единственное дополнительное время затрачивается на вызывать рекурсивные функции.
3. избегает присутствия глобальной переменной