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

我有一个树形结构

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

关于它的一些使用细节。

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

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

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

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

最好的方法是什么?

解决方案:

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

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

给TA打赏
共{{data.count}}人
人已打赏
未分类

SQL。根据主键查询完整的层次结构。

2022-9-8 3:18:36

未分类

在HTMLCSSJavaScript幻灯片中设置超时

2022-9-8 3:18:38

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索