I don't think it's possible to answer your question precisely without looking at the precise unordered_map
implementation your STL uses.
However, based on the unordered_map
interface, you could make decent educated guesses:
An unordered_map
needs to store:
one
bucket
container (probably a vector-like structure)max_bucket_count
buckets (probably singly-linked-list-like structures)one complete entry for each item (not only the value, but also the key, to handle key hash collisions)
After a quick look at the Libc++ implementation, you also need space to store:
The hashing function object
The equality test function object
The allocator function object
With this in mind, my guesstimate would be something like:
typedef unordered_map<K, V, ...> tMyMap;
size_t getMemoryUsage(const tMyMap& map) {
auto entrySize = sizeof(K) + sizeof(V) + sizeof(void*);
auto bucketSize = sizeof(void*);
auto adminSize = 3 * sizeof(void*) + sizeof(size_t);
auto totalSize = adminSize + map.size() * entrySize + map.max_bucket_count() * bucketSize();
return totalSize;
}
This would only work for the first of your cases, since in the second cases, each entry can have a completely different memory usage based on how big each vector is. For the second case, you would therefore have to add something like this:
size_t getMemoryUsage(const tMyMap& map) {
auto entrySize = sizeof(K) + sizeof(V) + sizeof(void*);
auto bucketSize = sizeof(void*);
auto adminSize = 3 * sizeof(void*) + sizeof(size_t);
auto totalSize = adminSize + map.size() * entrySize + map.max_bucket_count() * bucketSize();
auto contentSize = 0;
for (const auto& kv : map) {
// since accept is a vector<char>,
// it uses capacity() bytes of additional memory
contentSize += kv.second.accept.capacity();
}
totalSize += contentSize;
return totalSize;
}
However, considering real-world allocation logic, the memory your map actually uses may differ a lot from this due to e.g. external fragmentation. If you want to be 100% sure how much memory an unordered_map uses, you need to also take allocator behavior into account.