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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk