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. Best, Ion