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
> There is an in-memory B-tree at google code that looks decent, though
> I've not personally used it:
> 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
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk