Boost logo

Boost :

Subject: [boost] [flat_map] Any interest in a flat_map variant that is much faster on insertion/erase at the price of a slower lookup?
From: Giacomo Drago (giacomo_at_[hidden])
Date: 2015-03-13 03:51:54


My library is not ready for a formal review process, and I'd like to ask
whether there is some potential interest first, thus saving everybody a
lot of time.

I have been working on a flat_map
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 if
there is no interest in the first place (e.g. "thanks, but we have no
use for this"). Let's get straight to the benchmarks and to some

             #elems: 50000
        Random insertion: 18.605 ms
        Random find: 24.382 ms
        Iteration: 5.658 ms
        Random erase: 37.166 ms
        Random insertion: 400.141 ms
        Random find: 12.352 ms
        Iteration: 7.099 ms
        Random erase: 467.051 ms
        Random insertion: 611.678 ms
        Random find: 6.293 ms
        Iteration: 0.038 ms
        Random erase: 615.311 ms

             #elems: 200000
        Random insertion: 146.394 ms
        Random find: 163.506 ms
        Iteration: 21.973 ms
        Random erase: 225.314 ms
        Random insertion: 5068.93 ms
        Random find: 65.618 ms
        Iteration: 34.244 ms
        Random erase: 6851.09 ms
        Random insertion: 10696.9 ms
        Random find: 43.896 ms
        Iteration: 0.254 ms
        Random erase: 10604 ms

Of course one doesn't expect the random insertion to have a performance
that is comparable to the one of a tree-based map, like std::map.
However, my experimental::flat_map provides a better trade-off than
boost's flat_map for me, as random insertion is massively faster and in
the big picture of the application I am developing this is making a hell
of a difference.

Am I making any sense? Shall I polish the implementation, publish it,
and submit a proposal? I'd really appreciate your feedback.

Kind Regards

Boost list run by bdawes at, gregod at, cpdaniel at, john at