How to approximate the size of an std::unordered_map in C++

Question

It is said that an unordered_map<int,int> takes up much more space than a vector<int>. While I am completely aware of that, I would like to know how to get the approximate size of a single instance of an unordered_map in C++. For now, let's say that I inserted n = 1000000 elements into it. I presume that the memory taken up is n multiplied by some kind of constant, I am, however, unable to find an accurate answer anywhere on the Internet.
Here is what I'm doing. I'd like to calculate how much memory u_m uses, without writing any code. Is there a way to do that?

#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;
}

If that makes a difference, I intentionally put u_m outside of main

[Why should I not `#include `?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) [Why is `using namespace std;` considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) — Evg, Dec 08 '20 at 20:14
You cannot calculate such things from first principles because the definition of C++ doesn't contain enough first principles. You can experiment with a specific implementation instead. Use a custom allocator that keeps track of allocated memory. Or you can study the code of a specific implementation and map out its memory allocation strategy, but that's way more difficult. — n. m. could be an AI, Dec 08 '20 at 20:18

ShadowRanger · Answer 1 · 2020-12-08T20:26:00.067

There is no general purpose answer to this. The memory used can vary wildly based on the implementation. To be clear, unordered_map is not tree-based; it's typically implemented as an array of buckets.

But while the spec allows you to know how many buckets are currently in play (via bucket_count) and you can ask for the number of items in each bucket (with bucket_size), there is no way to ask how a bucket is implemented. Based on the various requirements of methods like bucket_size and extract/merge, it's likely a bare bones linked list (bucket_size is allowed to be O(n) in the size of the bucket, so it needn't know its own size directly; extract needs to be able to return a handle that can be transferred between unordered_maps, and merge is guaranteed not to copy or move when moving elements from one unordered_map to another), but the details of implementation are largely hidden.

There's also no guarantee on what is stored in the first place. It could be just key and value, or key, value and hash, or something else.

So while you can get basic info from the various .bucket* APIs, since the contents and implementation of a "bucket" is itself essentially unspecified, you'll never get an answer to "how big is an unordered_map" from any C++ standard APIs; you'd need to know the implementation details and use them alongside the .bucket* APIs, to get an estimate.

score 4 · Answer 2 · answered Dec 08 '20 at 20:18

An unordered_map is not a tree, it is a hash table. It size is dependent on several things, both on amount you've inserted, but also on things like calling reserve to pre-allocate memory. The specific settings of initial allcoation size and load factors are implementation dependent, so any guess you make will probably differ between compilers, and the order of operations that result in when and by how much the hash table resizes will differ too.

How to approximate the size of an std::unordered_map in C++

2 Answers2