Hi Giacomo, Giacomo Drago wrote:
I have been working on a flat_map (http://www.boost.org/doc/libs/1_57_0/doc/html/boost/container/flat_map.html) variant that keeps some of the distinctive features of the original one (contiguous storage/cache friendliness, zero memory overhead/shrink_to_fit support, vector-based representation, etc...) but makes insertion and erasure of the elements much faster, at the price of a slower lookup and in-order traversal.
Explaining how it works requires time and it's not really necessary
No, "how it works" is the first thing I want to know! It's unlikely that you've invented something completely new...
Let's get straight to the benchmarks
Rather than quantified benchmarks, to start with I'd like to know the big-O complexity of the operations. (Personally, I have a flat_map that does batched insertions i.e. the new items are appended individually and then merged at the end of the batch. This will have significant benefits for some workloads.) Regards, Phil.