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-21 13:00:23

Giacomo Drago wrote:
> On 2015-03-19 17:05, Phil Endecott wrote:
>> That almost sounds like an implicit binary tree, except that I guess
>> you're storing the min item in the parent, not the mid.  I.e. to store
>> the values 0 to 6, an implicit binary tree would store:
>>
>> 3 1 5 0 2 4 6
>>
>> The children of item i are at locations 2i+1 and 2i+2.  To iterate the
>> items in order, you do a mid-order traversal.
>>
>> But a (min-) heap with sorted levels would be more like this:
>>
>> 0 1 4 2 3 5 6
>>
>> In this case you can do a pre-order traversal to get the items in-order.
>
> A simple pre-order traversal? Does it work? In your example it clearly 
> does, but you can also have
>
> [ 0 ] [ 1 4 ] [ 2 5 6 7 ]

Well that doesn't look like "each level is kept sorted" to me, but
thanks for the further explanation of what you're actually doing.

It is possible that this is a novel structure.  I'm not convinced
that it is useful.  If you want a reasonably compact representation,
i.e. without the overhead of per-item pointers, but need fast
insertion and lookup (both in terms of computational complexity and
absolute speed), then an in-memory B tree is hard to beat.

Regards,  Phil.