5

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.

Darien Pardinas
  • 5,910
  • 1
  • 41
  • 48
  • Maybe this answers your question? http://stackoverflow.com/questions/13049340/initializing-a-stdmap-when-the-size-is-known-in-advance – Simon Karlsson Dec 30 '14 at 08:36
  • 1
    It's possible, but be aware that the size required will not be `(sizeof(Key) + sizeof(Value)) * num_elem`. You'll need to over-allocate to some degree because one of the first things a `map` will do is [`rebind_alloc`](http://en.cppreference.com/w/cpp/memory/allocator_traits) to some internal tree node type that it uses to hold each element. Other than that, my advice would be to read the `std::allocator` and `std::allocator_traits` docs, and then look at how you stdlib implements the former (assuming you can't find a tutorial on the topic). – Praetorian Dec 30 '14 at 08:42
  • 1
    Things displayed on graphs are usually sequential in nature so perhaps boost::flat_map (it is a sorted vector under hood) is better than std::map. – Öö Tiib Dec 30 '14 at 08:56
  • If you have the liberty to chnage the client's code as well, I'll suggest you to use boost::flat_map too, it does exactly what you need. Also: could you elaborate more on what kind of values you need to store? A simple solution could be as easy as store values in a vector, and sort the vector once based on your specific criteria. – dau_sama Apr 20 '15 at 11:56

1 Answers1

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.

PedroMVU
  • 83
  • 1
  • 6