How to implement a custom allocator to be used with std::map?

Question

I'm looking for some pointers on how to implement a custom allocator to be used with a std::map. I'm interested on populating a map with millions of entries without having an allocation for each element in the container (which is the default for this container). The reason for this is to pass data to a third party library that is using a map to store samples of a chart (QCustomPlot) and I'm feeling the performance hit when plotting large time series.

Is it possible to do this with one allocation if the size of the std::map is known in advance?

EDIT: The nodes will be fed in ascending order into the container.

Answer 1

The only thing that a custom allocator can do in that case, would be to avoid some of the overhead used by the default allocator caused by alignment, if you know the final size and overhead of std::map due to internal pointers, you could reserve a buffer with the size needed and in the custom allocator use all that contiguous memory.

The amount of memory this would save will depend on the types you are using on your map, and i don't think it will be that much.

As mentioned on the comments by Öö Tiib and dau_sama your best bet is boost::flat_map, or you could just do it custom via a

std::vector<std::pair<Key,Value>>

Anyway if you can't change the 3rd party lib and it only accepts a std::map you would still be out of luck unless it accepts some type of iterator that you can adapt.