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. Best Giacomo