Std :: map for small rare collections

Question

Given the MyData structure from which there are many instances (I would say several million), for each instance I need to save an element that can contain values ​​up to 8 keys. The key will always be int ranged 0-7 , and the values ​​will always be the three-dimensional point of the floats (let's call it Point3 ).

At maximum, it will contain:

 Key | Value ------------- 0 | [x,y,z] 1 | [x,y,z] 2 | [x,y,z] 3 | [x,y,z] 4 | [x,y,z] 5 | [x,y,z] 6 | [x,y,z] 7 | [x,y,z] 

However, in 99.9% of cases it will contain 0 or 1 key-value pairs, for example:

 Key | Value ------------- 1 | [x,y,z] 

How can I effectively determine the memory overhead, if any, to keep empty or unambiguous std::map<int, Point3> , compared to always storing an array of 8 Point3 (4 bytes per float * 3 values ​​* 8 slots = 96 bytes) and one BYTE with bits for which slots contain significant values?

In general, my question is: what is the memory overhead on an empty or almost empty std::map ?

Answer 1

The memory overhead on the card is not so bad. These are usually a few words on a node. Using a card to begin with will definitely be OK in accordance with the “no premature optimization” rule.

However, when you optimize, the map will be high on the list of data structures to replace. But at this point you can profile all the various operations that you use. How often do keys and / or values ​​change? This important information should know before optimization.

[edit] If I proposed a structure, it would be a std::pair<int, Point3D> . The reason is that this probably gives alignment-friendly 16-byte objects. I would not understand keys, because it is useful only for 0.1% of nodes that have several key / value pairs.

Answer 2

Check out this blog post. It takes into account a very thorough analysis of the memory usage of various STL containers (including std::map ) and different platforms / compilers.

In the 64-bit STL that ships with Visual Studio 2010 (Visual C ++ 10):

---

the map uses 32 bytes for the map object itself, then each node map is 26 bytes larger than the size of the contained object (probably 32 bytes after alignment and loss are taken into account). The number of node maps required for a map is 1 greater than the size of the map.