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