Re: [boost] [containers] flat_set/flat_map could add insert_sorted(begin, end)

Subject: Re: [boost] [containers] flat_set/flat_map could add insert_sorted(begin, end)
From: Thorsten Ottosen (nesotto_at_[hidden])
Date: 2010-04-21 06:57:59

Ion Gaztañaga skrev:
> On 21/04/2010 0:10, igaztanaga_at_[hidden] wrote:
>> On 20/04/2010 17:46, Thorsten Ottosen wrote:
>>> Hi Ion,
>> The question is how we know we don't need to reallocate.
> 
> Well, for multimap/set this is trivial. The problem is with set/map, if 
> we want to avoid a new allocation if it's not necessary:
> 
> input_size = distance(begin, end);
> merge_region_size = distance(lower_bound(begin), upper_bound(end));
> non_merge_region_size = size()-merge_region_size;
> 
> final size is between (input_size + non_merge_region_size) and 
> ((input_size + merge_region_size) + non_merge_region_size)
> 
> Depending on input_size, (e.g.: if it's less than free_mem = 
> capacity()-size()) we could first avoid reallocation. Or we could take 
> some input elements (begin(), begin() + free_mem), merge and see what 
> happens (if free_space is nearly exhausted or not). If there is no space 
> left or is much less than the remaining imput, we grow vector capacity 
> and try again.

That's one appproach. We could also strengthen the precondition
and require that the input sequence is sorted and unique.

The function with a weaker precondition could arguably do the same 
thing, but I think leaving that responsibility to the caller
gives the best flexibility; (1) sometimes the caller knows the sequence 
is already unique, or (2) sometimes the caller can call unique() first 
and reuse memory, or (3) sometimes the caller is forced to use 
unique_copy(). In case (1) and (2) we will get better performance, and 
possibel also in case
(3) where the caller might have additional information that allows him 
to use stack-buffers etc.

So for flat_set/flat_map I think this strong precondition is the best we 
can do, and for flat_multiset/flat_multimap, only is_sorted should be 
the precondition.

I'm wondering if the same interface would make sense in normal set/map,
but I'm thinking the extra info is little worth compared to 
heap-allocations and balancing.

-Thorsten