Boost logo

Boost :

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.



Boost list run by bdawes at, gregod at, cpdaniel at, john at