Re: [boost] [flat_map] Any interest in a flat_map variant that is much faster on insertion/erase at the price of a slower lookup?

Subject: Re: [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 05:11:09

On 2015-03-13 08:27, Dominique Devienne wrote:
> On Fri, Mar 13, 2015 at 9:22 AM, Ion Gaztañaga <igaztanaga_at_[hidden]> wrote:
>>
>> Just a question. Are your insertions one by one or by range?
>>
>
> Might also be interesting to know if your perf numbers are based on a
> primitive key or a UDT, and whether the relative performance changes
> depending on key/value sizes. --DD

Insertions are one by one, and they are random with respect to the order 
of the keys. Same applies for lookups and erasures. No cheating.

I will try with different keys that are not PDOs and have non-trivial 
comparators, but I expect the benchmarks to reflect my previous 
findings. The bottom line is that it makes fewer comparisons and swaps 
when inserting and removing, and more comparisons when looking up. 
Elements are not *quite* sorted into the storage vector, of course.

The main use case I see for this data structure - and I am already using 
it even though not in a production environment - is that you may need a 
very space-efficient associative, sorted container that is not so 
painfully slow when it comes to insert/erase elements.

I'll send more benchmarks. Any interest in the general design and the 
source code (not "boostified" yet)?

Best
Giacomo