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-03-19 15:21:44

Thanks for your kind reply, Phil. I will answer your questions the best 
I can.

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 ]

In that case, how do you 'jump' from 2 up to 4 and then down again to 5? 
How do you know "who's next" (as it can be someone ten levels above)? I 
am just confused and talking nonsense?

> You say that you think your lookup is O(log^2 N), so maybe I've not
> correctly understood your design.

I basically make a per-level binary search with some minor optimizations 
easily understandable by reading the code (but I can elaborate, if I am 
making some sense so far and you wish me to continue). How can you 
search in O(log N) in a heap where the elements of each level are sorted 
(not antagonizing, genuinely just asking for curiosity)?

If I convinced you so far, then we can get into how insertion and 
erasure work.

> P.S. Have you looked at Boost.Heap?
I used Boost.Heap with great profit in the past. I didn't use any Boost 
library for this project because the implementation is a throwaway 
prototype and hacking up a modified heap by the means of a std::vector 
was, for me, the fastest way to get the job done - for now.
In the unlikely case this strange and hardly useful data structure made 
it into Boost, it would be rewritten and properly Boostified, without 
any reinvention of the wheel of course, and stress tested to death.

Best
Giacomo