
Boost : 
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: 20150319 15:21:44
Thanks for your kind reply, Phil. I will answer your questions the best
I can.
On 20150319 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 midorder 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 preorder traversal to get the items inorder.
A simple preorder 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 perlevel 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk