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: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2015-03-13 12:39:50

El 13/03/2015 a las 16:04, Peter Dimov escribió:
>
> It doesn't have to have an interface, at least in principle. flat_map
> can just append the new elements to the end, keeping them sorted, until
> it hits a threshold, then merge. Lookups will first look at the new
> element range (because those are likely to be in cache), if not found,
> at the old element range.

That would complicate the container, and break some invariants, like 
"equal_range". flat_map is designed to cover an scenario for more 
searches than insertions, maybe another container could be designed for 
a different scenario.

> Actually, the new element range doesn't even need to be kept sorted, if
> the merge threshold is low, although on the other hand this runs into
> op< vs op== issues, so maybe not.

You've touched an interesting point. Sort+Merging could improve flat_map 
performance in some other scenarios. The option to do a merge can be 
added to a range insertion, current implementation has not very good 
performance due to excessive data movement. In this scenario we could 
back-insert, sort and merge. The problem is:

-> It requires additional memory (stable_sort is needed for 
flat_multimap) to achieve O(N·log(N)). inplace_merge requires additional 
memory to obtain O(N). A user might not want to pay for this (you might 
need 2x temporary memory). One option is to use the remaining capacity 
as additional memory by default and optionally add an insertion option 
that allocates temporary storage to achieve maximum performance.

-> we need to reimplement std::sort/std::stable_sort/std::inplace_merge 
in a Boost.Move-compatible way (using boost::adl_move_swap). It should 
allow customizing the temporary storage source. Maybe sorting experts 
would like to implement it in Boost.Move.

> Of course, when the underlying vector runs out of capacity, a
> non-inplace merge will be performed after reallocation.
>
> Upon closer look on the subject line, did I just reinvent a wheel? :-)

Maybe, but everyone should reinvent the wheel at least once in life. 
It's an great pleasure!

Best,

Ion