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 08:24:59

Ion Gaztañaga skrev:
> On 21/04/2010 12:57, Thorsten Ottosen wrote:
>> That's one appproach. We could also strengthen the precondition
>> and require that the input sequence is sorted and unique.
> 
> You still need to remove duplicates between the unique sorted input 
> range and stored values. Unless you require that the input sequence 
> should not contain any value already stored in the container (this could 
> be a more optimized function, it has a worst case with just a single 
> reallocation since the final size is size() + input_range_size).

I missed that, thanks. My use case actually have this property too.

Even without this condition we should be able to have only two 
reallocations: one initial that might allocate too much space and a 
second one which is basically shrink_to_fit() which can be chosen only 
to be performed if it reduces the space more than, say 10%. Call this 
strategy A (the percentage might be a default argument of the function).

Another strategy (B) would be to assume something about the average 
number of distinct elements. This is difficult to do in general, and
so the user would be asked for a number in the interface, specifying his 
belief in the number of elements to be inserted. It might be difficult 
even for the user to do this.

The good thing about strategy A is that it gives a single allocation in 
the worst case for the case where all the new elements must be stored
because the size estimation is correct. Therefore this sounds like a 
good approach.

-Thorsten