如何测量std :: unordered_map的内存使用情况

Question

我们知道基于哈希表的容器实现就像std::unordered_map使用了很多内存但我不知道多少是多少？

除了空间复杂性表示法,并且不考虑容器元素是否是指向更大对象的指针:

有没有办法弄清楚这样的容器在运行时使用了多少字节？

有没有办法在运行时告诉任何容器使用多少内存？

Answer 1

没有可移植的方法来判断正在使用多少字节.你能找到的是:

• size() 表示已将多少数据元素插入容器中
• bucket_count() 表示底层哈希表有多少个桶,每个桶都可以预期将链接列表托管到相关元素

现在:

• 实际用于元素存储的字节数将是 m.size() * sizeof(M::value_type)

• 用于散列表桶的字节取决于内部列表的存储方式 - std::unordered_map::bucket_size具有恒定的复杂性,因此我们可以合理地猜测size()每个桶都有一个和头指针,所以这m.bucket_count() * (sizeof(size_t) + sizeof(void*))是一个合理的猜测,尽管它可能只是存在由于受限制而且每桶没有存储,因此不断摊销的复杂性(我更喜欢自己这样实现)load_factor()size

• 如果每个插入的元素都是列表的一部分,它们将需要一个next指针,所以我们可以添加另一个m.size() * sizeof(void*)

• 每个内存分配可以四舍五入到便于内存分配库管理的大小 - 例如,下一个2的幂,接近100%最坏情况下的低效率和50%的平均值,所以让我们添加50%,仅用于列表节点作为桶可能是两个给定size_t的指针和一个指针:50%*size() * (sizeof(void*) + sizeof((M::value_type))

• 特别是在调试模式下,可能存在任何数量的特定于实现的内务处理和错误检测数据

您可以通过创建许多大型表并查看topProcess Manager 如何报告不同的内存使用情况来进一步探索此问题.

Answer 2

如果你想得到一个粗略的尺寸,我认为bucket_count()并且max_load_factor()足够了,它给出了当前的桶数和负载系数.

合理的:

• 如果load_factor<= 1,则表示bucket_count()> =地图中的项目,则bucket_count()是内存使用量的大小.

• 如果load_factor> 1,则bucket_count()*load_factor表示地图中的最大项目.请注意,这是最大尺寸,而不是实际尺寸.

因此粗略的内存使用情况可能如下所示:

  unsigned n = mymap.bucket_count();
  float m = mymap.max_load_factor();
  if (m > 1.0) {
    return n * m;
  }
  else {
    return n;
  }

如果您想获得准确的内存使用量,您可能需要计算所有桶以查看其中有多少元素:

  size_t count = 0;
  for (unsigned i = 0; i < mymap.bucket_count(); ++i) {
    size_t bucket_size = mymap.bucket_size(i);
    if (bucket_size == 0) {
      count++;
    }
    else {
      count += bucket_size;
    }
  }