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