Re: [boost] 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] 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: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2015-03-22 10:41:15

Giacomo Drago wrote:
> 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. :)

To be clear: in your structure, each pair of siblings is ordered.
But those elements are not ordered with respect to the other items
at the same level (the "cousins").

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

There is an in-memory B-tree at google code that looks decent, though
I've not personally used it:

   http://code.google.com/p/cpp-btree/

If you click "Wiki pages - UsageInstructions" at the bottom left of
that page you'll find tables giving the memory overhead.  A B-tree has
no per-item pointers, but it does have per-page pointers; you can
asymptotically approach zero overhead by increasing the page size.
With an infinite page size you effectively have a flat_map, with
a page size of one you have a binary tree.

In practice, a more important influence on memory footprint than the
per-page pointers is the empty space in the pages that results from
splitting after insertion, and after deletion but before merging.
But a flat_map implemented on a std::vector has a similar issue, i.e.
that std::vector doubles its size when it re-allocates.  So a
std::vector will be wasting up to half of the memory that it has
allocated.

Regards,  Phil.