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: Giacomo Drago (giacomo_at_[hidden])
Date: 2015-04-07 09:20:29

On 2015-03-24 19:32, Phil Endecott wrote:
> It seems to me that for an insertion, you'll potentially have to
> move all of the bottom level; that will be up to half of the
> container.  If my maths is right, you'll do on average one third
> of the number of moves that a flat_map will do.

I concur with you.

> Another way to get the same saving would be to have N normal
> flat_maps (where N is e.g. 2 or 3).  Insert into whichever is
> currently smallest, and lookup in both.  That has the same
> typical and worst-case complexity as a flat_map, but you can
> trade off (by constant factors) the cost of insertion vs. the
> cost of lookup and iteration by adjusting N.

This is simple and brilliant, and can help me with the actual scenario I 
am dealing with. Do you mind if I use this idea, and I appropriately 
mention you? At this point I think there is no reason to submit this 
library to Boost.

Best
Giacomo