On 22/08/2008, Carvalho, Malcolm
Is there any way to make this insertion time constant irrespective of the number of elements already present in the set?
Insertion time is amortized constant - which means that the average speed is constant. Occasionally a rehash occurs which make an individual insertion much slower. The third block of insertions probably doesn't contain a rehash, which is why it's faster. While the fourth does, and because the number of elements is now quite large, it's a larget hit. You can avoid this by rehashing in advance, so if you first call 'set.rehash(100001)', you should get roughly constant speed (as long as you don't have to many collisions). For a brief guide to an appropriate value for rehash see http://preview.tinyurl.com/5zbfef. Hope that helps, Daniel