Boost logo

Boost :

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

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? :-)

Boost list run by bdawes at, gregod at, cpdaniel at, john at