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