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: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2010-04-21 02:27:51

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.

Best,

Ion