在C++中计算树结构的内存使用量。

Question

我有一个树形结构

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

关于它的一些使用细节。

• 树在被填充后不会被修改。
• 无序地图中的键是短字符串（不超过5个字符）。

这个结构可以长得非常大。而我需要计算它在内存中的大小。这个大小不需要很精确.有什么现有的方法可以做到这一点吗？

如果没有，我在想这些方案。

1. 我可以单独跟踪这个结构的修改。
2. 为容器使用一个自定义的分配器，以保持对空间的跟踪（是否有一个通用的实现？
3. 超载 new 运算符来跟踪我的结构的内存（不知道如何跟踪插入到 vector 后）。)
4. 通过遍历整棵树来计算树被填充后的大小（最后的手段，因为对于大树来说，它将花费非常长的时间，但结果更精确）。

最好的方法是什么？

Answer 1

最后一个。我有以下理由。

1. 它是四种方法中最简单的一种。
2. 因为树在填充后是固定的，所以懒惰地评估大小比较合理，因为。
   • 因为当不使用大小时，我们可以节省计算大小的时间。
   • 它不会花费额外的时间，因为时间复杂度也是 O(n)，唯一额外的时间是调用递归函数。
3. 它避免了全局变量的存在