How to Estimate Memory Usage of Std::Map

How can i estimate memory usage of std::map?

The estimate would be closer to

(sizeof(A) + sizeof(B) + ELEMENT_OVERHEAD) * N + CONTAINER_OVERHEAD

There is an overhead for each element you add, and there is also a fixed overhead for maintaining the data structure used for the data structure storing the map. This is typically a binary tree, such as a Red-Black Tree. For instance, in the GCC C++ STL implementation ELEMENT_OVERHEAD would be sizeof(_Rb_tree_node_base) and CONTAINER_OVERHEAD would be sizeof(_Rb_tree). To the above figure you should also add the overhead of memory management structures used for storing the map's elements.

It's probably easier to arrive at an estimate by measuring your code's memory consumption for various large collections.

How to measure the memory usage of std::unordered_map

If you want to get a rough size, I think bucket_count() and max_load_factor() is enough, which gives the current count of buckets and the load factor.

Rational:

If load_factor <= 1, it indicates that bucket_count() >= the items in the map, then bucket_count() is the size of memory usage.
If load_factor > 1, then bucket_count() * load_factor indicates the max item in the map. Note this is the max size, not the real size.

So for a rough memory usage could look like this:

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

If you want to get the accurate memory usage, you may need to count all the buckets to see how many elements in it:

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

Any way to find size of memory allocated to map?

No, there is not. However you can achieve something similar for classes that support a .size method such as strings or standard container:

template <class Key, class Value>
unsigned long mapSize(const std::map<Key,Value> &map){
    unsigned long size = sizeof(map);
    for(typename std::map<Key,Value>::const_iterator it = map.begin(); it != map.end(); ++it){
        size += it->first.size();
        size += it->second.size();
    }
    return size;
}

If you want to know the allocated memory you could use .capacity:

template <class Key, class Value>
unsigned long mapCapacity(const std::map<Key,Value> &map){
    unsigned long cap = sizeof(map);
    for(typename std::map<Key,Value>::const_iterator it = map.begin(); it != map.end(); ++it){
        cap += it->first.capacity();
        cap += it->second.capacity();
    }
    return cap;
}

std::map vs unordered_map memory footprint for small N

For small N, a sorted vector is often the fastest container, and has minimal memory footprint. boost::flat_map is an implementation, others call it AssociativeVector. You can use std::lower_bound to implement it easily. Since the data has to be sorted, insert and delete operations are O(n) since the data has to be shifted in the vector.

With a sorted vector, you can do a binary search which is O(log N) for retrieval. The complexity of std::lower_bound is:

The number of comparisons performed is logarithmic in the distance between first and last (At most log2(last - first) + O(1) comparisons)

Determine memory usage of an std::map/std::set at runtime

Implement a custom allocator which will count the memory used, and provide that to the constructor of your map/set.

Memory consumption by STL containers

For std::vector and std::string, capacity, rather than size, would
be a better approximation. For node based containers (std::set,
etc.), you'd want multiply the number of nodes (roughly the number of
elements) times the size of each node. This only accurate, however, if
the allocator doesn't use an optimized pool allocator for the nodes.

If you really want to know how much memory is being used, however, a
better strategy would be to replace the global operator new and
operator delete, and keep track of the actual allocations. Even more
accurate would be to replace malloc and free. Formally, this is not
allowed, but in practice, I've never encountered an implementation where
it doesn't work. On the other hand, if you replace malloc and free,
you have to implement the actual memory management yourself. If you
replace operator new and operator delete, you can use malloc and
free, which makes it fairly trivial.

Note too that each allocation has some fixed overhead. A 100000
allocations of 10 bytes each will consume significantly more memory than
10 allocations of 100000 bytes each.

std::map in class : trade off between execution speed and memory usage

I don't think this is your best option, for 25 elements, you will not benefit that much from using a map in terms of lookup performance. Also, it depends on what kinds of properties are you going to have, if it is a fixed set of properties as in your example, then string lookup would be a waste of memory and CPU cycles, you could go for an enum of all properties or just an integer and use a sequential container for the properties each element has. For such a small number of possible properties, lookup time will be lower than a map because of cache friendliness and integer comparisons, and memory usage will be lower too. For such a small set of properties this solution is marginally better.

