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.