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: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2015-03-24 15:32:04

Giacomo Drago wrote:
> From your silence on the "sorted vs non sorted" issue, I am positive we 
> are on the same page about that, regardless its relevance.

Yes, I have finally worked out what you're doing there.

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.

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.  Looking at some
of your benchmark numbers, you seem to be getting about X2 for
insertion and erasing, vs. X0.66 for find.  So I would expect
a "flat map pair" to get comparable performance, and without
losing the worst-case complexity of flat_map.

Regards,  Phil.