Ion Gaztañaga skrev:
On 21/04/2010 0:10, igaztanaga@gmail.com 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