Then there is the problem that an int is usually twice as small as a double. And they are different types. So it is not directly possible to store both in a single container, but you could have enough space for a double in each element, and either use a union or just read/write an int from/to the address of the double if the property "index" is larger than 14.

So you can have something as simple as:

struct Property {
   int type;
   union {
       int d_int;
       double d_double;
   };
};

class MyObject {
    std::vector<Property> properties;
};

And for type 1 - 14 you read the d_double field, for type 15 - 25 the d_int field.

BENCHMARKS!!!

Out of curiosity I did some testing, creating 250k objects, each with 5 int and 5 double properties, using a vector, a map and a hash for the properties, and measured memory usage and time taken to set and get the properties, ran each test 3 times in a row to see impact on caching, calculate checksum for getters to verify consistency, and here are the results:

vector | iteration | memory usage MB | time msec | checksum 
setting 0 32 54
setting 1 32 13
setting 2 32 13
getting 0 32 77 3750000
getting 1 32 77 3750000
getting 2 32 77 3750000

map | iteration | memory usage MB | time msec | checksum 
setting 0 132 872
setting 1 132 800
setting 2 132 800
getting 0 132 800 3750000
getting 1 132 799 3750000
getting 2 132 799 3750000

hash | iteration | memory usage MB | time msec | checksum 
setting 0 155 797
setting 1 155 702
setting 2 155 702
getting 0 155 705 3750000
getting 1 155 705 3750000
getting 2 155 706 3750000

As expected, the vector solution is by far the fastest and most efficient, although it is most influenced by cold cache, even running cold it is way faster than a map or hash implementation.

On a cold run, the vector implementation is 16.15 times faster than map and 14.75 times faster than hash. On a warm run it is even faster - 61 times faster and 54 times faster respectively.

As for memory usage, the vector solution is far more efficient as well, using over 4 times less memory than the map solution and almost 5 times less than the hash solution.

As I said, it is marginally better.

To clarify, the "cold run" is not only the first run but also the one inserting the actual values in the properties, so it is fairly illustrative of the insert operations overhead. None of the containers used preallocation so they used their default policies of expanding. As for the memory usage, it is possible it doesn't accurately reflect actual memory usage 100% accurately, since I use the entire working set for the executable, and there is usually some preallocation taking place on OS level as well, it will most likely be more conservative as the working set increases. Last but not least, the map and hash solutions are implemented using a string lookup as the OP originally intended, which is why they are so inefficient. Using integers as keys in the map and hash produces far more competitive results:

vector | iteration | memory usage MB | time msec | checksum 
setting 0 32 55
setting 1 32 13
setting 2 32 13
getting 0 32 77 3750000
getting 1 32 77 3750000
getting 2 32 77 3750000

map | iteration | memory usage MB | time msec | checksum 
setting 0 47 95
setting 1 47 11
setting 2 47 11
getting 0 47 12 3750000
getting 1 47 12 3750000
getting 2 47 12 3750000

hash | iteration | memory usage MB | time msec | checksum 
setting 0 68 98
setting 1 68 19
setting 2 68 19
getting 0 68 21 3750000
getting 1 68 21 3750000
getting 2 68 21 3750000

Memory usage is much lower for hash and map, while still higher than vector, but in terms of performance the tables are turned, while the vector solution sill wins at inserts, at reading and writing the map solution takes the trophy. So there's the trade-off.

As for how much memory is saved compared to having all the properties as object members, by just a rough calculation, it would take about 80 MB of RAM to have 250k such objects in a sequential container. So you save like 50 MB for the vector solution and almost nothing for the hash solution. And it goes without saying - direct member access would be much faster.

Calculating memory space occupied by unordered maps

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.

std::unordered_map very high memory usage

The unordered_map structure is designed to hold large numbers of objects in a way that makes adds, deletes, lookups, and orderless traverses efficient. It's not meant to be memory-efficient for small data structures. To avoid the penalties associated with resizing, it allocates many hash chain heads when it's first created.