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: Giacomo Drago (giacomo_at_[hidden])
Date: 2015-03-22 10:58:25

Hi Phil, thanks for following up.

On 2015-03-22 14:41, Phil Endecott wrote:
> 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").

Well... To be clear: they are. For each level of the binary heap (if we 
agree on the definition of level) the elements are sorted. Indeed, 
that's basically the whole point of it, otherwise I couldn't make a 
level-wise binary search when looking up, and I would need some sort of 
sorcery to get those benchmarks. Are we... on the same page? Am I 
missing something?

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

On a vector you can easily shrink_to_fit thus bringing the overhead to 
zero (if you neglect the vector size and a pointer to its buffer). I'll 
study the B-tree and its trade-offs - I declare my ignorance in this 
particular area - but I still think a flat_map (that does not mean this 
flat_map in particular) has some reason to be.

Best
Giacomo