On 2015-03-24 19:32, Phil Endecott wrote:
It seems to me that for an insertion, you'll potentially have to move all of the bottom level; that will be up to half of the container. If my maths is right, you'll do on average one third of the number of moves that a flat_map will do.
I concur with you.
Another way to get the same saving would be to have N normal flat_maps (where N is e.g. 2 or 3). Insert into whichever is currently smallest, and lookup in both. That has the same typical and worst-case complexity as a flat_map, but you can trade off (by constant factors) the cost of insertion vs. the cost of lookup and iteration by adjusting N.
This is simple and brilliant, and can help me with the actual scenario I am dealing with. Do you mind if I use this idea, and I appropriately mention you? At this point I think there is no reason to submit this library to Boost. Best Giacomo