Giacomo Drago wrote:
From your silence on the "sorted vs non sorted" issue, I am positive we are on the same page about that, regardless its relevance.
Yes, I have finally worked out what you're doing there. 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. 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. Looking at some of your benchmark numbers, you seem to be getting about X2 for insertion and erasing, vs. X0.66 for find. So I would expect a "flat map pair" to get comparable performance, and without losing the worst-case complexity of flat_map. Regards, Phil.