Boost logo

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: 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.


Boost list run by bdawes at, gregod at, cpdaniel at, john at