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-21 13:22:47
On 2015-03-21 17:00, Phil Endecott wrote:
> Giacomo Drago wrote:
> 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.
Well, it is *exactly* "each level is kept sorted", literally. :)
> 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.
I see. Can you provide me with an implementation of such data structure
having the same memory footprint of a flat_map (no per-item pointers)
and better performance characteristics? I look forward to seeing it.