Boost logo

Boost :

Subject: Re: [boost] [containers] flat_set/flat_map could add insert_sorted(begin, end)
From: Thorsten Ottosen (nesotto_at_[hidden])
Date: 2010-04-21 06:57:59


Ion Gaztañaga skrev:
> 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.

That's one appproach. We could also strengthen the precondition
and require that the input sequence is sorted and unique.

The function with a weaker precondition could arguably do the same
thing, but I think leaving that responsibility to the caller
gives the best flexibility; (1) sometimes the caller knows the sequence
is already unique, or (2) sometimes the caller can call unique() first
and reuse memory, or (3) sometimes the caller is forced to use
unique_copy(). In case (1) and (2) we will get better performance, and
possibel also in case
(3) where the caller might have additional information that allows him
to use stack-buffers etc.

So for flat_set/flat_map I think this strong precondition is the best we
can do, and for flat_multiset/flat_multimap, only is_sorted should be
the precondition.

I'm wondering if the same interface would make sense in normal set/map,
but I'm thinking the extra info is little worth compared to
heap-allocations and balancing.

-Thorsten


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk