Re: [boost] [flat_map] Any interest in a flat_map variant that is much faster on insertion/erase at the price of a slower lookup?

Subject: Re: [boost] [flat_map] Any interest in a flat_map variant that is much faster on insertion/erase at the price of a slower lookup?
From: Peter Dimov (lists_at_[hidden])
Date: 2015-03-13 11:04:00

Ion Gaztañaga wrote:
> El 13/03/2015 a las 14:38, Phil Endecott escribió:
>
> > (Personally, I have a flat_map that does batched insertions i.e. the new 
> > items are appended individually and then merged at the end of the batch. 
> > This will have significant benefits for some workloads.)
>
> Yes, this should be added to flat_map. The interface won't be very pretty, 
> but I would like to hear suggestions in this direction.

It doesn't have to have an interface, at least in principle. flat_map can 
just append the new elements to the end, keeping them sorted, until it hits 
a threshold, then merge. Lookups will first look at the new element range 
(because those are likely to be in cache), if not found, at the old element 
range.

You could add a "please merge now" hint, but it won't be required.

Actually, the new element range doesn't even need to be kept sorted, if the 
merge threshold is low, although on the other hand this runs into op< vs 
op== issues, so maybe not.

Of course, when the underlying vector runs out of capacity, a non-inplace 
merge will be performed after reallocation.

Upon closer look on the subject line, did I just reinvent a wheel? :-)