如何在 C++ 中近似 std::unordered_map 的大小

Question

据说 anunordered_map<int,int>比 a 占用更多的空间vector<int>。虽然我完全意识到这一点，但我想知道如何在C++ 中获得 an 的单个实例的大致大小。现在，假设我向其中插入了元素。我认为占用的内存乘以某种常数，但是，我无法在 Internet 上的任何地方找到准确的答案。 这就是我正在做的事情。我想计算使用了多少内存，而无需编写任何代码。有没有办法做到这一点？unordered_mapn = 1000000n
u_m

#include<bits/stdc++.h>
using namespace std;

const int N = 1000000;
unordered_map<int,int> u_m ;

int main(){
     for(int i = 0;i<N;i++){
         u_m[i] = 123+i;
     }
     return 0;
}

如果有差别，我故意把u_m外面的main

Answer 1

对此没有通用的答案。使用的内存可能因实现而异。需要明确的unordered_map是，不是基于树的；它通常被实现为一个桶数组。

但是，虽然规范允许您知道当前有多少个存储桶（通过bucket_count）并且您可以询问每个存储桶中的项目数（使用bucket_size），但无法询问存储桶是如何实现的。根据bucket_size和extract/等方法的各种要求merge，它很可能是一个简单的链表（bucket_size允许O(n)在桶的大小中，所以它不需要直接知道自己的大小；extract需要能够返回一个句柄可以在unordered_maps之间转移，并且merge保证在将元素从一个移动unordered_map到另一个时不会复制或移动），但实现的细节在很大程度上是隐藏的。

也无法保证首先存储的内容。它可能只是键和值，或键、值和散列，或其他东西。

因此，虽然您可以从各种.bucket*API 中获取基本信息，但由于“存储桶”的内容和实现本身本质上是未指定的，因此您永远无法unordered_map从任何 C++ 标准 API 中得到“桶有多大”的答案；您需要了解实现细节并将它们与.bucket*API一起使用，以进行估算。