Giacomo Drago
Anyway, I finally managed to find some time to publish the source code with a brief explanation: https://github.com/giacomodrago/flat_map
I think your "brief explanation" is this sentence: [The elements] are organised in a heap where each level is kept sorted. OK. If there is more that I've missed, please let me know. That almost sounds like an implicit binary tree, except that I guess you're storing the min item in the parent, not the mid. I.e. to store the values 0 to 6, an implicit binary tree would store: 3 1 5 0 2 4 6 The children of item i are at locations 2i+1 and 2i+2. To iterate the items in order, you do a mid-order traversal. But a (min-) heap with sorted levels would be more like this: 0 1 4 2 3 5 6 In this case you can do a pre-order traversal to get the items in-order. Have I understood correctly? An implicit tree can clearly do lookup in O(log N). Insertion at a leaf is also O(log N), but I'm not sure about rebalancing; I suspect that each time you move a node you need to move all of its children, which obviously gets expensive. You say that you think your lookup is O(log^2 N), so maybe I've not correctly understood your design. The last time I looked at implicit binary trees, it was with the aim of improving locality of reference: a binary search in a flat_map, although theoretically O(log N), has terribly unfriendly VM and cache behaviour for large N. This is the same argument as for B-trees. Regards, Phil. P.S. Have you looked at Boost.Heap?