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